Must all variables be integers?

No. A mixed model can combine integer and continuous variables; all-integer formulations are also supported by MILP methods.

Is MILP itself a learning model?

No. It is an optimization framework that can use inputs produced by learning models.

Does a returned solution prove optimality?

Not automatically. Check feasibility, termination status, and the solver's bound or gap.

AI Glossary / Mathematics and optimization / Intermediate

Mixed integer linear programming

Definition

Mixed integer linear programming, usually abbreviated MILP, is an optimization framework with a linear objective, linear constraints, and integer restrictions on some decision variables. Other variables may be continuous. It can represent decisions that combine indivisible choices, such as opening a facility, with quantities that can vary continuously, such as the amount shipped.

What it means

“Programming” here means mathematical planning, rather than writing application code. “Linear” means that the objective and constraints combine variables with fixed coefficients; multiplying two decision variables is not linear. “Integer” means a variable must take whole-number values within its bounds.

A binary variable is an integer variable restricted to zero or one. It can represent an option being selected or rejected. Problems in which all variables are integer are an important special case handled by MILP methods. The practical value is that operational choices can be expressed explicitly rather than approximated by fractional decisions that cannot be implemented.

How it works

Define the decisions, an objective to minimize or maximize, resource constraints, and variable bounds. Specify exactly which variables are integer. For example, a production quantity q and a binary activation decision z can be linked by 0≤q≤Cz, where C is a valid capacity. If z=0, production must be zero.

Solvers commonly use relaxations that temporarily allow fractional values for integer variables, together with branching and additional valid constraints. A relaxation gives information about how good the original problem's optimum could be. Feasible integer solutions provide implementable candidates.

Inspect the termination status and reported bound or optimality gap. A time-limited run may find a useful feasible solution without proving it best. An infeasible model has no solution satisfying all its stated requirements; an unbounded model permits unlimited improvement. Neither status should be reported as an ordinary recommended plan.

Three practical examples

1. Facility planning: binary choices decide which depots open, while continuous variables assign shipment quantities subject to demand and capacity.

2. Staff scheduling: integer or binary assignments specify who covers a shift. Linear constraints enforce coverage and explicit availability rules.

3. AI operations: a planner chooses whole accelerator instances while allocating divisible workloads among them, using a linear approximation of costs and capacities. Whether that approximation is adequate requires separate validation.

Think of it this way

Think of planning a delivery with whole trucks and divisible cargo. You can load 2.4 tonnes, but hiring 0.3 of an indivisible truck may not be an available choice.

The analogy explains why some variables need whole-number restrictions while others do not. It does not make every transport model linear: congestion, nonlinear fuel consumption, or uncertain arrival times may require different formulations or explicit approximations.

Worked example

A fictional workshop must supply 7 units. It can activate an internal machine, z∈{0,1}, producing a continuous quantity q between 0 and 10z. It can also purchase a continuous quantity y≥0 from an external supplier. Require q+y≥7 and minimize cost 8z+2q+5y.

If z=0, q must be zero, so buying y=7 costs 35. If z=1, internal units are cheaper than purchased units, and capacity covers demand. Choose q=7 and y=0, costing 8+14=22. Producing excess units only adds cost. The integer optimum is therefore z=1, q=7, y=0, with cost 22.

Relax z to the interval [0,1]. Then q=7 and z=0.7 satisfy q≤10z, at cost 5.6+14=19.6. This is the relaxation optimum: effective internal unit cost is 2.8, below the supplier's 5. The lower cost is not implementable because fractional activation is forbidden. Rounding z down to zero while retaining q=7 breaks the capacity link. The example is checked by cases, not presented as a solver execution.

Illustrative case study

Fictional case study: a repair network uses a demand forecast to plan next week's service capacity. An initial continuous model recommends fractional staffing assignments that managers cannot implement. The team adds binary shift choices and linear coverage constraints, while retaining continuous quantities for consumable materials.

Managers inspect a proposed schedule and discover that a training requirement was omitted. They add it and solve the revised model. This illustrates a boundary of optimization: a mathematically optimal answer only satisfies the requirements actually represented in the model. Forecast accuracy and operational completeness remain separate responsibilities.

Common misconceptions and mistakes

Do not assume that rounding a continuous solution produces the integer optimum. Rounding can violate constraints or create a feasible but unnecessarily expensive plan.

Do not interpret “linear” as “easy at every size.” Integer choices can create a demanding combinatorial search.

Do not use an arbitrarily enormous capacity constant in a linking constraint when a tighter valid bound is available. Loose formulations can weaken relaxations and complicate numerical behavior. Conversely, an unjustifiably small bound can remove legitimate choices.

Business use

MILP can turn predictions into operational decisions: a demand estimate becomes an input to a capacity or allocation model. Keep that connection visible, because an optimal schedule for an inaccurate demand assumption may still disappoint.

Record the objective units, input assumptions, feasibility checks, runtime limit, and any remaining gap. Compare the recommendation with a practical baseline and test alternative demand scenarios. Users need to know both what decision was selected and which constraints made it preferable.

Check your understanding

Why is the workshop's relaxed cost of 19.6 not an implementable alternative to 22?

Answer: It depends on z=0.7, but the machine activation variable must be either zero or one. The relaxation removes a real decision restriction.

Related terms

Linear programming
Binary variable
Constraint satisfaction
integer programming
feasible region
branch and bound
relaxation
optimality gap

Learn next

change the workshop's activation cost and identify when outsourcing becomes cheaper. Then compare feasible integer solutions with relaxation bounds and study how tighter capacity information changes a formulation.

Sources

Sources: SciPy, Optimization tutorial, mixed integer linear programming: https://docs.scipy.org/doc/scipy/tutorial/optimize.html#mixed-integer-linear-programming ; SciPy, milp reference: https://docs.scipy.org/doc/scipy/reference/generated/scipy.optimize.milp.html . Primary formulation, variable restrictions, termination information, and rounding caveat were read. The workshop problem and case study are original illustrations, not measured business results.

Previous: Mixed-data sampling Next: Mixed methods