Calculating All Feasible Solutions of Integer Linear Programming with PuLP and SCIP
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 NPhard. 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 noncommercial solvers for mixed integer programming (MIP) and mixed integer nonlinear programming (MINLP). It is also a framework for constraint integer programming (CIP) and branchcutandprice. 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
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:

Read model file using
read
command.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
count
command.SCIP> count

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
 Tobias Achterberg. SCIP: Solving constraint integer programs. Mathematical Programming Computation, 1(1):141, 2009. http://mpc.zib.de/index.php/MPC/article/view/4
 https://pypi.python.org/pypi/PuLP
 http://en.wikipedia.org/wiki/Linear_programming
 http://www.gnu.org/software/glpk/glpk.html
 http://www.coinor.org/
 http://www.cplex.com/
 http://www.gurobi.com/