Solve MILP problem using python

Python-MIP is a library that includes many tools for modeling and solving Mixed-Integer Linear Programming (MILP) problems. With user-friendly interface and relatively high performance, it's a good choice for solving MILP problems. In this post, we will dive into how to solve a MILP model by Python-MIP.

1. Install and set up#

Make sure you have installed Python. Install Python-MIP by running the following command

pip install mip

Import Python-Mip

import mip

2. Initialize model#

The following code creates an empty MILP model with default settings.

model = mip.Model()

The model with default setting has objective function Minimize and use solver CBC. To modify these settings, use the following code.

# use GRB for Gurobi
model = mip.Model(sense=mip.MAXIMIZE, solver_name=mip.CBC)

3. Add variables#

Add a variable to model using method add_var().

x = m.add_var()

The variable with default config belongs to set $\mathbb{R}^+$ . Change variable type, upper bound, lower bound using parameters var_type, ub, lb

x = m.add_var(var_type=mip.BINARY) # x in {0; 1}
y = m.add_var(var_type=mip.INTEGER) # y is integer
z = m.add_var(lb=0, ub=5) # 0 ≤ z ≤ 5

4. Add constraints#

Add a constraint to model using method add_constr()

# add constraint 4x + y ≤ 11
model.add_constr(4*x + y <= 11)
 
# add constraint 4x + y = 11
model.add_constr(4*x + y == 11)
 
# add constraint 4x + y ≥ 11
model.add_constr(4*x + y >= 11)

5. Objective function and optimize model#

# Set objective min(2x + y)
model = mip.Model(sense=mip.MINIMIZE)
model.objective = 2*x+y
 
# Solve model
model.optimize()

6. Example#

\begin{aligned} \text{min} \quad & 2x + y && \\ \text{s.t} \quad & 4x + y & \leq & \quad 11 \\ & x + y & = & \quad 0 \\ & x & \geq & \quad 0 \\ & y & \geq & \quad 0 \\ & x, y & \in & \quad \mathbb{Z}^+\\ \end{aligned}

The following code solves the MILP model above

"""
filename: main.py
run command: python main.py
"""
import mip
 
model = mip.Model(sense=mip.MINIMIZE, solver_name=mip.CBC)
x = model.add_var(lb=0, ub=mip.INF, var_type=mip.INTEGER)
y = model.add_var(lb=0, ub=mip.INF, var_type=mip.INTEGER)
 
# Set objective function
model.objective = 2*x+y
# Set constraints
model.add_constr(4*x + y <= 11)
model.add_constr(x + y == 5)
 
model.optimize() # Solve model
print('-------------------------------------------------')
# Print solution
print(f'x: {x.x}')
print(f'y: {y.x}')

Running the code above yields the following results: optimal solution $x = 0$ , $y = 5$ , optimal value 5, and solving time 0.04 seconds

Welcome to the CBC MILP Solver
Version: Trunk
Build Date: Oct 28 2021
 
Starting solution of the Linear programming relaxation problem using Primal Simplex
 
Coin0506I Presolve 0 (-2) rows, 0 (-2) columns and 0 (-4) elements
Clp0000I Optimal - objective value 5
Coin0511I After Postsolve, objective 5, infeasibilities - dual 0 (0), primal 0 (0)
Clp0032I Optimal objective 5 - 0 iterations time 0.032, Presolve 0.02, Idiot 0.00
 
Starting MIP optimization
Cgl0004I processed model has 0 rows, 0 columns (0 integer (0 of which binary)) and 0 elements
Cgl0015I Clique Strengthening extended 0 cliques, 0 were dominated
Cbc3007W No integer variables
Total time (CPU seconds):       0.04   (Wallclock seconds):       0.04
 
-------------------------------------------------
x: 0.0
y: 5.0