# Binary linear programming

In this section we will show you how to model binary linear programming

$\min_{x} \sum_i c_i x_i\\ \mathrm{s.t.}~\sum_{i}S_{j, i}x_i = b_j,~\forall j\\ x_i \in \{0, 1\}.$

## Applications​

Linear programming problems with discrete variables, known as 'Mixed integer programming (MIP)', have many applications. You may be surprised at the wide range of applications even though the objective function and constraints are all linear. Two applications are listed below, but there are too many applications to list here.

• Capital Budeting
• Warehouse Location

A linear programming solver based on the branch-and-bound method is useful if the size is not that large. Of course, JijModeling supports linear programming solvers. However, for consistency with other tutorials, we will solve it here using Simulated annealing in JijZept.

## Modeling by JijModeling​

import jijmodeling as jm# set problemproblem = jm.Problem('binary_lp')# define variablesS = jm.Placeholder('S', dim=2)M = S.shape[0].set_latex("M")N = S.shape[1].set_latex("N")b = jm.Placeholder('b', shape=(M, ))c = jm.Placeholder('c', shape=(N, ))x = jm.Binary('x', shape=(N, ))i = jm.Element('i', (0, N))j = jm.Element('j', (0, M))# Objectiveproblem += jm.Sum(i, c[i]*x[i])# Constriantsproblem += jm.Constraint("eq_const", jm.Sum(i, S[j, i] * x[i]) == b[j], forall=j)problem
\begin{alignat*}{4}\text{Problem} & \text{: binary\_lp} \\ \min & \quad \sum_{ i = 0 }^{ N - 1 } c_{i} \cdot x_{i} \text{s.t.} & \\& \text{eq\_const} :\\ &\quad \quad \sum_{ i = 0 }^{ N - 1 } S_{j,i} \cdot x_{i} = b_{j},\ \forall j \in \left\{ 0 ,\ldots , M - 1 \right\} \\[8pt]& x_{i_{0}} \in \{0, 1\}\end{alignat*}

The set_latex method can be used to override the representation of a formula in the LaTeX display on Jupyter; overriding the shape often results in a clean look.

Ex.

S = jm.Placeholder('S', dim=2)M = S.shape[0].set_latex("M")N = S.shape[1].set_latex("N")

## Prepare an instance​

# set S matrixinst_S = [[0, 2, 0, 2, 0], [1, 0, 1, 0, 1], [1, 2, 3, 2, 1]]# set b vectorinst_b = [2, 2, 6]# set c vectorinst_c = [1, 2, 3, 4, 5]instance_data = {'S': inst_S, 'b': inst_b, 'c': inst_c}
$S = \left( \begin{array}{ccccc} 0 & 2 & 0 & 2 & 0 \\ 1 & 0 & 1 & 0 & 1 \\ 1 & 2 & 3 & 2 & 1 \end{array}\right), \quad \mathbf{b} = \left( \begin{array}{c} 2 \\ 2 \\ 6 \end{array}\right), \quad \mathbf{c} = \left( \begin{array}{c} 1 \\ 2 \\ 3 \\ 4 \\ 5 \end{array}\right)$
info

Be careful with variable names and scopes. Variable names such as S, b, and c are used when modeling with JijModeling and cannot be used when preparing instances. To avoid this problem, we use the prefix inst_.

## Solve by JijZept's SA​

JijZept's SA solves the problem using SA after converting it to an unconstrained optimization problem called QUBO. Therefore, the constraints are assigned to the objective function as penalty terms, and we must set their strength.

The strength of the penalty term is passed in the multipliers argument in dictionary form, along with the labels of the constraint conditions.

If the search option is set to True, SA will iterate through the problem and JijZept middleware will adjust the multiplier's strength.

import jijzept as jz# set samplersampler = jz.JijSASampler()# solve problemresult = sampler.sample_model(problem, instance_data, multipliers={"eq_const": 1}, search=True)

## Check the results​

• result.record: store the value of solutions
• result.evaluation: store the results of evaluation of the solutions.

First, check the results of evaluation.

# Show the result of evaluation of solutionsprint("Energy: ", result.evaluation.energy)       # Energy is objective value of QUBOprint("Objective: ", result.evaluation.objective) # Objective values of original constrained problemprint("Constraints violation: ", result.evaluation.constraint_violations)  # violation of constraints
Energy:  [-1.899999976158142, -115.4111099243164, -307.6000061035156, -309.3999938964844, -309.3999938964844, -308.6000061035156, -309.3999938964844, -309.0, -309.79998779296875, -309.3999938964844, -309.79998779296875, -308.6000061035156, -309.79998779296875, -309.3999938964844, -309.79998779296875]Objective:  [3.0, 11.0, 12.0, 8.0, 8.0, 12.0, 8.0, 10.0, 6.0, 8.0, 6.0, 12.0, 6.0, 8.0, 6.0]Constraints violation:  {'eq_const': [4.0, 2.0, 2.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0]}

### Extract feasible solutions and an index of lowest solution​

import numpy as np# Get feasible solution indexfeasible = [i for i, violation in enumerate(result.evaluation.constraint_violations["eq_const"]) if violation == 0]# Get feasible objectiveobjective = np.array(result.evaluation.objective)feas_obj = {i: obj_value for i, obj_value in zip(feasible, objective[feasible])}lowest_index = min(feas_obj, key=feas_obj.get)print(f"Lowest solution index: {lowest_index}, Lowest objective value: {feas_obj[lowest_index]}")
Lowest solution index: 8, Lowest objective value: 6.0

## Check the solution​

Finally, we get the solution from JijZept.

# check solutionnonzero_indices, nonzero_values, shape = result.record.solution["x"][lowest_index]print("indices: ", nonzero_indices)print("values: ", nonzero_values)
indices:  ([0, 1, 2],)values:  [1, 1, 1]