Permalink: 2014-07-29 by Kai Sun in Blog tags: SCIP PuLP ILP LP

1. Introduction

Integer linear programming (ILP) is a method to achieve the best outcome in a mathematical model whose requirements are represented by linear relationships and unknown variables are required to be integers. Integer linear programming can be applied to various fields of study and has proved useful in diverse types of problems. In contrast to linear programming, which can be solved efficiently in the worst case, integer linear programming problems are in many practical situations NP-hard. Therefore, solving integer linear programming is not easy. Moreover, despite the fact that there are many professional solvers which can solve integer linear programming efficiently in most cases, most of them can only give one optimal solution even if many solutions exist. However, more than one solution, or even all solutions are needed in some applications.

In this article, PuLP and SCIP (Solving Constraint Integer Programs) are combined together to solve that general problem, that is, given an integer linear programming problem, calculate all feasible solutions efficiently if the number of feasible solutions is not infinite. Specifically, first, PuLP is used to generate the integer programming model file; then the model file is passed to SCIP and all feasible solutions of the model are calculated with SCIP.

PuLP is an LP modeler written in python. PuLP can generate MPS or LP files and call GLPK, COIN CLP/CBC, CPLEX, and GUROBI to solve linear problems. SCIP is currently one of the fastest non-commercial solvers for mixed integer programming (MIP) and mixed integer nonlinear programming (MINLP). It is also a framework for constraint integer programming (CIP) and branch-cut-and-price. It allows for total control of the solution process and the access of detailed information down to the guts of the solver.

Alt text

The remainder of the article is organized as follows. In section 2, a sample problem is described which is used to illustrate the steps in the other sections. Section 3 shows how to generate the model file. Section 4 shows how to calculating all feasible solutions of a given model file.

2. Sample Problem

Problem description:

Kai Sun would like to buy 100 chickens with 100 LTC. A rooster, a hen and a chick costs 3 LTC, 2LTC and 0.5LTC respectively. How many roosters, hens and chicks should Kai buy? If there are many solutions, output all of them.

Convert the problem to ILP:

Variables:

Integer x, y, z, d

Constraints:

x+y+z = 100 
3x+2y+0.5z = 100 
0 <= x, y, z, d

Objective function:

Minimize d

Here we use a dummy variable d because for this problem, there are no objective function need to be optimized.

3. Model File Generation

With PuLP, it is easy to express the ILP and generate ".lp" file, which can be further read by SCIP.

from pulp import *
prob = LpProblem("chicken", LpMinimize)
x = LpVariable("x", 0 , None, LpInteger) # 0 is the lower bound;
                                  # "None" means no upper bound;
y = LpVariable("y", 0 , None, LpInteger)
z = LpVariable("z", 0 , None, LpInteger)

prob += x+y+z == 100, "constraint 1"
prob += x*3+y*2+z*0.5 == 100, "constraint 2"

prob.writeLP("problem.lp")

In this example, model file "problem.lp" is generated, and the contents of "problem.lp" are shown below:

\* chicken *\
Minimize
OBJ: __dummy
Subject To
constraint_1: x + y + z = 100
constraint_2: 3 x + 2 y + 0.5 z = 100
Bounds
__dummy = 0
0 <= x
0 <= y
0 <= z
Generals
x
y
z
End

4. Calculating All Feasible Solutions

With SCIP, all feasible solutions of "problem.lp" can be calculated easily in the following steps:

  1. Read model file using read command.

    SCIP> read problem.lp
    
  2. Set the parameters which are required for collecting all feasible solutions.

    SCIP> set emphasis counter
    SCIP> set constraints countsols collect TRUE
    
  3. Calculating all feasible solutions using count command.

    SCIP> count
    
  4. Write all feasible solutions to a file.

    SCIP> write allsolutions chicken_sol.txt
    

Finally, file "chicken_sol" contains all feasible solutions of the sample problem:

#, z, y, x, objval
1(1), 80, 0, 20, 0
2(2), 68, 30, 2, 0
3(3), 70, 25, 5, 0
4(4), 72, 20, 8, 0
5(5), 74, 15, 11, 0
6(6), 76, 10, 14, 0
7(7), 78, 5, 17, 0

References

  1. Tobias Achterberg. SCIP: Solving constraint integer programs. Mathematical Programming Computation, 1(1):1-41, 2009. http://mpc.zib.de/index.php/MPC/article/view/4
  2. https://pypi.python.org/pypi/PuLP
  3. http://en.wikipedia.org/wiki/Linear_programming
  4. http://www.gnu.org/software/glpk/glpk.html
  5. http://www.coin-or.org/
  6. http://www.cplex.com/
  7. http://www.gurobi.com/