Binary Linear Programming

Binary Linear Programming#

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

\[\begin{split} \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} \end{split}\]

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

@jm.Problem.define('binary_lp', sense=jm.ProblemSense.MAXIMIZE)
def problem(problem: jm.DecoratedProblem):
    # define variables
    S = problem.Float(ndim=2)
    M = problem.DependentVar(S.len_at(0))
    N = problem.DependentVar(S.len_at(1))
    b = problem.Float(shape=(M,))
    c = problem.Float(shape=(N,))
    x = problem.BinaryVar(shape=(N,))
    
    # Objective
    problem += jm.sum(c[i] * x[i] for i in N)
    
    # Constraints
    problem += problem.Constraint(
        "eq_const", 
        [jm.sum(S[j, i] * x[i] for i in N) == b[j] for j in M]
    )

problem
\[\begin{split}\begin{array}{rl} \text{Problem}\colon &\text{binary\_{}lp}\\\displaystyle \max &\displaystyle \sum _{i=0}^{N-1}{{c}_{i}\cdot {x}_{i}}\\&\\\text{s.t.}&\\&\begin{aligned} \text{eq\_{}const}&\quad \displaystyle \sum _{i=0}^{N-1}{{S}_{j,i}\cdot {x}_{i}}={b}_{j}\quad \forall j\;\text{s.t.}\;j\in \left\{0,\ldots ,M-1\right\}\end{aligned} \\&\\\text{where}&\\&\text{Decision Variables:}\\&\qquad \begin{alignedat}{2}x&\in \mathop{\mathrm{Array}}\left[N;\left\{0, 1\right\}\right]&\quad &1\text{-dim binary variable}\\\end{alignedat}\\&\\&\text{Placeholders:}\\&\qquad \begin{alignedat}{2}b&\in \mathop{\mathrm{Array}}\left[M;\mathbb{R}\right]&\quad &1\text{-dimensional array of placeholders with elements in }\mathbb{R}\\c&\in \mathop{\mathrm{Array}}\left[N;\mathbb{R}\right]&\quad &1\text{-dimensional array of placeholders with elements in }\mathbb{R}\\S&\in \mathop{\mathrm{Array}}\left[(-)\times (-);\mathbb{R}\right]&\quad &2\text{-dimensional array of placeholders with elements in }\mathbb{R}\\\end{alignedat}\\&\\&\text{Dependent Variables:}\\&\qquad \begin{alignedat}{2}M&=\mathop{\mathtt{len\_{}at}}\left(S,0\right)&\quad &\in \mathbb{N}\\N&=\mathop{\mathtt{len\_{}at}}\left(S,1\right)&\quad &\in \mathbb{N}\\\end{alignedat}\end{array} \end{split}\]

The meaning of @jm.Problem.define(..., 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.

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

We solve that problem with jijzept_solver.

import jijzept_solver

instance = problem.eval(instance_data)
solution = jijzept_solver.solve(instance, solve_limit_sec=1.0)

Check the results and solution#

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

# get the information of the result
obj = solution.objective
df = solution.decision_variables_df
const = solution.constraints_df

print(f"Objective value : {obj}")
print(f"Decision variakbles : \n {df}")
print(f"Constraints : \n {const}")

Objective value : 12.0
Decision variakbles : 
       kind  lower  upper name subscripts description substituted_value  value
id                                                                           
0   Binary    0.0    1.0    x        [0]        <NA>              <NA>    0.0
1   Binary    0.0    1.0    x        [1]        <NA>              <NA>    0.0
2   Binary    0.0    1.0    x        [2]        <NA>              <NA>    1.0
3   Binary    0.0    1.0    x        [3]        <NA>              <NA>    1.0
4   Binary    0.0    1.0    x        [4]        <NA>              <NA>    1.0
Constraints : 
    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>
Contents