Fact-checked by Grok 2 weeks ago

Integer programming

Integer programming is a mathematical optimization paradigm in which some or all decision variables are constrained to take integer values, typically to model discrete choices such as selecting whole units or binary decisions.^[1]^[2] In the predominant case of integer linear programming, the objective function to maximize or minimize is linear, as are the equality and inequality constraints defining the feasible region.^[3]^[4] The integrality requirement introduces combinatorial complexity, rendering general integer programs NP-hard and computationally intractable for large instances without approximation or heuristics, in contrast to the polynomial-time solvability of their linear programming relaxations obtained by ignoring integrality.^[5]^[4] Solution approaches rely on techniques such as branch-and-bound enumeration of integer subproblems, cutting-plane methods to tighten relaxations by adding valid inequalities, and polyhedral analysis to exploit problem structure via facet-defining inequalities.^[6] Pioneered by Ralph Gomory's fractional cutting planes in 1958, these methods have evolved with computational advances, enabling commercial solvers to handle problems with millions of variables and constraints in applications like supply chain optimization and network design.^[7]^[8] Integer programming models arise in diverse fields, including production planning, where variables represent indivisible batch sizes; vehicle routing, capturing depot selections; and capital budgeting, enforcing all-or-nothing project investments.^[9]^[10] Mixed-integer variants allow continuous variables alongside integers, broadening applicability to hybrid systems like blending processes with setup decisions, while pure integer forms suit purely discrete scenarios such as graph coloring or set covering.^[11] Despite theoretical intractability, empirical progress in presolving, symmetry detection, and machine learning-augmented heuristics has dramatically expanded solvable problem scales since the 1970s advent of practical branch-and-cut frameworks.^[12]^[13]

Definition and Formulation

Mathematical Foundations

Integer programming encompasses optimization problems where decision variables are restricted to integer values, distinguishing it from continuous linear programming by the requirement that solutions lie at lattice points within the feasible region defined by linear constraints.^[6] The core mathematical structure involves a linear objective function maximized or minimized subject to linear inequalities and non-negativity conditions, with the integrality constraint applied to all or a subset of variables.^[14] In pure integer programming, every variable x \in \mathbb{Z}^n must be integer; in mixed-integer programming, only specified variables carry this restriction, allowing continuous variables for the remainder.^[15] The standard formulation of an integer linear program is to solve \max \mathbf{c}^T \mathbf{x} subject to A \mathbf{x} \leq \mathbf{b}, \mathbf{x} \geq \mathbf{0}, and \mathbf{x} \in \mathbb{Z}^n, where \mathbf{c} \in \mathbb{R}^n is the objective coefficient vector, \mathbf{b} \in \mathbb{R}^m the right-hand side vector, and A \in \mathbb{R}^{m \times n} the constraint matrix.^[16] This model generalizes to equality constraints via slack variables, transforming A \mathbf{x} + \mathbf{s} = \mathbf{b}, \mathbf{s} \geq \mathbf{0}, preserving the linear structure.^[6] The feasible set consists of integer points inside the polyhedron defined by the linear programming (LP) relaxation, where integrality is ignored; optimal IP solutions coincide with extreme points of the convex hull of these integer points, though computing this hull directly is computationally intensive.^[17] Binary integer programming, a special case, restricts variables to \{0,1\}, enabling modeling of discrete choices such as selection or assignment in combinatorial problems.^[18] General integer variables can be represented via binary expansion for bounded cases, decomposing x into \lfloor \log_2 U \rfloor + 1 binary variables weighted by powers of 2, where U is an upper bound, thus reducing to binary form at the cost of increased dimensionality.^[14] These formulations underpin the theoretical analysis of integer programs, revealing their inherent discreteness and non-convexity compared to LPs, which admit polynomial-time solvability via interior-point or simplex methods.^[16]

Canonical and Standard Forms

The canonical form of an integer linear program expresses the optimization problem as maximizing a linear objective function subject to linear inequality constraints and non-negativity requirements on the decision variables, which are restricted to integers.^[11] Here, the decision vector \\mathbf{x} \\in \\mathbb{Z}^n, the objective coefficients form \\mathbf{c} \\in \\mathbb{R}^n, the right-hand side vector is \\mathbf{b} \\in \\mathbb{R}^m, and the constraint matrix is A \\in \\mathbb{R}^{m \\times n}. This formulation privileges inequality constraints for broad applicability in modeling resource limits or upper bounds.^[11] The standard form converts the canonical inequalities into equalities by introducing non-negative slack variables \\mathbf{s} \\in \\mathbb{R}^m_{\\geq 0}, yielding A \\mathbf{x} + \\mathbf{s} = \\mathbf{b} alongside the non-negativity and integrality on \\mathbf{x}.^[6] This transformation aligns integer programs with linear programming standards, enabling direct application of relaxation techniques like the simplex method for bounding in branch-and-bound algorithms.^[19] Both forms assume maximization without loss of generality, as minimization converts via negating the objective, and unrestricted variables can be split into positive and negative components.^[11]

Illustrative Examples

A basic example of integer programming involves optimizing over lattice points within a polyhedral feasible region. Consider maximizing y subject to -x + y \leq 1, $3x + 2y \leq 12, $2x + 3y \leq 12, and x, y \geq 0 integers.^[4] The integer-optimal solutions are at (1,2) and (2,2), both with objective value 2.^[6] Relaxing to continuous variables yields an optimum near (1.8, 2.8) with value 2.8, illustrating the gap between integer and linear programming solutions due to integrality constraints.^[4] The 0-1 knapsack problem provides another fundamental illustration: maximize \sum p_j x_j subject to \sum w_j x_j \leq W and x_j \in \{0,1\} for items with profits p_j and weights w_j, where W is capacity.^[18] This models selecting non-divisible items to maximize value without exceeding weight, a canonical pure integer program with one inequality constraint.^[18] Combinatorial problems like minimum vertex cover demonstrate mixed-integer formulations. For graph G = (V, E), minimize \sum_{v \in V} y_v subject to y_u + y_v \geq 1 for all edges \{u,v\} \in E and y_v \in \{0,1\}, where y_v = 1 if vertex v is selected.^[20] This ensures every edge is incident to at least one selected vertex, capturing NP-hard covering structures solvable via integer programming.^[20]

Historical Development

Origins in Linear Programming (1940s-1960s)

Linear programming emerged in the late 1940s as a method for optimizing continuous variables subject to linear constraints, with George Dantzig developing the simplex algorithm in 1947 to solve such problems efficiently.^[21] This framework was initially applied to resource allocation in military logistics during and after World War II, where decision variables often represented indivisible quantities like units of equipment or personnel, necessitating integer values.^[22] Practitioners quickly recognized that standard linear programming relaxations—treating integer constraints as continuous—frequently yielded non-integer solutions suboptimal for real-world discrete applications, prompting the need for specialized integer programming techniques.^[23] In the early 1950s, initial approaches to integer programming involved relaxing problems to linear programs and manually enumerating or adjusting solutions to enforce integrality, often combined with bounding strategies.^[24] A seminal early application occurred in 1954 when Dantzig, Fulkerson, and Johnson tackled the traveling salesman problem, employing linear programming relaxations to generate lower bounds and systematically enumerating subtours to find optimal integer solutions, effectively pioneering decomposition and bounding ideas for combinatorial integer programs.^[24] These efforts highlighted the computational challenges of integrality, as linear programming polyhedra often contained fractional vertices distant from integer points, requiring methods to tighten relaxations or search discrete feasible regions.^[25] The late 1950s marked algorithmic breakthroughs, with Ralph Gomory developing the first cutting-plane method in 1958 while at the RAND Corporation, introducing fractional cuts derived from simplex tableaux to eliminate non-integer solutions and prove convergence to integer optima for pure integer programs.^[21] Independently, A.H. Land and A.G. Doig formalized the branch-and-bound algorithm in 1960, partitioning the feasible region into subproblems with added constraints on variables to prune non-optimal branches using linear programming bounds.^[26] These innovations, building directly on linear programming infrastructure, established integer programming as a distinct yet intertwined field, enabling systematic solution of small-to-medium discrete optimization problems despite their inherent combinatorial explosion.^[27] By the mid-1960s, implementations of these methods on early computers demonstrated practical viability for specific applications, though general scalability remained limited.^[25]

Key Algorithmic Breakthroughs (1970s-1990s)

In 1973, Vašek Chvátal formalized the Chvátal-Gomory cutting plane procedure, which generates valid inequalities for the integer hull by rounding coefficients of linear programming relaxations while preserving feasibility for integer solutions; this method iteratively tightens bounds by deriving cuts such as cx \leq d from inequalities Ax \leq b where c is integral and d = \lfloor c^T b / \|c\|_1 \rfloor, offering a finite convergence guarantee under certain conditions despite potential numerical instability in practice.^[28] These cuts advanced beyond earlier Gomory fractional cuts by emphasizing polyhedral closure and integrality proofs, influencing subsequent separation oracles and facet-defining inequalities in combinatorial optimization.^[29] The 1980s saw a theoretical milestone with Hendrik W. Lenstra Jr.'s 1983 algorithm, which solves integer linear programs in polynomial time when the number of variables n is fixed, achieving runtime $2^{O(n^3)} \cdot poly(m, \log B) where m is constraints and B bound sizes; it relies on a flatness theorem for lattices and recursive decomposition into lower-dimensional subproblems via basis reduction.^[30] This breakthrough resolved a long-standing question on fixed-parameter tractability, though impractical for large n due to exponential dependence, it spurred research in approximation and heuristic extensions for variable dimensions.^[31] By the early 1990s, branch-and-cut frameworks integrated branch-and-bound with dynamic cutting plane generation, culminating in Manfred Padberg and Giovanni Rinaldi's 1991 algorithm for the symmetric traveling salesman problem, which solved instances up to 532 cities to optimality by iteratively adding problem-specific facets like comb inequalities within LP relaxations at nodes.^[32] This hybrid approach, leveraging separation routines and stabilization techniques, dramatically expanded solvable problem sizes—e.g., from dozens to hundreds of variables—paving the way for commercial solvers and demonstrating empirical efficacy on structured mixed-integer programs despite worst-case hardness.^[33]

Computational Maturation (2000s-Present)

The period from the 2000s onward marked a phase of computational maturation in integer programming, characterized by exponential gains in solver efficiency that transformed it from a niche academic tool into a cornerstone of industrial optimization. Refinements to branch-and-cut algorithms, including stronger cutting planes such as mixed-integer rounding (MIR) cuts and enhanced Gomory cuts, alongside advanced presolving techniques that reduce problem size by detecting redundancies and tightening bounds, enabled solvers to tackle instances with thousands of variables and constraints previously deemed intractable.^[8] Heuristic methods for rapid feasible solution generation, such as local branching and relaxation-induced neighborhood search, further accelerated practical deployment by providing high-quality incumbents early in the search process.^[8] Commercial solvers drove much of this progress, with IBM's CPLEX undergoing iterative enhancements in barrier methods for linear programming relaxations and parallel branch-and-bound exploration, while Gurobi Optimization, founded in 2008 by former CPLEX developers Robert Bixby, Zonghao Gu, and Edward Rothberg, introduced innovations like concurrent optimization across multiple threads and adaptive tuning for cut selection.^[34] ^[35] Open-source alternatives, notably SCIP (Solving Constraint Integer Programs), initiated around 2002 as a framework for mixed-integer nonlinear programming extensible to linear cases, contributed through modular plugin architectures that facilitated community-driven improvements in constraint handling and decomposition strategies like Dantzig-Wolfe and Benders methods.^[36] ^[8] These developments were complemented by hardware advances, including multi-core processors, which solvers exploited via parallelism in node exploration and cut separation. Benchmark evaluations underscore the scale of improvement: on MIPLIB 2017 instances, 2020-era solvers resolved 149 of 240 mixed-integer linear problems within 24 hours (geometric mean solve time of 104 seconds), whereas 2001 solvers failed all such cases; algorithmic speedups alone reached approximately 50-fold for overlapping solvable instances, with total effective gains (including hardware) nearing 1,000-fold.^[35] Broader analyses indicate solver software for mixed-integer programming accelerated by roughly 5 million times from 1989 to 2024, with CPLEX achieving 30,000-fold gains from 1991 to 2008 and Gurobi adding 178-fold from 2009 to 2023, outpacing hardware improvements by orders of magnitude.^[37] This maturation has causal implications for real-world applications, as evidenced by routine solving of logistics, energy scheduling, and finance models at scales unimaginable two decades prior, though persistent challenges remain in highly combinatorial structures requiring custom extensions.^[8]

Computational Complexity

Theoretical Hardness Results

The decision problem for integer programming—determining whether there exists an integer vector \mathbf{x} satisfying A\mathbf{x} \leq \mathbf{b} with \mathbf{x} \geq \mathbf{0}—is NP-complete.^[38] This result holds even for the special case of 0-1 integer programming, where variables are restricted to \{0,1\}, via a polynomial-time reduction from 3-SAT that encodes clauses as linear inequalities enforcing satisfiability constraints.^[39] Similarly, reductions from SAT construct general integer programs by representing boolean variables and clause implications through inequalities with small integer coefficients, preserving the input size.^[40] Integer programming is strongly NP-hard, meaning the NP-hardness persists even when all data (coefficients in A and \mathbf{b}) have constant bit length, independent of the problem size; this rules out pseudo-polynomial algorithms unless P=NP, unlike weakly NP-hard problems such as the knapsack problem.^[41] For instance, the vertex cover problem reduces to integer programming with unit coefficients, yielding hardness without reliance on large numbers.^[42] A notable exception occurs when the number of variables n is fixed: Lenstra's 1983 algorithm solves integer programming feasibility in polynomial time for constant n, using lattice basis reduction to enumerate relevant regions, with time complexity $2^{O(n^3)} \cdot \text{poly}(m, \log(\max|b_i|)) where m is the number of constraints.^[43] For optimization, the same approach extends by binary search over the objective value. However, the exponent grows rapidly with n, rendering it impractical beyond small fixed dimensions, and the general variable-n case remains intractable.^[44]

Empirical Performance and Scalability

Modern mixed-integer programming (MIP) solvers demonstrate strong empirical performance on benchmark instances, routinely achieving optimality or near-optimality within seconds to hours on contemporary hardware. The MIPLIB 2017 collection, comprising 1,065 instances with a curated benchmark subset of 240, serves as a primary standard for evaluating solver efficacy, where commercial tools like Gurobi and CPLEX solve the majority of cases efficiently due to advanced branch-and-cut implementations. ^[45] ^[46] Open-source alternatives such as SCIP also perform competitively on these sets, particularly for mixed-integer nonlinear extensions, though they lag behind commercials in aggregate speed. ^[36] Comparative benchmarks across domains, including genome-scale metabolic models, highlight Gurobi's edge in solve times over CPLEX and SCIP, with Gurobi often completing flux balance analyses fastest while SCIP trails due to weaker presolving on large linear relaxations. ^[47] A comprehensive analysis of solver evolution from 2001 to 2020 reveals that the virtual best MILP solver of 2001 was outperformed by 2020 counterparts by factors exceeding 10^6 in performance profiles, reflecting algorithmic refinements in cutting planes, heuristics, and node selection. ^[48] ^[35] Recent surveys underscore ongoing gains in exact methods, with parallelism and machine learning integrations further boosting throughput on multi-core systems. ^[8] Scalability in practice extends to problems with thousands to millions of variables and constraints, especially those exhibiting sparsity or exploitable structure, as evidenced by routine solutions in logistics and scheduling applications. ^[49] For instance, specialized variants achieve near-linear complexity up to 100,000 variables in structured integer linear programs via tailored decomposition. ^[50] Unstructured dense instances remain challenging, often capping at hundreds of variables for guaranteed optimality, though heuristics yield practical bounds. ^[8] Hardware and software synergies have amplified effective speed by orders of magnitude since 1989, enabling MIPLIB-scale benchmarks to run in fractions of prior times. ^[37] Limits persist for highly combinatorial problems without reformulation, where exponential branching dominates despite presolve reductions. ^[51]

Solution Methods

Exact Algorithms

Exact algorithms for integer programming guarantee the identification of a global optimum by exhaustively searching the feasible integer points while leveraging relaxations to prune the search space efficiently. These methods typically begin with the linear programming (LP) relaxation, obtained by relaxing integer constraints to continuous bounds, which provides an initial bound on the optimal value. If the LP optimum is integer-feasible, it solves the problem; otherwise, techniques refine the relaxation or partition the space to enforce integrality. Modern implementations integrate linear programming solvers, such as variants of the simplex method, to handle relaxations at each step.^[52] Branch-and-bound (B&B) forms the core of many exact solvers, systematically dividing the problem into subproblems via a tree search. Introduced by Land and Doig in 1960, the algorithm solves the LP relaxation at the root node and branches on a fractional variable, imposing floor and ceiling constraints to create child nodes. Bounds from these relaxations—upper for maximization, lower for minimization—allow fathoming branches that cannot yield better solutions than the current best integer incumbent. Pruning occurs if a node's bound is worse than the incumbent or if the subproblem is infeasible, ensuring termination with the optimum upon exhausting the tree. Variable selection strategies, such as most fractional or pseudocost branching, and strong bounding enhance efficiency.^[53] Cutting plane methods strengthen the LP relaxation by adding valid inequalities that eliminate fractional solutions without excluding integer optima. Gomory's pioneering work in 1958 developed finite cutting plane procedures for pure integer programs, deriving cuts from the simplex tableau of an optimal fractional LP solution. For instance, Gomory fractional cuts exploit the form of basic variables expressed as non-integer linear combinations of originals, yielding inequalities like \sum a_j x_j \geq \lceil b \rceil for positive coefficients. These are iteratively added until an integer solution emerges, though pure cutting planes can generate many constraints. Chvátal-Gomory cuts generalize this by applying rounding to any valid inequality.^[54] Branch-and-cut combines B&B with cutting planes, generating and applying cuts dynamically at tree nodes to tighten relaxations and reduce the enumerated space. This hybrid approach, prevalent in solvers since the 1990s, separates cut generation from the LP solver for modularity, employing libraries of problem-specific cuts (e.g., Gomory mixed-integer cuts for mixed-integer programs) alongside generic ones. Stabilization techniques, like adding cuts gradually or using aggregation, prevent numerical instability from excessive constraints. Empirical evidence shows branch-and-cut outperforming standalone B&B, solving instances with thousands of variables and constraints within hours on standard hardware.^[55] For structured problems, dynamic programming offers exact solutions by decomposing into overlapping subproblems with optimal substructure, computing values bottom-up via recursion with memoization. Though exponential in general dimensions, it excels in low-dimensional or knapsack-like cases, where states track partial sums or weights. Reformulations, such as network flows or shortest paths, enable polynomial-time exact DP for specific integer programs.^[52]

Heuristic Approaches

Heuristic approaches in integer programming generate high-quality feasible solutions efficiently, forgoing optimality guarantees to tackle computationally demanding instances where exact methods falter. Integrated into modern mixed-integer programming solvers, these techniques furnish incumbent solutions that inform branch-and-bound processes or approximate optima under time limits.^[56] Linear programming-based heuristics leverage the LP relaxation of the mixed-integer program. Rounding methods derive an LP solution and convert fractional integer variables to nearest integers, with subsequent adjustments to restore feasibility if needed. Diving heuristics progressively fix variables to integer values informed by the LP solution—often prioritizing objective-favorable rounding—and iteratively resolve the tightened LP to direct additional fixings, variants including coefficient tuning and pseudocost-guided diving.^[56]^[57] The feasibility pump, developed by Fischetti, Glover, and Lodi in 2005, exemplifies an advanced LP-based method. It cycles between rounding a continuous relaxation solution to an integer approximation and minimizing the distance from that approximation to the feasible set via a continuous solve, converging toward a feasible integer solution; enhancements like objective perturbations in later variants promote diversity.^[58]^[59] Mixed-integer programming-based heuristics frame subproblems as MIPs. Local branching, introduced by Fischetti and Lodi in 2003, confines exploration to neighborhoods of an incumbent solution via constraints bounding changes in integer variables, such as Hamming distance limits of 10 or 20. Relaxation Induced Neighborhood Search fixes variables matching between the incumbent and the node's LP relaxation, then resolves the reduced MIP.^[56] Metaheuristics adapt trajectory and population strategies—simulated annealing, tabu search, genetic algorithms—for MIP, typically via hybrid matheuristics incorporating exact sub-solvers or decoders mapping to feasible integers. Empirical assessments reveal heuristics often secure near-optimal or optimal solutions in seconds for cases demanding hours for full resolution, though their role skews toward primal bounds over dual proofs.^[56]

Exploitable Problem Structures

Certain integer linear programming problems possess constraint structures that guarantee the linear programming (LP) relaxation yields integer-optimal solutions, enabling polynomial-time solvability via standard LP algorithms such as the simplex method.^[60] A primary such structure arises when the constraint matrix A is totally unimodular (TU), defined as a matrix where the determinant of every square submatrix is -1, $0, or $1.^[60] For an integer program \max \mathbf{c}^\top \mathbf{x} subject to A\mathbf{x} = \mathbf{b}, \mathbf{x} \geq \mathbf{0}, with A TU and \mathbf{b} integer-valued, the polyhedron \{ \mathbf{x} \mid A\mathbf{x} = \mathbf{b}, \mathbf{x} \geq \mathbf{0} \} has integer vertices, ensuring the LP optimum is integer.^[61] This property extends to inequality forms A\mathbf{x} \leq \mathbf{b} by converting to equality via slack variables, preserving TU if the original A is TU.^[60] TU matrices characterize several combinatorial optimization problems with integral polyhedra. Notable examples include the node-arc incidence matrix of a directed graph, which is TU and underlies minimum-cost flow problems solvable in O(nm \log n (m + n \log n)) time using combinatorial algorithms or LP.^[62] Similarly, the incidence matrix of a bipartite graph is TU, rendering the assignment problem—maximizing \sum c_{ij} x_{ij} subject to row and column sum constraints—efficiently solvable, as its LP relaxation yields integer assignments.^[63] Transportation problems, with TU supply-demand constraints, also benefit, allowing LP-based solutions without branch-and-bound.^[62] These structures exploit the absence of fractional vertices in the LP polytope, avoiding the integrality gap prevalent in general integer programs.^[61] Beyond strict TU, certain nearly totally unimodular matrices enable strong proximity bounds between LP and IP optima, facilitating faster exact solving via orbital branching or reduced enumeration in branch-and-bound frameworks, though these yield approximations rather than guaranteed integrality without additional cuts.^[64] In network design and scheduling applications, partial TU substructures (e.g., in constraint rows) can be exploited by specialized reformulations or decomposition, decomposing the problem into TU subproblems solvable independently before aggregation.^[62] Detection of TU or network matrices in practice relies on graph-theoretic checks, such as verifying bipartiteness for incidence matrices, which run in linear time.^[63]

Variants

Mixed-Integer Linear Programming

Mixed-integer linear programming (MILP) extends integer linear programming by permitting a subset of decision variables to remain continuous while requiring others to attain integer values, within a framework of linear objectives and constraints. This hybrid structure models real-world scenarios involving discrete selections alongside quantifiable flows or levels, such as facility activation decisions coupled with material transport volumes.^[15] The canonical MILP formulation minimizes \mathbf{c}^T \mathbf{x} subject to A \mathbf{x} = \mathbf{b}, bounds l \leq \mathbf{x} \leq u, and integrality constraints on designated components of \mathbf{x}. Binary variables, constrained to {0,1}, frequently encode on/off choices or logical disjunctions, often implemented via big-M constraints or specialized solver features to linearize conditional expressions.^[15]^[65] Distinct from pure integer programming, which mandates integrality across all variables, MILP's continuous variables preserve tractable linear programming relaxations as lower bounds for bounding in search algorithms. Solution methods rely on relaxing integrality to yield convex linear programs, then branching on fractional integer candidates while incorporating cuts to refine polyhedral approximations of the feasible set.^[15]^[66] Formulation quality profoundly influences computational tractability, as compact, tight relaxations—achieved through techniques like lifted cover inequalities or perspective reforms—reduce branching overhead and enhance heuristic efficacy in modern solvers. MILP dominates practical optimization in domains like logistics, energy systems, and manufacturing, where solvers such as Gurobi leverage presolving, parallelism, and machine learning for instances with thousands of variables.^[65]^[67]

Integer Nonlinear Programming

Integer nonlinear programming refers to optimization problems in which some or all decision variables are constrained to integer values and either the objective function or the constraints incorporate nonlinear relationships.^[68] These problems generalize both integer linear programming, by allowing nonlinearity, and nonlinear programming, by imposing integrality restrictions.^[69] Formally, a mixed-integer nonlinear program (MINLP), the predominant variant that permits both integer and continuous variables, can be stated as minimizing f(\mathbf{x}, \mathbf{y}) subject to g_i(\mathbf{x}, \mathbf{y}) \leq 0 for i = 1, \dots, m, h_j(\mathbf{x}, \mathbf{y}) = 0 for j = 1, \dots, p, \mathbf{x} \in \mathbb{Z}^{n_1}, and \mathbf{y} \in \mathbb{R}^{n_2}, where f, g_i, and h_j are nonlinear functions.^[70] Unlike mixed-integer linear programs (MILPs), which benefit from polyhedral relaxations and efficient cutting-plane methods, MINLPs often feature nonconvex nonlinearities that introduce multiple local optima and exacerbate the integrality gap.^[69] Pure integer nonlinear programs, with all variables integer-valued, further complicate matters by lacking continuous relaxations, rendering standard nonlinear solvers inapplicable without reformulation.^[68] Computational challenges stem from the combinatorial explosion of integer choices combined with the need to navigate nonconvex feasible regions, leading to NP-hard complexity even for restricted cases; for instance, problems with bilinear terms alone remain NP-hard.^[69] Certain nonconvex MINLPs can be undecidable due to nonlinearities capable of encoding undecidable problems like the halting problem, though practical instances typically avoid such pathology.^[71] Exact solution methods extend branch-and-bound (B&B) frameworks from MILP by solving nonlinear program (NLP) relaxations at tree nodes, using techniques like spatial branching on continuous variables alongside integer branching.^[72] For convex MINLPs, decomposition approaches such as outer approximation (OA), which linearizes nonlinear constraints around trial points to generate MILP master problems, or generalized Benders decomposition (GBD), which dualizes complications via subproblems, provide convergence guarantees under regularity conditions like constraint qualifications.^[73] Nonconvex cases require global optimization variants, including alpha-BB underestimators for twice-differentiable functions or multistart heuristics within B&B, though these scale poorly beyond moderate sizes (e.g., hundreds of variables).^[69] Reformulations, such as piecewise linear approximations of nonlinear terms or perspective functions for certain factorable forms, can transform MINLPs into MILPs or convex equivalents, but introduce auxiliary variables and potential loss of exactness.^[68] Heuristic and hybrid methods dominate large-scale applications, including genetic algorithms, simulated annealing, or machine learning surrogates to guide branching and pruning.^[74] For example, decomposition-based heuristics iteratively solve restricted NLPs or MILPs, using Lagrangian relaxation to handle couplings.^[73] Commercial solvers like BARON employ deterministic global B&B with McCormick relaxations for factorable nonconvexities, achieving optimality gaps under 1% on benchmark sets like MINLPLib as of 2012 updates, though performance degrades with signomial terms or high-dimensional nonconvexity.^[69] Empirical studies highlight that convexifiable structures, such as posynomial objectives, enable efficient local solvers like IPOPT within B&C frameworks, but general nonconvex MINLPs often necessitate problem-specific exploitations.^[70]

Extensions to Uncertainty

Integer programming formulations often assume deterministic parameters, but real-world applications frequently involve uncertainty in data such as demand forecasts, costs, or capacities, necessitating extensions that incorporate probabilistic or adversarial models of variability.^[75] These extensions maintain the integer constraints while adapting optimization objectives to account for incomplete knowledge, typically through recourse actions, worst-case guarantees, or distributional assumptions.^[76] Stochastic integer programming (SIP) models uncertainty via known probability distributions over parameters, distinguishing between here-and-now decisions (made before uncertainty realization) and wait-and-see recourse decisions (adapted afterward). In two-stage SIP, first-stage variables are often integer to represent committing resources like facility openings, while second-stage variables handle outcomes across scenarios, potentially also integer-valued to enforce discrete adjustments; the objective minimizes first-stage costs plus expected recourse costs.^[75] Multi-stage variants extend this to sequential decisions over time horizons with evolving uncertainty, solved via decomposition methods like stochastic dual dynamic integer programming, which leverages integer properties for bounding and branching.^[77] SIP problems inherit the combinatorial hardness of integer programming, with solution times scaling poorly beyond dozens of scenarios due to the need for scenario trees or sample averages, though progress in hybrid branch-and-cut approaches has enabled applications in energy planning and supply chains as of 2021.^[78] Robust integer programming, by contrast, eschews probabilistic assumptions for uncertainty sets defining feasible parameter perturbations, optimizing decisions to remain feasible and near-optimal under any realization within the set, often via worst-case objective maximization over adversaries.^[79] For instance, Bertsimas-style budgeted uncertainty allows controlled conservatism, reformulated as mixed-integer programs solvable by standard solvers when the underlying Graver basis (encoding integer dependencies) is precomputed, achieving polynomial-time solvability for fixed-width bases despite general NP-hardness.^[80] Multi-stage robust mixed-integer programs extend this to dynamic settings, using affine decision rules or exact reformulations for recourse, with applications in robust scheduling where exact solutions via semi-infinite programming have been demonstrated for problems up to 100 variables as of 2023.^[81] These approaches prioritize feasibility guarantees over expected performance, trading solution tractability for resilience against model misspecification in distributions.^[82] Chance-constrained integer programming further bridges stochastic and robust paradigms by enforcing constraints to hold with high probability (e.g., 95% reliability), often approximated via scenario reduction or convex safe approximations, though integer variables complicate exact reformulation and increase computational demands.^[83] Distributionally robust variants amplify this by optimizing over ambiguity sets of distributions, yielding conservative yet data-driven solutions; for example, moment-based ambiguity in objective coefficients can be cast as tractable mixed-integer programs when training data informs set parameters, with empirical studies showing robustness to out-of-sample uncertainty as of 2023. Overall, these extensions amplify the inherent complexity of integer programming, with ongoing research focusing on scalable heuristics and decomposition to handle instances beyond small-scale exact solves.^[85]

Applications

Optimization in Manufacturing and Logistics

Integer programming formulations enable precise optimization of discrete decisions in manufacturing, such as determining production quantities and batch setups under capacity limits. In production planning, mixed-integer linear programming models account for setup costs and times by introducing binary variables to indicate production runs, alongside integer variables for lot sizes, minimizing total costs while satisfying demand over multiple periods.^[86] For example, in sawn timber manufacturing, a mixed-integer linear programming model optimized ripping operations by selecting cut patterns to minimize waste, integrated with a population-based incremental learning algorithm for solution, demonstrating feasibility for practical instances with dozens of logs and patterns.^[87] In steelmaking-continuous casting processes, mixed-integer programming schedules sequences of casts and setups to adhere to compatibility constraints between grades, reducing delays and improving throughput; a 2005 model handled up to 20 casts per sequence with slab matching to caster widths.^[88] In grain handling facilities, mixed-integer programming optimizes blending and storage decisions, incorporating integer constraints for discrete truck loads and bin assignments to minimize transportation and operational costs. A 2022 application in a Brazilian grain terminal used such models to select harvesting machinery and routes, achieving up to 15% cost reductions in simulated scenarios compared to manual planning.^[89] These models leverage branch-and-bound or cutting-plane methods to enumerate feasible integer solutions, ensuring global optimality for problems with up to thousands of variables when structures like total unimodularity are absent, necessitating exact algorithms over relaxations.^[8] Logistics applications rely on integer programming for routing and network design, where binary variables represent edge selections in graphs to model indivisible shipments or vehicle assignments. The vehicle routing problem, a core logistics challenge, is formulated as an integer program minimizing total distance subject to capacity and depot constraints, with subtour elimination via inequalities; extensions to time windows add further integer variables for sequencing. In automotive inbound logistics, a mixed-integer linear programming model optimized milk-run routes for parts delivery, integrating supplier clustering and vehicle loading, solved via Gurobi to yield schedules with 10-20% fewer vehicles than heuristics in test cases with 50 suppliers.^[90] Supply chain network optimization employs mixed-integer programming to select warehouse locations and flows, balancing fixed opening costs against transportation savings; a periodic review policy integrated with integer models minimized inventory across echelons, reducing holding costs by coordinating order-up-to levels in multi-supplier chains.^[91] Facility location-allocation problems in logistics use 0-1 integer variables to decide site openings from candidate sets, minimizing sum of fixed and variable costs; a 2023 case in Iranian chain stores solved such a model for 15 potential locations serving 100 demand points, achieving 12% cost savings over greedy placements via exact solving with LINGO.^[92] Reverse logistics for returns handling applies integer programming to route collections and allocate processing capacities, as in a model minimizing transportation for product recovery networks with integer flow variables enforcing capacity discreteness.^[93] Empirical scalability in logistics often requires decomposition, such as Benders' for large-scale routing, enabling solutions for instances with hundreds of nodes where pure integer programming would exceed computational limits.^[8]

Scheduling and Timetabling

Integer programming models are widely employed in scheduling problems to optimize the allocation of jobs to machines or time slots under constraints such as precedence relations, resource availability, and non-overlap requirements. In job-shop scheduling, which involves sequencing operations across multiple machines for each job to minimize makespan, formulations typically use binary variables to enforce disjunctive ordering constraints between operations competing for the same machine, as in the classic model proposed by Manne in 1960 and refined in subsequent works.^[94] Time-indexed integer linear programming approaches further discretize time horizons into slots, assigning binary indicators for operation starts while bounding completion times via cumulative constraints, enabling exact solutions for small to medium instances via branch-and-bound solvers.^[95] Timetabling problems, a specialized class of scheduling focused on periodic resource assignments like classes to timeslots or exams to periods, leverage similar integer formulations but emphasize conflict avoidance and fairness objectives. For university course timetabling, mixed-integer programming models assign lectures to rooms and times while incorporating student section choices, teacher preferences, and capacity limits; a 2022 formulation maximized student satisfaction by jointly optimizing class allocations and timetables, solving instances with hundreds of courses using commercial solvers like CPLEX.^[96] School timetabling often employs integer linear programming for cohort-based structures, where binary variables ensure no teacher or room overlaps across student groups, with objectives minimizing idle times or deviations from preferences, as demonstrated in models handling up to 40 classes and 20 periods.^[97] Examination timetabling uses integer programs to minimize conflicts, defined as pairs of exams taken by the same student in overlapping slots, with binary assignment variables subject to room and invigilator constraints; a 2024 model for this NP-hard problem incorporated time windows and consecutive period penalties, achieving optimal solutions for datasets with over 1,000 exams via Lagrangian relaxation hybrids.^[98] Conference scheduling extends these to multi-track events, modeling session assignments with integer variables for timeslots and rooms to balance attendance and speaker constraints, with recent 2024 approaches handling thousands of talks through compact formulations that reduce variable counts by aggregating symmetric slots.^[99] These applications highlight integer programming's strength in providing provably optimal solutions for tractable instances, though large-scale problems often require hybridization with heuristics due to exponential complexity.^[100]

Network and Infrastructure Design

Integer programming formulations are employed in network design to optimize the selection and configuration of discrete elements, such as links, nodes, and capacity modules, minimizing construction and operational costs while ensuring requirements like connectivity, traffic capacity, and survivability against failures. These problems often involve binary variables indicating whether to build a component and integer variables for quantities like cable counts or facility sizes, subject to constraints on demand satisfaction and budget. For instance, in telecommunication backbone networks, mixed-integer programs model multi-layer routing and dimensioning to support unsplittable flows, achieving optimality gaps below 0.3% in large-scale instances with thousands of links using branch-and-cut solvers.^[101] In telecommunication infrastructure, integer linear programs address frequency assignment in GSM networks by minimizing interference through graph coloring constraints, yielding feasible solutions that reduced interference by 83.6% in a Berlin-Dresden deployment with 2,877 carriers across 50 channels. Node location problems, such as selecting hub sites from 750 candidates, are solved exactly via 0-1 integer programs with around 100,000 variables, enabling optimal placement of 10 primary and 20 secondary nodes in seconds using commercial solvers like CPLEX. Survivable network design extends this by incorporating failure scenarios, formulating minimum-cost edge selections to maintain multi-commodity flows under single-link disruptions, as in models for k-node-connected subgraphs.^[101]^[102]^[103] Transportation infrastructure leverages mixed-integer programming for road and access network layout, such as forest road systems where binary decisions on road segments minimize earthwork volumes and lengths while connecting harvest areas to mills, as demonstrated in optimization models balancing logging efficiency and environmental constraints. In power grid design, integer programs select transmission lines and generator placements to optimize AC power flow under integer capacity constraints, tractable via modern solvers for realistic grids despite NP-hardness. These applications in electric infrastructure planning integrate renewables, using nested mixed-integer formulations to decide on peaking units and storage amid uncertainty, prioritizing long-term cost minimization over decades.^[104]^[105]^[106]

Finance and Resource Allocation

Integer programming models are employed in finance to address discrete decision-making under constraints, particularly in capital budgeting where firms select mutually exclusive or independent investment projects to maximize value while adhering to limited capital resources. In such formulations, binary variables indicate project acceptance (1) or rejection (0), with the objective maximizing the sum of net present values and constraints enforcing budget limits and precedence relationships.^[6] These 0-1 integer programs extend the classical knapsack problem, accounting for indivisibility of projects; for instance, computational studies on real firm data from the 1960s demonstrated that branch-and-bound algorithms could solve problems with up to 100 variables efficiently when dependencies were sparse.^[107] Portfolio optimization leverages mixed-integer programming to incorporate realistic constraints absent in continuous models, such as cardinality limits on the number of assets held to reduce diversification costs or minimum trade sizes due to liquidity requirements. Binary variables enforce these thresholds, while continuous variables represent fractional allocations; for example, a mixed-integer quadratic program minimizes variance subject to expected return targets and at most k assets selected, solvable via successive linear approximations.^[108] Fixed transaction costs are modeled by introducing binary indicators for trades exceeding zero, transforming the problem into a mixed-integer linear program that balances rebalancing benefits against costs, as applied in practitioner tools for index tracking.^[109] In resource allocation contexts within finance, integer programming optimizes the distribution of indivisible funds across competing uses, such as loan portfolios or hedging instruments, where variables denote integer quantities allocated to ensure coverage without fractional commitments. Multinational firms have used binary integer programs under capital rationing to prioritize investments across periods, incorporating cash flows and risk via scenario-based constraints; empirical applications show improvements over heuristic rankings by 5-15% in selected value.^[110] These models prioritize empirical solvability, often relaxing to linear programs for bounds before branching on integers, highlighting IP's role in causal trade-offs between return, risk, and feasibility in discrete settings.^[111]

Recent Advances and Challenges

Improvements in Solver Technology

Advancements in integer programming solvers have centered on refining the branch-and-bound algorithm through integration of cutting planes, yielding the branch-and-cut paradigm, which tightens linear programming relaxations by dynamically adding valid inequalities to improve bounding and reduce the search tree size.^[8] This approach has evolved with sophisticated cut selection and separation heuristics, enabling solvers to handle instances with thousands of variables and constraints that were intractable decades ago. Algorithmic progress from 2001 to 2020 amplified solver efficacy, with linear programming relaxations benefiting from roughly nine-fold improvements due to enhanced simplex and interior-point methods, while mixed-integer aspects saw compounded gains from better node selection, pseudocost branching, and presolving reductions that eliminate redundant variables and constraints early.^[48] Primal heuristics, invoked at multiple stages such as root node processing or post-presolve, have proliferated in modern solvers, with dozens of variants like diving, rounding, and local search contributing to faster feasible solution discovery; a 2025 analysis highlights their role in closing optimality gaps on challenging benchmarks.^[112] Machine learning integrations represent a frontier, including supervised and reinforcement learning for adaptive cut generation and heuristic parameter tuning, achieving up to orders-of-magnitude speedups on structured problems by predicting effective branching variables or inequality types.^[113] ^[114] Techniques borrowed from Boolean satisfiability solvers, such as pseudo-conflict-directed clause learning, enhance conflict analysis in branch-and-cut to propagate tighter bounds and prune infeasible subtrees more efficiently.^[115] Commercial implementations, exemplified by Gurobi's iterative releases, deliver measurable gains like 16% overall faster mixed-integer solving and 26% on models exceeding 100 seconds, driven by refined dual simplex for relaxations and parallel tree exploration.^[116] Emerging hardware accelerations, particularly GPU-optimized barrier methods for linear programming subproblems within mixed-integer frameworks, address bottlenecks in large-scale routing and scheduling, with reported breakthroughs in solving dense constraint systems previously limited by CPU-bound iterations.^[117] These developments, combined with hardware speedups averaging 20-fold over two decades, have democratized access to optimal solutions for industrial applications, though open-source solvers lag commercial ones by factors of 10-20 on average due to less refined interior-point implementations and fewer proprietary heuristics.^[48] ^[118]

Persistent Limitations and Open Questions

Despite algorithmic advances such as branch-and-cut and decomposition methods, integer programming retains inherent limitations stemming from its NP-hard complexity; the decision problem of determining feasibility for a general integer linear program is NP-complete, precluding polynomial-time solvability for arbitrary instances unless P=NP. In fixed dimension, solvability improves to polynomial time via algorithms like Lenstra's ellipsoid-based approach from 1983, but variable dimension exacerbates exponential growth in search tree sizes for branch-and-bound solvers.^[8] Practical scalability constraints persist, particularly for large-scale mixed-integer programs with thousands of variables and constraints, where modern solvers like Gurobi or SCIP often fail to guarantee optimality within reasonable time limits due to weak relaxations or vast enumeration spaces.^[119] These issues manifest causally from the discrete nature of integer constraints, which introduce integrality gaps and non-convexity absent in continuous linear programming, leading to unreliable bounding and prolonged runtimes in applications like network design or scheduling.^[8] Open questions center on enhancing decomposition techniques, such as Benders and Dantzig-Wolfe, to handle emerging complexities in nonlinear or stochastic extensions, while theoretical gaps remain in deriving tight approximation ratios for NP-hard subclasses like the traveling salesman problem formulated as IP.^[8] Integration of machine learning for predictive presolving and heuristic guidance shows promise but lacks rigorous worst-case guarantees, prompting research into hybrid frameworks that preserve exactness.^[120] Additionally, the efficacy of quantum annealing for IP remains unresolved, with empirical scaling advantages unproven for industrially relevant sizes beyond contrived benchmarks.^[121]

References

[1]
What is integer programming? - IBM
Integer programming expresses the optimization of a linear function subject to a set of linear constraints over integer variables.
[2]
Integer Optimization - Gurobi
Integer optimization, or integer programming, is a specialized area within mathematical optimization that addresses problems requiring variables to be integers ...
[3]
Integer Programming - MATLAB & Simulink - MathWorks
Integer programming is minimizing or maximizing a function subject to equality, inequality, and integer constraints. Integer constraints restrict some or ...
[4]
[PDF] 10.1 Integer Programming and LP relaxation - cs.wisc.edu
Definition 10.1.1 An integer program is a linear program in which all variables must be integers. As in a linear program, the constraints in an integer program ...
[5]
Integer Optimization - Quantum Computing Inc
Integer problems tend to be harder One key aspect of optimization is that problems can often become much harder when restricted to the domain of integers, ...Integer problems tend to be... · Integer Optimization · Integer linear programming...
[6]
[PDF] Integer Programming - MIT
If the optimal values for the decision variables in the linear program are all integer, they are optimal; otherwise, a new cut is derived from the new optimal ...
[7]
50 Years of Integer Programming 1958-2008 - SpringerLink
In 1958, Ralph E. Gomory transformed the field of integer programming when he published a paper that described a cutting-plane algorithm for pure integer ...
[8]
Last fifty years of integer linear programming: A focus on recent ...
Aug 1, 2025 · We survey recent advances in developing exact solution methods for MILPs. We focus on computational aspects and recent practical performance improvements.
[9]
[PDF] Business Applications of Integer Programming
Integer programming is used in business for new product development, production planning, real estate, route selection, and stock market transactions.
[10]
[PDF] Integer Programming - UW Math Department
Set-covering problems have many applications in areas such as airline crew scheduling, political districting, airline scheduling, and truck routing. Either–Or ...
[11]
Integer Programming - an overview | ScienceDirect Topics
Integer programming (IP) is defined as an optimization problem in which decision variables must take on integer values, with classifications into pure IP, ...
[12]
Evolution and state-of-the-art in integer programming - ScienceDirect
We discuss the evolution of both technique and philosophy leading to the current state-of-the-art for modeling and solving this challenging class of problems.
[13]
A brief history of linear and mixed-integer programming computation
Recent advances in integer programming software [34][35][36][37][38] [39] [40] has made it possible to obtain optimal solutions for large integer ...
[14]
[PDF] Integer Programming Formulation 1
Formally, in an integer program some decision variables are forced to be integers. Note that this formulation differs from the corresponding LP formulation ...Missing: mathematical | Show results with:mathematical
[15]
Mixed-Integer Programming (MIP/MILP) – A Primer on the Basics
Understand how Mixed-Integer Programming (MIP)and Mixed Integer Linear Programming (MILP) enable advanced decision-making through mathematical optimization.<|separator|>
[16]
[PDF] Lecture 18 Integer linear programming
Integer linear programming. • a few basic facts. • branch-and-bound. 18–1. Page 2. Definitions integer linear program (ILP) minimize. cT x subject to Ax ≤ b x ...
[17]
[PDF] Lecture 2: Modeling and Formulation
In the formulation, we specify constraints that ensure that the feasible solutions to the resulting mathematical optimization problem are indeed. “feasible” in ...
[18]
[PDF] A Tutorial on Integer Programming
The purpose of this chapter is to show some interesting integer programming applications and to describe some of these solution techniques as well as.
[19]
Integer Linear Programming - Gurobi Optimization
The canonical form represents ILP problems in a specific structure that facilitates the application of optimization algorithms. This form includes an ...
[20]
[PDF] 1 Vertex Cover via LP
Jan 28, 2011 · We can formulate it as an integer linear programming problem as follows. For each vertex v we have a variable xv. We interpret the variable as ...
[21]
[PDF] LINEAR PROGRAMMING
Integer Programming began in 1958 by R. E. Gomory. Unlike the earlier work on the traveling salesman problem by D. R. Fulkerson, S. M. Johnson and Dantzig ...
[22]
Optimization/Mathematical Programming - Informs.org
In the 1970s, the IBM 360 class of computers was introduced, and stronger efforts for integer programming were made. Prior to the availability of commercial MP ...<|separator|>
[23]
[PDF] 1 CHAPTER XV: APPLIED INTEGER PROGRAMMING ...
LP was invented in the late. 1940's. Those examining LP relatively quickly came to the realization that it would be desirable to solve problems which had some ...
[24]
George Dantzig's contributions to integer programming - ScienceDirect
Dantzig, Fulkerson, and Johnson (DFJ from now on) pioneered the idea of employing linear programming relaxation and valid inequalities to solve integer programs ...
[25]
[PDF] 50 Years of Integer Programming 1958–2008 - UW Math Department
The study of combinatorial optimization problems such as the traveling salesman problem has had a significant influence on integer programming. Fifty-plus ...
[26]
LP from the '40s to the '90s - jstor
the work of Land and Doig in 1960, it gradually became practical to solve integer programming models of increasing size. (7) LP on computers: LP problems were.
[27]
Early Integer Programming - PubsOnLine
During the academic year 1953–54, I was a third-year graduate student in mathematics at Princeton, doing research on nonlinear differential equations.
[28]
[PDF] ON CUTTING PLANES*
We give a geometrical description of Chvatal's version of Gomory's cutting plane method. Restricting ourselves to rational spaces, we prove that the derived ...
[29]
On cutting-plane proofs in combinatorial optimization - ScienceDirect
Gomory's cutting-plane technique can be viewed as a recursive procedure for proving the validity of linear inequalities over the set of all integer vectors ...
[30]
[PDF] INTEGER PROGRAMMING WITH A FIXED NUMBER OF VARIABLES*
LENSTRA, JR. Universiteit van Amsterdam. It is shown that the integer linear programming problem with a fixed number of variables is polynomially solvable.
[31]
Integer Programming with a Fixed Number of Variables - PubsOnLine
In this paper we consider the integer linear programming problem with a fixed value of n. In the case n = 1 it is trivial to design a polynomial algorithm for ...
[32]
A Branch-and-Cut Algorithm for the Resolution of Large-Scale ...
A Branch-and-Cut Algorithm for the Resolution of Large-Scale Symmetric Traveling Salesman Problems. Authors: Manfred Padberg and Giovanni RinaldiAuthors ...
[33]
A Branch-and-Cut Algorithm for the Resolution of Large-Scale ... - jstor
Abstract. An algorithm is described for solving large-scale instances of the Symmetric. Traveling Salesman Problem (STSP) to optimality. The core of the ...
[34]
Our Story - Gurobi Optimization
In 2008, our founders created Gurobi Optimization with a single, simple vision: To build the world's fastest and most powerful mathematical optimization solver ...
[35]
[PDF] Progress in Mathematical Programming Solvers from 2001 to 2020
Jun 23, 2022 · This study investigates the progress made in lp and milp solver performance during the last two decades by comparing the solver software ...
[36]
SCIP
SCIP is currently one of the fastest non-commercial solvers for mixed integer programming (MIP) and mixed integer nonlinear programming (MINLP). It is also a ...Installing SCIP · SCIP C-API · First Steps Walkthrough · Interfaces
[37]
Solver performance: 1989 vs 2024
Jan 5, 2024 · In this article, we estimate the magnitude of speed improvement for optimization solvers and computer hardware in the 35 years from 1989 to 2024.1989: Crossword Compilation... · Computer Improvements · Solver Improvements
[38]
[PDF] Lecture 5 Integer Programming
The Integer Programming problem (IP) is that of deciding whether there exists an integer solution to a given set of m rational inequalities on n variables.
[39]
Proving 0-1 integer programming is NP-complete (using reduction ...
In this post, we will prove that 0-1 integer programming is NP-complete using a reduction from 3-CNF-SAT (which is NP-complete). We will follow the template ...
[40]
[PDF] NP-completeness of Some Number Theory Problems
Is Integer Programming (IP). NP-Hard? Theorem: Integer Programming is NP-Hard. Proof: By reduction from Satisfiability (SAT ≤ p IP). • Take an instance of SAT ...<|control11|><|separator|>
[41]
[PDF] THE COMPUTATIONAL COMPLEXITY OF LINEAR ...
Sep 9, 2025 · In this section, we prove that solving integer linear programs is NP-hard, even if they have only a polynomial number of constraints. THEOREM 2.
[42]
On the Computational Complexity of Integer Programming Problems
In this paper a general integer programming problem is shown to be NP-complete; the proof given for this result uses only elementary linear algebra.
[43]
[PDF] On the Complexity of Integer Programming - LARA
In this note we show that there is a pseudopolynomial algorithm for the problem that results by extending the knapsack problem in all three directions above.Missing: hard | Show results with:hard
[44]
[PDF] The Computational Complexity of Integer Programming ... - DROPS
Abstract. We prove that integer programming with three alternating quantifiers is NP-complete, even for a fixed number of variables.
[45]
MIPLIB 2017 – The Mixed Integer Programming Library
The Benchmark Set contains 240 instances that are solvable by (the union of) today's codes. For practical reasons, the benchmark instances were selected subject ...The Benchmark Set · The Collection Set · Guide to the Instance Statistics · News LogMissing: progress | Show results with:progress
[46]
MIPLIB 2017: data-driven compilation of the 6th mixed-integer ...
Jan 7, 2021 · The new MIPLIB 2017 collection consists of 1065 instances. A subset of 240 instances was specially selected for benchmarking solver performance.
[47]
A benchmark of optimization solvers for genome-scale metabolic ...
Jan 22, 2024 · For single-species FBA, it can be observed that GUROBI was the fastest solver, followed by CPLEX, whereas SCIP was the slowest solver for models ...
[48]
Progress in mathematical programming solvers from 2001 to 2020
The article contains a comprehensive performance comparison of the virtual best lp/milp solver from 2001 with the best solvers from 2020.
[49]
How many decision variables can be solved for Mixed Integer ...
Mar 16, 2016 · Short answer : Yes it is possible to solve MIP with millions of decision variables. Theory In general MIP is NP-hard problem and cannot be solved in polynomial ...
[50]
[PDF] Solving Large-Scale Integer Linear Programs
We show variations in computational time and number of function evaluations for 100 to 100,000-variable ILP problems and in all problems near-linear complexity ...
[51]
Fast and Interpretable Mixed-Integer Linear Program Solving ... - arXiv
Dec 31, 2024 · Existing ML-based MILP solvers mainly focus on end-to-end solution learning, which suffers from the scalability issue due to the high ...
[52]
[PDF] Exact and Heuristic Methods for Mixed Integer Linear Programs
Among the currently most successful methods, to solve MIP problems, are linear programming (LP, for short) based branch-and-bound algorithms, where the ...
[53]
[PDF] Branch and Bound in Mixed Integer Linear Programming Problems
Nov 5, 2021 · In this paper, we surveyed the existing literature studying different approaches and algorithms for the four critical components.
[54]
[PDF] Cutting Planes for Mixed-Integer Programming: Theory and Practice
Next: A finite cutting-plane algorithm for mixed-integer programming ... • Gomory (1958) developed the first finite cutting plane algorithm for pure IPs.
[55]
[PDF] Computational Integer Programming Lecture 12: Branch and Cut
We iteratively try to improve the current bound by adding valid inequalities. In practice, branch and cut is the method typically used for solving difficult ...
[56]
[PDF] "Heuristics in Mixed Integer Programming" in - CWI
The polishing algorithm is then a fully general metaheuristic implemented within an MILP framework and, in turn, making use of an external MILP solver as main ' ...
[57]
[PDF] Primal Heuristics for Mixed Integer Programs - OPUS
other three diving heuristics described in this chapter rely on some informa- tion which is got during the MIP-solving process: Guided Diving needs an.
[58]
[PDF] The feasibility pump - dei.unipd
We start from any x∗ ∈ P, and initialize a typically infeasible integer point ex as the rounding of x∗. At each FP iteration, called a pumping cycle, we fix ex ...
[59]
[PDF] Feasibility Pump 2.0 1 Introduction - dei.unipd
Finding a feasible solution of a given Mixed-Integer Programming. (MIP) model is a very important NP-complete problem that can be extremely hard in practice.
[60]
[PDF] Chapter 2 Integer Programming Paragraph 1 Total Unimodularity
– A matrix A is called totally unimodular (TU), iff the determinants of all submatrices of A are either -1, 0, or 1. – A polytope P={ x | Ax=b, x ≥ 0 } with A ...
[61]
[PDF] 1 Totally Unimodular Matrices - Stanford CS Theory
Totally unimodular matrices are very well behaved, because they always define polytopes with integer vertices, as long as the right-hand side is integer-valued.
[62]
[PDF] Applications and efficient algorithms for integer programming ...
Jul 30, 2020 · Abstract. We present here classes of integer programming problems that are solvable effi- ciently and with combinatorial flow algorithms.
[63]
[PDF] Integer programming and totally unimodular matrices - AMiner
A matrix A is totally unimodular if every square submatrix has determinant 0, 1, or -1. A graph is bipartite if and only if its incidence matrix is totally ...
[64]
[PDF] Integer programs with nearly totally unimodular matrices - arXiv
Jul 12, 2024 · First, we derive a strong proximity result for the case where A is a general totally unimodular ma- trix: Given an optimal solution of the ...
[65]
[PDF] Mixed Integer Linear Programming Formulation Techniques
We now have several extremely effective state-of-the-art solvers. [82, 69, 52, 171] that incorporate many advanced techniques [1, 2, 25, 23, 92, 112, 24] and, ...<|separator|>
[66]
Integer Programming vs. Linear Programming | Medium
Sep 26, 2024 · Linear Programming: Easier to solve since the solution space is continuous and convex, making the use of efficient algorithms like the Simplex ...
[67]
Mixed-Integer Linear Programming - an overview - ScienceDirect.com
Mixed Integer Linear Programming (MILP) is defined as an optimization technique that involves both integer and non-integer variables, commonly used for ...
[68]
[PDF] Nonlinear Integer Programming - Optimization Online
Abstract. Research efforts of the past fifty years have led to a development of linear integer programming as a mature discipline of mathematical optimization. ...
[69]
Review Non-convex mixed-integer nonlinear programming: A survey
We survey the literature on non-convex MINLPs, discussing applications, algorithms, and software. Special attention is paid to the case in which the objective ...
[70]
Mixed-Integer Nonlinear Programming: A Survey of Algorithms and ...
This paper presents an overview of mixed-integer nonlinear programming techniques by first providing a unified treatment of the Branch and Bound, ...
[71]
[PDF] Undecidability and hardness in mixed-integer nonlinear programming
May 24, 2018 · This survey paper discusses two of the lesser known aspects of Mixed-Integer Nonlinear Programming ... Non-convex mixed-integer nonlinear.<|separator|>
[72]
Branch and bound (BB) for MINLP - Optimization Wiki
Dec 16, 2021 · Branch and bound is a method used to solve Mixed Integer Non-Linear Programming (MINLP) models. There is a difference in the exact steps of the algorithm.Introduction · Algorithmic Discussion · Numerical Solution
[73]
[PDF] Computational Strategies for Improved MINLP Algorithms
Major methods for solving MINLP include OA, GBD, B&B, B&C, ECP methods[16]. OA and. GBD are two common methods for solving MINLP problems. OA is a ...
[74]
A differential evolution algorithm for solving mixed-integer nonlinear ...
Solving mixed-integer nonlinear programming problems can be challenging. ... This scheme generates two challenges: (i) the vulnerability of the algorithms ...
[75]
[PDF] Two-stage stochastic integer programming: A brief introduction
Two-stage stochastic integer programming combines stochastic and integer programming, minimizing first-stage costs and expected second-stage costs. It has ...
[76]
Stochastic Integer Programming - ScienceDirect.com
Stochastic integer programming introduces integer variables into linear stochastic programs, requiring rethinking of structural properties and algorithmic ...
[77]
[PDF] Stochastic Dual Dynamic Integer Programming - MIT Sloan
Mar 27, 2017 · This paper develops effective decomposition algorithms for a large class of multistage stochastic integer programming problems. In this section, ...
[78]
Stochastic Integer Programming
Stochastic integer programming (SIP) problems combine the power of integer decision variables for modeling discrete decisions and logical relationships with ...
[79]
[1402.2852] Robust Integer Programming - arXiv
Feb 12, 2014 · Abstract:We provide a complexity classification of four variants of robust integer programming when the underlying Graver basis is given.
[80]
Robust integer programming - ScienceDirect.com
We provide a complexity classification of four variants of robust integer programming when the underlying Graver basis is given. We discuss applications to ...
[81]
Multi-Stage Robust Mixed-Integer Programming - Optimization Online
Mar 31, 2023 · In this paper, we propose a new model and solution approach for multi-stage robust mixed-integer programs, which may contain both continuous and discrete ...
[82]
Technical Note: Multistage Robust Mixed-Integer Programming
Jan 30, 2025 · In this technical note, we propose a new model and solution approach for multistage robust mixed-integer programs, which may contain both continuous and ...
[83]
A study of distributionally robust mixed-integer programming with ...
Mar 1, 2024 · This study addresses a class of linear mixed-integer programming (MILP) problems that involve uncertainty in the objective function parameters.Missing: survey | Show results with:survey
[84]
A study of distributionally robust mixed-integer programming ... - arXiv
Apr 3, 2023 · Abstract:This study addresses a class of linear mixed-integer programming (MILP) problems that involve uncertainty in the objective function ...
[85]
[PDF] Multi-Stage Robust Mixed-Integer Programming - Optimization Online
Mar 31, 2023 · Two-stage robust optimization problems with mixed-integer recourse decisions have been solved exactly by semi-infinite programming techniques ( ...
[86]
Solving mixed integer programming production planning problems ...
In this study, we have solved production planning problems involving multiple products, multiple resources, multiple periods, setup times and setup costs.
[87]
Mixed-Integer Linear Programming Model for Production Planning
Aug 6, 2025 · ... mixed integer programming to model the ripping operation. A metaheuristic, namely the Population Based Incremental Learning algorithm, was ...
[88]
A mixed-integer linear programming model for the continuous ...
This paper presents a mixed-integer programming model for scheduling steelmaking-continuous casting production.<|separator|>
[89]
Production Optimization in a Grain Facility through Mixed-Integer ...
Aug 17, 2022 · Early works in the area applied linear and mixed-integer programming models for problems related to harvesting methods and machinery selection.
[90]
Optimizing automotive inbound logistics: A mixed-integer linear ...
We present a mixed-integer linear programming approach to solve this complex problem using Gurobi. The solution capability and quality are enhanced.
[91]
Optimizing Supply Chain Inventory: A Mixed Integer Linear ... - MDPI
In this paper, periodic review (s,S) policy is used to optimize inventories from an integrated perspective of inventory management across the supply chain.
[92]
An integer linear programming approach for a location-allocation ...
Jun 14, 2023 · As the population grows and demand increases, cities have seen a rise in the number of chain stores. To remain competitive, these companies ...
[93]
An integer linear programming for a comprehensive reverse supply ...
The presented model is an integer linear programming model being solved using Lingo 9 software. Numerical experiments are conducted to gain insight into the ...
[94]
An Improved Formulation for the Job-Shop Scheduling Problem - jstor
This paper presents an extension of an earlier integer programming model developed by other authors to formulate a general n-job, m-machine job-shop problem ...
[95]
A time-indexed LP-based approach for min-sum job-shop problems
Jan 14, 2011 · In this paper we propose two time-indexed IP formulations for job-shop scheduling problems with a min-sum objective.
[96]
A mixed-integer programming approach for solving university course ...
Feb 15, 2022 · This article presents a mixed-integer programming model for solving the university timetabling problem which considers the allocation of students to classes.
[97]
[PDF] Cohort-Based Timetabling with Integer Linear Programming
In this paper, we describe an Integer Linear Programming (ILP) solution to the. School Timetabling Problem (STP), for schools that are cohort-based. Our Master.
[98]
An Integer Linear Programming Model for the Examination ...
Nov 11, 2024 · Timetabling problems are specific types of scheduling problems that involve the assignment of limited resources to a set of activities or events ...Abstract · Introduction · Problem Description · Numerical Results
[99]
A generic approach to conference scheduling with integer ...
Sep 1, 2024 · We tackle the conference scheduling problem with integer programming models. •. Our models handle conferences with up to a few thousand ...
[100]
[PDF] An integer programming model for timetabling at the University of ...
Jun 26, 2024 · In this thesis, we propose a model to solve the CTT at the University of Groningen. (RUG) using integer linear programming (which is a special ...<|separator|>
[101]
[PDF] Designing telecommunication networks by integer programming
May 3, 2012 · What constitutes a good network? ▫ Study common mathematical properties of network applications. ▫ Develop theory, algorithms,.
[102]
Integer Polyhedra Arising from Certain Network Design Problems ...
In this paper a general integer linear programming model is presented for the important practical problem of designing minimum-cost survivable networks, ...
[103]
The survivable k-node-connected network design problem
In this paper we consider the k-node-connected subgraph problem. We propose an integer linear programming formulation for the problem and investigate the ...
[104]
[PDF] Designing a Forest Road Network Using Mixed Integer Programming
This paper presents a. Mixed Integer Programming (MIP) optimization model to design a forest access system con- sisting of logging roads for trucking and access ...
[105]
[PDF] Designing AC Power Grids using Integer Linear Programming
In view of re- cent developments in the field of integer programming, we show that this model is computationally tractable. A power grid is a transmission ...Missing: infrastructure | Show results with:infrastructure
[106]
[PDF] Electric Power Infrastructure Planning: Mixed-Integer Programming ...
Aug 11, 2017 · This paper addresses the long-term planning of electric power infrastructures considering high renewable penetration.
[107]
Integer Programming in Capital Budgeting - jstor
The purposes of this note are to illustrate some cormiputational experience using existing integer algorithms to solve a set of capital budgeting problemrs and ...
[108]
Mixed-Integer Quadratic Programming Portfolio Optimization
This example shows how to solve a Mixed-Integer Quadratic Programming (MIQP) portfolio optimization problem using the problem-based approach.Problem Outline · Objective and Successive... · MATLAB® Problem Formulation
[109]
[PDF] Portfolio optimization with linear and fixed transaction costs
Bertsimas,. Darnell and Soucy [BDS99] use generic mixed-integer programming methods to deal with fixed costs and other integer constraints in several practical ...
[110]
[PDF] Capital Rationing and Binary Integer Programming for Investment ...
This paper at- tempts: (1) to develop a mathematical programming model for capital budgeting deci~ions of a multinational firm based on linear programming.<|separator|>
[111]
[PDF] Optimization Methods in Finance - andrew.cmu.ed
This course discusses sev- eral classes of optimization problems (including linear, quadratic, integer, dynamic, stochastic, conic, and robust programming) ...
[112]
New book on primal heuristics in integer programming
Jul 21, 2025 · A modern MIP solver can call dozens of heuristics at various points: before or after node processing, after presolving, at the root, and so on.
[113]
Learning to Cut Generation in Branch-and-Cut Algorithms for ...
Aug 29, 2025 · In this article, we propose a framework combining supervised learning and deep reinforcement learning to learn strategies for generating combinatorial cuts in ...Missing: advancements | Show results with:advancements
[114]
Deep learning enhanced mixed integer optimization
We show that deep learning constructed heuristics substantially improve the performance of standard off-the-shelf MIP solvers.
[115]
[PDF] IMPROVING CONFLICT ANALYSIS IN MIP SOLVERS BY PSEUDO ...
Jul 26, 2023 · The area of Boolean satisfiability (SAT) solving has witnessed dramatic performance improvements over the last couple of decades, and several ...
[116]
Prior Version Enhancements - Gurobi Optimization
This page provides a summary of feature enhancements and performance improvements introduced in previous versions of the Gurobi Optimizer.
[117]
https://developer.nvidia.com/blog/solve-linear-programs-using-the-gpu-accelerated-barrier-method-in-nvidia-cuopt/
[118]
Do we know why open source MIP solvers are significantly slower ...
The best open-source solver - HiGHS - is 20 times slower than the best commercial solver (COPT). That's down to the idiosyncratic IPM implementation in HiGHS.
[119]
A Comprehensive Survey of Linear, Integer, and Mixed-Integer Programming Approaches for Optimizing Resource Allocation in 5G and Beyond Networks
### Summary of Challenges and Open Problems in Integer and Mixed-Integer Programming
[120]
A Survey for Solving Mixed Integer Programming via Machine ... - arXiv
Mar 6, 2022 · This paper surveys the trend of leveraging machine learning to solve mixed integer programming (MIP) problems.Missing: open | Show results with:open
[121]
Integer Programming from Quantum Annealing and Open ... - arXiv
Sep 24, 2020 · We developed an algorithm that solves integer linear programming problems, a classically NP-hard problem, on a quantum annealer, and investigated problem and ...