Integer programming

Integer programming is a branch of mathematical optimization in which some or all decision variables must take integer values. It represents indivisible quantities and discrete choices, such as how many machines to install or whether to open a facility. The most widely studied form, integer linear programming, combines these restrictions with a linear objective function and linear constraints. Here, “programming” means constructing and solving an optimization model, rather than writing computer code. (web.mit.edu)

Mathematical formulation and variants

A mixed-integer linear program can be written as

Here $A$ is a coefficient matrix, $b$ contains constraint bounds, $c$ contains objective coefficients, and $I$ identifies the integer-constrained variables. Variables outside $I$ may take real values. Equalities, lower-bound inequalities, and maximization objectives are also possible. The feasible set consists of all assignments satisfying both the algebraic constraints and the variable-domain restrictions. (gurobi.com)

In a pure integer program, every decision variable is integer-constrained. A mixed-integer program combines integer and continuous variables. A binary integer program restricts its variables to $0$ or $1$, making them suitable for yes-or-no decisions. Integer programming also includes nonlinear models; integrality alone does not imply linearity. Quadratic objectives and constraints define important intermediate classes between linear and general nonlinear models. (web.mit.edu)

Modeling discrete decisions

Binary variables translate many rules from logic into linear constraints. If $y_A$ and $y_B$ indicate whether two actions occur, $y_A\leq y_B$ expresses “action A requires action B.” The inequality $y_A+y_B\leq1$ prohibits choosing both, while $\sum_j y_j=1$ requires exactly one choice from a collection. These constructions connect integer models with Boolean algebra. (docs.mosek.com)

A standard knapsack problem chooses items with values $v_j$ and weights $w_j$ under capacity $W$:

Related formulations describe project selection and capital budgeting, potentially with several resource constraints. Binary choices can also be linked to continuous activity levels: $0\leq q\leq My$ permits positive production $q$ only when $y=1$. This is a big-M formulation, where $M$ must be a valid upper bound. Such models represent fixed setup costs and facility-opening decisions. (web.mit.edu)

Relaxation and geometry

Removing integrality restrictions produces a linear-programming relaxation, solvable by methods for linear programming. Its feasible region contains every feasible integer solution. Therefore, for minimization, its optimal value is a lower bound on the integer optimum; for maximization, it is an upper bound. If an optimal relaxed solution already satisfies integrality, it also solves the original problem. Simply rounding a fractional solution need not preserve feasibility or optimality. (gurobi.com)

For example, maximize $x+y$ subject to $2x+2y\leq3$ and nonnegative integer $x,y$. The relaxation attains $1.5$, whereas the integer optimum is $1$. Rounding the relaxed optimum $(0.75,0.75)$ coordinatewise to $(1,1)$ violates the constraint.

Geometrically, linear inequalities define a convex polyhedron, while integrality selects lattice points within it. Their convex hull is the ideal linear relaxation: optimizing a linear objective over it gives the integer optimal value whenever an optimum exists. Describing that hull explicitly, however, can require many inequalities. (arxiv.org)

Solution methods

Branch-and-bound systematically divides the problem into subproblems. If an integer variable has relaxed value $3.6$, branching creates cases $x_j\leq3$ and $x_j\geq4$, excluding the fractional value without losing integer possibilities. A subproblem is discarded when it is infeasible, its bound cannot improve the best known feasible solution, or its relaxation yields an integer optimum. This avoids explicitly enumerating every candidate assignment. (gurobi.com)

The cutting-plane method adds inequalities valid for integer solutions but violated by selected fractional solutions. Combining cuts with branching gives branch-and-cut, a central framework in integer optimization. Solvers also use preprocessing and heuristics: preprocessing simplifies the model, while heuristics seek feasible solutions that improve the incumbent and strengthen pruning. (arxiv.org)

For minimization, an incumbent supplies an upper bound $U$, while the search supplies a lower bound $L$. The optimality gap measures their separation. Equality certifies optimality in exact arithmetic; practical termination may instead use specified absolute or relative tolerances. A feasible solution alone is not an optimality certificate. (gurobi.com)

Complexity and formulation quality

Within computational complexity, general integer linear optimization is NP-hard. This worst-case classification does not mean every instance is difficult: practical performance depends strongly on structure and formulation. (csc.kth.se)

Some structured models have integral linear relaxations. In particular, if $A$ is totally unimodular and $b$ is integral, every vertex of $\{x:Ax\leq b,\ x\geq0\}$ is integral. When an optimal vertex exists, linear programming can therefore solve the associated integer problem directly. (arxiv.org)

Equivalent integer formulations can have different relaxation strengths and computational behavior. Tight bounds, informative valid inequalities, and reduced symmetry can improve the search. Excessively large big-M constants can weaken bounds and cause numerical difficulties, even though they leave the intended integer choices unchanged. (docs.mosek.com)

References

1. Integer Programming, Chapter 9 of Applied Mathematical Programmingweb.mit.edu
2. Mixed-Integer Programming: An Intro to the Basicsgurobi.com
3. A Directed Augmentation Algorithm for Integer Programmingweb.mit.edu
4. 9 Mixed integer optimization — MOSEK Modeling Cookbookdocs.mosek.com
5. Finding total unimodularity in optimization problems solved by linear programsarxiv.org
6. Structural Analysis of Branch-and-Cut and the Learnability of Gomory Mixed Integer Cutsarxiv.org
7. What Is MILP? Solver & Uses Explainedgurobi.com
8. Notes for the course advanced algorithmscsc.kth.se
9. 4 The Optimizer for Mixed-Integer Problems — MOSEK Command Line Toolsdocs.mosek.com