Calculating All Feasible Solutions of Integer Linear Programming with PuLP and SCIP
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.
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
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:
Integer x, y, z, d
x+y+z = 100 3x+2y+0.5z = 100 0 <= x, y, z, 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:
Read model file using
SCIP> read problem.lp
Set the parameters which are required for collecting all feasible solutions.
SCIP> set emphasis counter SCIP> set constraints countsols collect TRUE
Calculating all feasible solutions using
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
- 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