Lesson 1

The integer linear programming (ILP) problem is about maximizing (or minimizing) a linear function subject to linear constraints over integer variables. Many combinatorial optimization problems can be easily reduced to it.

The code below shows how to use an ILP solver to find an integer point satisfying the system \[x \ge 0, \quad y \ge 0, \quad x+7y \le 17{,}5, \quad x \le 3{,}5,\] where the maximum of the objective function \(x+10y\) is achieved.

from mip import *


model = Model(sense=MAXIMIZE, solver_name='cbc')
model.verbose = False

x = model.add_var(var_type=INTEGER)
y = model.add_var(var_type=INTEGER)

model += x >= 0
model += y >= 0
model += x + 7 * y <= 17.5
model += x <= 3.5

model.objective = x + 10 * y
model.optimize()

print(model.objective_value)
print(x.x, y.x)

23.0
3.0 2.0