InteractiveMap of Operations Research
Back to Optimization Core
MethodIntermediate02.03
Optimization Core

Integer & Mixed-Integer Programming

Discrete decisions: yes/no, counts, assignments, logic.

Overview

Integer and mixed-integer programming model discrete choices: open a depot, assign a crew, select a project, start a machine, or include an arc in a route. The integrality is what makes the recommendation operationally executable.

MILP is especially useful when data is limited but business rules are well understood: experts can encode those rules directly as sets, parameters, variables, linear constraints, and an objective. The craft is formulation. A tight formulation, good bounds, and valid cuts can beat a weak model even when both describe the same business problem.

Core ideas

Binary variables

Represent yes/no structure such as facility opening, assignment, route activation, and logical implications.

Sets and parameters

Sets index repeated entities such as products, shelves, workers, tasks, or authors; parameters hold fixed inputs such as prices, sizes, capacities, availability, and visibility factors.

Branch & bound

Searches discrete choices while pruning regions whose bound cannot beat the incumbent solution.

Branch & cut

Adds valid inequalities during the search to tighten weak relaxations.

Branch & price

Branch & price is a core checkpoint for Integer & Mixed-Integer Programming: define it concretely, attach units or rules where possible, and test whether stakeholders interpret it the same way.

Formulation strength

A strong formulation closes the relaxation gap and can matter more than switching solvers.

Linearization

Linearization approximates or reformulates nonlinear relationships over a relevant interval so MILP tools can be used, usually trading exactness for tractability.

How to use it

  1. 1Start with the operational decision: write the entities, time horizon, objective, and business rules in plain language.
  2. 2Define sets, parameters, binary/integer/continuous variables, constraints, and objective before choosing a solver.
  3. 3Build a small instance in a modeling tool such as Pyomo and solve it with GLPK, GLOP, CP-SAT, SCIP, or another solver that matches the model.
  4. 4Compare the recommendation against a baseline policy, not just against mathematical optimality.
  5. 5Document assumptions, sensitivity results, and the conditions under which the recommendation should be revisited.

Applications

Facility locationProduct allocationVehicle routingCrew schedulingUnit commitmentCash flow optimization
  • Facility location: compare feasible policies, quantify the operating tradeoffs, and make the assumptions behind the recommendation visible.
  • Product allocation: assign products to shelves, bookcases, ads, slots, or displays while respecting capacity, fit, grouping, and revenue rules.
  • Vehicle routing: compare feasible policies, quantify the operating tradeoffs, and make the assumptions behind the recommendation visible.
  • Crew scheduling: compare feasible policies, quantify the operating tradeoffs, and make the assumptions behind the recommendation visible.
  • Unit commitment: compare feasible policies, quantify the operating tradeoffs, and make the assumptions behind the recommendation visible.
  • Cash flow optimization: choose financial instruments, timing, or allocations under capital, risk, and policy constraints.

Common pitfalls

  • Using MILP when the real rules are unknown and must first be learned from data.
  • Leaving business rules only in prose instead of translating them into auditable constraints.
  • Treating binary variables as a technical detail instead of a modeling choice that affects the recommendation.
  • Linearizing nonlinear behavior without checking whether the approximation is accurate enough over the operating range.
  • Reporting one answer without showing sensitivity to demand, capacity, costs, or behavioral assumptions.
  • Ignoring implementation details such as data quality, explainability, ownership, and how users will override bad recommendations.

Resources