Binary Linear Programming

Binary Linear Programming#

In this section, we will show you how to model binary linear programming $\( \begin{align} &\max_{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\}. \end{align} \)$

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 Budgeting

  • Warehouse Location

A linear programming solver based on the branch-and-bound method is useful if the size is not too 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 problem
problem = jm.Problem('binary_lp', sense=jm.ProblemSense.MAXIMIZE)

# define variables
S = jm.Placeholder('S', ndim=2)
M = S.len_at(0, latex="M")
N = S.len_at(1, latex="N")

b = jm.Placeholder('b', ndim=1)
c = jm.Placeholder('c', ndim=1)
x = jm.BinaryVar('x', shape=(N,))
i = jm.Element('i', belong_to=(0, N))
j = jm.Element('j', belong_to=(0, M))

# Objective function
problem += jm.sum(i, c[i]*x[i])

# Constraints
problem += jm.Constraint("eq_const", jm.sum(i, S[j, i] * x[i]) == b[j], forall=j)

problem
\[\begin{split}\begin{array}{cccc}\text{Problem:} & \text{binary\_lp} & & \\& & \max \quad \displaystyle \sum_{i = 0}^{N - 1} c_{i} \cdot x_{i} & \\\text{{s.t.}} & & & \\ & \text{eq\_const} & \displaystyle \sum_{i = 0}^{N - 1} S_{j, i} \cdot x_{i} = b_{j} & \forall j \in \left\{0,\ldots,M - 1\right\} \\\text{{where}} & & & \\& x & 1\text{-dim binary variable}\\\end{array}\end{split}\]

The meaning of Problem(..., sense=jm.ProblemSense.MAXIMIZE) is to explicitly choose that the optimization problem is to be solved by maximizing the objective function. If sense is not specified, the default is to solve the problem by minimizing the objective function.

The len_at 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.

e.g.

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

Prepare an instance#

Next, we set the instance of the problem. As an example, we set up the following instance:

# set S matrix
inst_S = [[0, 2, 0, 2, 0], [1, 0, 1, 0, 1], [1, 2, 3, 2, 1]]
# set b vector
inst_b = [2, 2, 6]
# set c vector
inst_c = [1, 2, 3, 4, 5]
instance_data = {'S': inst_S, 'b': inst_b, 'c': inst_c}
\[\begin{split}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)\end{split}\]

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 JijSolver#

We solve that problem with jijsolver.

import jijsolver

interpreter = jm.Interpreter(instance_data)
instance = interpreter.eval_problem(problem)
solution = jijsolver.solve(instance, time_limit_sec=1.0)

Check the results and solution#

Let’s check the solution obtained. The solution obtained from jijsolver is managed in OMMX format. .decision_variables, .objective, and .constraints allow us to get the information of decision variables, objective function, and constraints in the problem, respectively.

# get the information of the result
df = solution.decision_variables
obj = solution.objective
const = solution.constraints

print("Objective value : {}".format(obj))
print(const)

Objective value : 12.0
   equality  value         used_ids      name subscripts description  \
id                                                                     
0        =0    0.0           {1, 3}  eq_const        [0]        <NA>   
1        =0    0.0        {0, 2, 4}  eq_const        [1]        <NA>   
2        =0    0.0  {0, 1, 2, 3, 4}  eq_const        [2]        <NA>   

   dual_variable removed_reason  
id                               
0           <NA>           <NA>  
1           <NA>           <NA>  
2           <NA>           <NA>

Also, we can check the solution \(x\) as follow:

# check the solution
x_result = df["value"].to_list()
print(x_result)

[0.0, 0.0, 1.0, 1.0, 1.0]
Contents