Skip to content
Tutorials Center
My learning

Topics

Lesson 19 of 38 ยท Integer Programming

Integer Programming Basics

Learn what integer and mixed-integer linear programs are, why rounding an LP solution fails, what the LP relaxation bound means, and how to solve a MILP with SciPy.

Linear programming lets variables take any real value. Real decisions are often not like that: you cannot build 2.7 factories, hire 3.4 drivers or schedule half a flight. When some or all variables must be whole numbers, you have an integer program. This looks like a small change, but it turns an easy problem (solvable in polynomial time) into one that is NP-hard in general.

In this chapter you will learn how integer programs are formulated, solved and tightened. This first lesson explains the vocabulary, shows why simple rounding is a trap, and solves your first model with SciPy's milp.

Kinds of integer programs

A mixed-integer linear program (MILP) has the form:

TEXT
minimize    cยทx
subject to  A x โ‰ค b
            x โ‰ฅ 0
            x_j integer for j in J
  • If every variable is integer, it is a pure integer program (ILP).
  • If only some are, it is a mixed-integer program (MIP/MILP).
  • If every variable is restricted to 0 or 1, it is a binary (0-1) program. Binary variables model yes/no decisions; see Binary Variables and Logic.

The problem you get by dropping the integrality requirements is the LP relaxation. It is easy to solve, and it tells you a lot.

Why rounding fails

A tempting plan is: solve the LP, then round each variable to the nearest integer. Try it on a small production problem. Maximize profit 5x + 4y where x and y are numbers of two products, subject to 6x + 4y โ‰ค 24 (machine time) and x + 2y โ‰ค 6 (labor).

Python LP optimum versus rounding

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The LP optimum is x = 3, y = 1.5 with profit 21. Rounding y up gives (3, 2), which breaks the labor constraint. Rounding down gives (3, 1), which is feasible but worth only 19. Is there something better? Yes, and it is far from the LP point.

Python The true integer optimum via milp

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The integer optimum is (4, 0) with profit 20. It is not a neighbor of the LP solution at all. Rounding is not just inexact: it can be infeasible, suboptimal, or both. This is why we need real integer-programming algorithms.

Never round an LP solution and call it optimal. With large integers (hundreds of units) rounding error is tiny in relative terms, but with small counts, binary decisions or tight constraints it can be badly wrong.

The picture

The feasible region of the LP is a polygon. The feasible region of the ILP is only the integer lattice points inside it. The optimum of the ILP lies at one of those points, not necessarily at a vertex of the polygon.

flowchart LR
    A["LP relaxation<br/>(drop integrality)"] -->|"solve fast"| B["Upper bound 21<br/>for a max problem"]
    C["Feasible integer points"] -->|"best one found"| D["Lower bound 20"]
    B --> E["Gap = 21 - 20"]
    D --> E

The relaxation gives an optimistic bound, any integer solution gives a pessimistic one, and the algorithms of this chapter close the gap between them.

Bounds and the optimality gap

Because the relaxation has more freedom, its optimum is never worse than the integer optimum:

  • For a maximization problem, LP value โ‰ฅ ILP value (an upper bound).
  • For a minimization problem, LP value โ‰ค ILP value (a lower bound).

Any feasible integer point gives the opposite bound (the incumbent). The relative gap |bound - incumbent| / |incumbent| is how solvers report progress, and a gap of 0 proves optimality. Here the gap was (21 - 20)/20 = 5%.

When the LP optimum happens to be integer, you are done immediately. This happens automatically for network problems (see Network Flow Models), because their constraint matrices are totally unimodular.

Modeling mixed problems

Mixed-integer models are everywhere because only some quantities are discrete. A plant either opens (binary) or not, and then ships any amount (continuous). In milp, the integrality array has one entry per variable: 0 continuous, 1 integer. Binary variables are integer variables with bounds [0, 1].

Python A mixed model: how many trucks, and how much cargo

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The solver buys 4 trucks (capacity 32 t) and moves 3 tonnes by hand for 540. A fifth truck would cost 120 to save only 3 tonnes of handling (60), and using no trucks at all would cost 700.

Strengths and limits

  • Integer models can express things LP cannot: counts, yes/no choices, logical rules, fixed costs, and either-or constraints.
  • The price is computing time. Doubling a model's size can multiply solve time by far more than two.
  • Good formulations matter more than good solvers; Cutting Planes and Formulation Strength explains why.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What is the LP relaxation of an integer program?

    The relaxation keeps all linear constraints but lets integer variables take any real value, so it is a normal LP.
  2. 2. For a maximization ILP, how does the LP relaxation optimum compare with the ILP optimum?

    The relaxation has a larger feasible set, so its best value can only be as good or better; it is an upper bound when maximizing.
  3. 3. Why is rounding the LP solution unreliable?

    In the example, rounding up broke a constraint and rounding down lost profit; the best integer point was somewhere else entirely.
  4. 4. In scipy.optimize.milp, what does integrality=[1, 0, 0] mean?

    Each entry flags one variable: 1 means integer, 0 means continuous.

Summary

  • Integer programs require some or all variables to be whole numbers; pure, mixed and binary variants exist.
  • The LP relaxation drops integrality and gives a bound: upper for maximize, lower for minimize.
  • Rounding an LP solution can be infeasible or suboptimal, so real ILP methods are needed.
  • The gap between the relaxation bound and the best integer solution measures how close you are to proof of optimality.
  • scipy.optimize.milp solves small and medium MILPs with integrality, bounds and LinearConstraint.

Next: Binary Variables and Logic