Mixed-Integer Programming (MIP)

I was recently invited to join a data science project focused on optimizing combinations of variables that take on integer values. Through this project, I had the opportunity to learn about Mixed-Integer Programming (MIP), and I’d like to share some insights here.

What is a MIP solver?

A Mixed-Integer Programming (MIP) problem is a special case of linear optimization in which some or all variables are required to take integer values while the objective function and constraints remain linear.

Example

Alright, the definition above is from the textbook. Now, let’s look at a practical example along with a sample Python code to better illustrate what MIP is.

Suppose we manage a workshop that manufactures chairs (profit of SGD 10 each) and tables (profit of SGD 20 each). Producing one unit of each requires the following resources:

The workshop has 100 hr of carpentry and 40 hr of painting this week, Products cannot be split, which means only whole chairs/tables may be built.

Get Sin Jie’s stories in your inbox

Join Medium for free to get updates from this writer.

Remember me for faster sign in

What is the profit-optimizing production plan?

Solution

Python code to resolve the question above:

"""
Furniture production MIP solved with OR-Tools (CBC backend).

Scenario
--------
Make chairs (profit SGD20) and tables (profit SGD 30) with
resource limits:
  • Carpentry: 100 h  (3 h/ chair, 4 h/ table)
  • Painting :  40 h  (1 h/ chair, 2 h/ table)

Decision vars are integers.  Maximise total profit.
"""

from ortools.linear_solver import pywraplp


def main():
    # 1. Build a CBC mixed-integer solver
    solver = pywraplp.Solver.CreateSolver(
        "CBC_MIXED_INTEGER_PROGRAMMING"
    )
    if not solver:
        raise RuntimeError("CBC solver unavailable")

    infinity = solver.infinity()

    # 2. Decision variables (non-negative integers)
    chairs = solver.IntVar(0, infinity, "chairs")
    tables = solver.IntVar(0, infinity, "tables")

    # 3. Constraints
    solver.Add(3 * chairs + 4 * tables <= 100)     # carpentry hours
    solver.Add(1 * chairs + 2 * tables <= 40)      # painting hours

    # 4. Objective: maximise profit
    solver.Maximize(20 * chairs + 30 * tables)

    # 5. Solve
    status = solver.Solve()

    # 6. Report results
    if status == pywraplp.Solver.OPTIMAL:
        print("Status : OPTIMAL")
        print(f"Chairs : {chairs.solution_value():.0f}")
        print(f"Tables : {tables.solution_value():.0f}")
        print(f"Profit : SGD {solver.Objective().Value():.2f}")
    else:
        print("Solver ended with status", status)


if __name__ == "__main__":
    main()

Expected output

Status : OPTIMAL
Chairs : 20
Tables : 10
Profit : SGD 700.00

Conclusion

The example above only involved 2 integer variables, while we may have more 2 variables by adding more constraints to the solver.

Hope it helps, bye.