Mixed-Integer Programming
- Also called: MIP, MILP, MIQP, MICP
- Category: Planning & manipulation › Trajectory optimisation
- Tags: optimization, integer-programming, motion-planning, task-allocation, hybrid-systems
Optimization in which some variables must take integer values, often 0 or 1, letting one problem combine discrete choices with continuous quantities.
Definition
Mixed-integer programming (MIP) is optimization over a mix of continuous variables and variables restricted to integers, most often binary variables that take the value 0 or 1. The binary variables encode discrete decisions: which region a path passes through, which foot touches down next, whether a contact is active, which robot takes which task. The continuous variables carry the rest, such as positions, velocities and forces. Common classes are named by the form of the remaining problem: mixed-integer linear programs (MILP), mixed-integer quadratic programs (MIQP) and, more generally, mixed-integer convex programs (MICP).
These problems are NP-hard in general, but modern solvers handle many practical instances well. They use branch and bound: solve the continuous relaxation with the integer requirements dropped, pick a variable that came out fractional, split into two subproblems that force it down or up, and prune any branch whose relaxation is already worse than the best integer solution found. Cutting planes tighten the relaxation along the way. Commercial solvers such as Gurobi and CPLEX and open-source ones such as SCIP, HiGHS and CBC implement these methods.
How a problem is written matters as much as which solver is used. Logical conditions are often encoded with big-M constraints, which switch a constraint on or off with a binary variable and a large constant; too large a constant weakens the relaxation and causes numerical trouble. Formulations with tight relaxations solve much faster, which is one reason structured approaches such as graphs of convex sets are designed so that their relaxation is close to the true problem.
Why it matters
Many robot planning problems are partly discrete: going left or right of an obstacle, choosing a contact sequence, assigning tasks. Mixed-integer programming handles these choices exactly within one optimization, often with a bound on how far the answer is from optimal, instead of relying on hand-made heuristics or sampling.
Key applications
- Footstep and contact sequence planning for legged robots
- Trajectory planning through convex regions for drones and arms
- Task assignment and scheduling for robot fleets
- Hybrid model predictive control with discrete modes
- Task and motion planning with discrete action choices
In practice
A team planning footsteps for a humanoid across stepping stones represents each stone's walkable surface as a convex polygon. For each of the next steps, they add binary variables that select which polygon the foot lands on, with constraints that are only active for the chosen polygon, plus continuous variables for the foot positions and limits on step length and turning. The cost rewards progress toward the goal and penalizes awkward steps. A mixed-integer solver returns a step sequence, usually within a time limit set for replanning, along with the gap between the best solution found and the best bound. If solve times are too long, the team reduces the number of steps planned at once, tightens big-M values or warm-starts from the previous plan.
Common misconceptions
- Mixed-integer programs are always too slow for robotics — small, well-formulated problems can solve fast enough for online replanning
- Rounding the continuous relaxation gives the optimal integer solution — rounding can be infeasible or far from optimal unless the relaxation is tight
- Any large value of M works in big-M constraints — overly large values weaken the relaxation and cause numerical difficulties
- A solver that stops at its time limit has failed — it usually returns the best solution so far and an optimality gap that says how good it is
Who should know this
- Motion and footstep planning engineers
- Fleet scheduling and task allocation developers
- Researchers in optimization-based control
- Robotics students studying optimization
Related technologies
- Branch and Bound
- Gurobi
- SCIP
- HiGHS
- Linear Programming
- Convex Optimization
Related terms
- Graph of Convex Sets
- Task and Motion Planning
- Model Predictive Control
- Motion Planning
- Trajectory Planning
- Multi-Agent Path Finding
Related projects
- Drake: MIT robotics toolbox for model-based dynamics, optimization, and control system design
- GTSAM: Factor-graph optimization library powering many modern SLAM backends
- OMPL: Sampling-based motion planning library powering MoveIt and countless robotics applications
- MoveIt 2: Motion planning framework for ROS 2 robot arms, with kinematics and collision checking
- PyRoki: Modular Python toolkit for kinematic optimization across CPU, GPU, and TPU via JAX
- PyPose: PyTorch library for differentiable robotics with deep learning and Lie group optimization
Videos
- Mixed Integer Linear Programming (MILP) Tutorial: APMonitor.com