Mixed Integer Programming: Solvers & Lab Guide

Short answer

Mixed integer programming is a mathematical optimization method that determines the optimal objective value subject to constraints where some decision variables are restricted to integer values while others remain continuous. By combining discrete choices with continuous quantities, mixed integer programming enables researchers and laboratory managers to rigorously model complex scheduling, sample batching, and resource allocation problems that cannot be solved by simple rounding.

Definition and scope

In applied mathematics and operations research, mathematical programming identifies an optimal resource allocation among competing activities. When all decision variables assume real values along a continuous continuum, problems are structured as continuous linear programs or convex models, often formulated in environments like CVXPY convex optimization modeling. In contrast, many laboratory and experimental decisions are discrete: facilities run an integer number of multi-well plates or assign a robotic arm to a specific assay station.

Mixed integer programming (MIP)—primarily applied as mixed-integer linear programming (MILP)—addresses optimization problems where objective functions and constraints are linear, but specified variables are constrained to integers. As documented in the SciPy reference manual for scipy.optimize.milp, a standard MILP minimizes a linear objective function subject to matrix inequalities and variable bounds:

minimize c^T x

subject to: b_l ≤ A x ≤ b_u and l ≤ x ≤ u, with x_i ∈ ℤ for all i in X_integer

Here, c is the objective vector, A is the linear constraint matrix, b_l and b_u represent constraint bounds, and l and u set lower and upper variable bounds. Solvers categorize the underlying types of variables into distinct mathematical domains:

• Continuous variables: Take real values within [l, u], representing physical quantities such as buffer volume, incubation duration, or temperature.
• Integer variables: Restricted to integer values (0, 1, 2, …), representing discrete units such as microplates, technician shifts, or instrument runs.
• Binary variables: Restricted to {0, 1}, modeling logical decisions, mutual exclusivity, or machine on/off states.
• Semi-continuous and semi-integer variables: Must take a value of zero or fall within designated bounds [l, u], modeling operating thresholds where instruments must stay idle or run above a minimum batch volume.

How it works or how it is used in practice

Because mixed integer programming problems are NP-hard, solvers cannot rely solely on standard simplex or interior point methods. Modern open-source solvers, such as HiGHS and COIN-OR Cbc (Coin-or branch and cut), resolve these models using branch-and-cut algorithms that integrate three mathematical techniques:

1. Linear Programming (LP) Relaxation: Dropping integrality constraints transforms the problem into a continuous LP, which solves rapidly via dual simplex to yield a valid lower bound on the optimal minimization objective.
2. Branch and Bound Tree Search: When relaxation yields fractional values for integer variables, the solver branches into subproblems (e.g., adding constraints x_i ≤ 2 and x_i ≥ 3). Nodes are pruned whenever their relaxed bound cannot beat the best known integer solution.
3. Cutting Plane Generation: Solvers dynamically add valid linear inequalities—cutting planes—that remove fractional regions without eliminating integer feasible points. Implementations from the COIN-OR Cut Generation Library (Cgl), such as Gomory cuts and knapsack cover cuts, tighten relaxations and accelerate convergence.

Convergence is evaluated via the relative MIP gap, |Primal Bound – Dual Bound| / |Primal Bound|. The solver terminates when the gap falls below a defined tolerance (such as 1e-4), guaranteeing near-global optimality.

Types or related concepts

Mixed integer programming spans several mathematical optimization problem classes:

Problem Class	Variables	Objective	Constraints	Primary Algorithm	Standard Solvers
Linear Programming (LP)	Continuous	Linear	Linear equalities / inequalities	Simplex, Interior Point	Clp, HiGHS, GLPK
Pure Integer Programming (IP)	Integer only	Linear	Linear equalities / inequalities	Branch-and-cut, cutting planes	HiGHS, Cbc, GLPK
Mixed-Integer Linear Programming (MILP)	Continuous and Integer	Linear	Linear equalities / inequalities	Branch-and-cut with Cgl cuts	HiGHS, Cbc, SCIP
Mixed-Integer Quadratic Programming (MIQP)	Continuous and Integer	Convex Quadratic	Linear equalities / inequalities	Branch-and-bound with QP relaxations	HiGHS, CPLEX, Gurobi
Mixed-Integer Nonlinear Programming (MINLP)	Continuous and Integer	Nonlinear	Nonlinear algebraic equations	Outer approximation, spatial branch-and-bound	Bonmin, Couenne, SCIP

In research workflows, Python developers formulate MILP models using scipy.optimize.milp or packages like PuLP and Pyomo. Advanced symbolic formulations are also managed within the broader SageMath computational mathematics platform.

Where it matters for labs, clinics or supply decisions

Mixed integer programming directly addresses laboratory workflow, clinical scheduling, and supply chain logistics:

• High-Throughput Assay Batching: Analytical facilities processing PCR or sequencing runs operate with fixed 96-well or 384-well plates and strict turnaround deadlines. MILP models assign incoming sample queues to batches, minimizing reagent waste while guaranteeing turnaround requirements.
• Robotic Liquid Handler Scheduling: Automated workstations execute multi-step protocols with shared deck positions and tip limits. Formulations optimize pipetting schedules and incubation dwell times to maximize throughput without resource clashes.
• Reagent and Consumable Inventory Control: Laboratories manage diagnostic cartridges and reagents subject to minimum order quantities, limited -80°C storage, and finite shelf-lives. Binary variables capture fixed reorder costs, while continuous variables track usage to avoid stockouts.
• Clinical Staff Rostering: Laboratories balance technician coverage across specialized testing benches under union shift rules and fluctuating sample arrivals. Formulations balance coverage while minimizing overtime.

Model coefficients and demand bounds are frequently calibrated via linear regression models and verified through cross-validation in statistical modeling to ensure robust performance under operational variance.

Common misunderstandings

Operational teams and computational researchers frequently encounter three major misunderstandings:

• Misunderstanding 1: Rounding continuous LP solutions produces the optimal integer solution. Rounding fractional values often creates infeasible solutions that breach critical laboratory capacity limits, or yields solutions far from the true mathematical optimum. Rigorous branch-and-cut exploration is essential.
• Misunderstanding 2: Solution time depends solely on variable count. Solve times depend primarily on formulation tightness. A weak formulation with 1,000 variables can stall indefinitely, while a tight formulation with 50,000 variables solves within seconds.
• Misunderstanding 3: Integer variables only represent physical counts. Binary variables routinely model logical switches, precedence orderings, equipment activation states, and mutually exclusive protocol branches.

Frequently asked questions

What is the difference between LP, IP, and MIP?

Linear programming (LP) restricts all variables to continuous real numbers. Pure integer programming (IP) requires every variable to take integer values. Mixed integer programming (MIP) incorporates both, allowing some variables to be continuous while restricting others to discrete integers or binary flags.

How does a branch-and-cut solver determine when to stop?

The solver tracks the primal bound (best integer solution found) and dual bound (best possible objective across unexplored nodes). It stops when the relative MIP gap between these bounds drops below the target tolerance, when a time limit is reached, or when the search tree is completely explored.

Which open-source Python libraries support mixed integer programming?

SciPy includes native MILP solving through scipy.optimize.milp backed by HiGHS. PuLP and Pyomo provide algebraic modeling layers that interface with HiGHS, COIN-OR Cbc, and GLPK solvers.

Sources

• SciPy Documentation — scipy.optimize.milp Reference Manual (https://docs.scipy.org/doc/scipy/reference/generated/scipy.optimize.milp.html), read 2026-11-12.
• COIN-OR Foundation — Computational Infrastructure for Operations Research Projects Directory (https://www.coin-or.org/projects/), read 2026-11-12.
• HiGHS Solver Project — High-performance serial and parallel linear optimization software documentation (https://highs.dev/), read 2026-11-12.