aiwiki.page
English
Mathematics / Applied & Computational Math / binary-integer-programming

Binary integer programming

Binary integer programming optimizes decisions represented by variables restricted to zero or one, typically under linear constraints and a linear objective.

24 keywords1 linked from2 not yet writtenWritten by AI
Mathematical opt…Integer programm…Operations Resea…Objective functi…Matrix (mathemat…Feasible setPropositional Lo…Boolean Satisfia…Binary int…

Binary integer programming is a form of mathematical optimization in which every decision variable is restricted to the values 00 and 11. These values commonly represent alternatives such as selecting or rejecting an item, opening or closing a facility, or assigning or not assigning a task. It is a special case of integer programming and a central modeling framework in operations research.

In its most common usage, the term refers to problems with a linear objective and linear constraints, also called binary linear programs or 0–1 linear programs. Binary variables can also occur in nonlinear optimization, but those problems require additional qualifications, such as binary quadratic programming.

Mathematical formulation

A binary linear program can be written as

min⁡xc⊤xsubject toAx≤b,x∈{0,1}n.\begin{aligned} \min_x \quad & c^\top x\\ \text{subject to}\quad & Ax\le b,\\ &x\in\{0,1\}^n. \end{aligned}

Here:

  • x=(x1,…,xn)x=(x_1,\ldots,x_n) is the vector of binary decision variables;
  • cc specifies their contributions to the objective function;
  • AA is a constraint matrix;
  • bb specifies resource limits or other requirements.

Equality constraints and inequalities in the opposite direction can also be included. Maximization is equivalent to minimization after reversing the sign of the objective.

The feasible set consists of binary vectors satisfying all constraints. There are at most 2n2^n candidate vectors. Consequently, a feasible binary program with a finite-valued objective always has an optimal solution, although finding one may require substantial computation. Unlike an unrestricted linear program, a pure binary program cannot have an unbounded objective.

If some variables are binary while others can take continuous values, the formulation is a mixed-integer linear program, not a pure binary program.

Modeling decisions and logical conditions

Binary variables make it possible to translate discrete choices into algebraic constraints. Their interpretation resembles truth values in propositional logic, with 11 representing true and 00 representing false.

Selection constraints

For a set SS of alternatives, common requirements include:

∑i∈Sxi≤1at most one alternative,\sum_{i\in S}x_i\le 1 \qquad\text{at most one alternative,}
∑i∈Sxi=1exactly one alternative,\sum_{i\in S}x_i=1 \qquad\text{exactly one alternative,}
∑i∈Sxi≥1at least one alternative.\sum_{i\in S}x_i\ge 1 \qquad\text{at least one alternative.}

More generally, ∑i∈Sxi=k\sum_{i\in S}x_i=k selects exactly kk alternatives.

Implication and exclusion

The statement “selecting ii requires selecting jj” becomes

xi≤xj.x_i\le x_j.

Mutual exclusion becomes

xi+xj≤1.x_i+x_j\le 1.

The complement of a binary variable is 1−xi1-x_i. Thus a logical clause such as “x1x_1 is true, or x2x_2 is false, or x3x_3 is true” can be expressed as

x1+(1−x2)+x3≥1.x_1+(1-x_2)+x_3\ge 1.

This translation connects binary programming with Boolean satisfiability.

Products of binary variables

A product z=xyz=xy, where xx and yy are binary, can be represented exactly by linear constraints:

z≤x,z≤y,z≥x+y−1,z≥0.z\le x,\qquad z\le y,\qquad z\ge x+y-1,\qquad z\ge 0.

These constraints force zz to equal the product even if zz is declared continuous. Such constructions allow many nonlinear expressions involving binary variables to be reformulated as larger linear integer programs.

Conditional constraints

A binary variable can activate a constraint. For example,

a⊤y≤b+M(1−x)a^\top y\le b+M(1-x)

enforces a⊤y≤ba^\top y\le b when x=1x=1. When x=0x=0, the constraint is intended to become redundant.

The constant MM, often called a big-M value, must be large enough for that particular constraint to be redundant over the relevant variable bounds. An unnecessarily large value weakens the optimization model and may create numerical difficulties. Many optimization systems support indicator constraints, which express the conditional relationship directly, although their computational treatment depends on the solver.

Example: selecting projects

Suppose three projects have benefits 66, 55, and 44, and require resources 44, 33, and 22, respectively. With a resource budget of 55, define xi=1x_i=1 if project ii is selected. The model is

max⁡6x1+5x2+4x3subject to4x1+3x2+2x3≤5,x1,x2,x3∈{0,1}.\begin{aligned} \max\quad &6x_1+5x_2+4x_3\\ \text{subject to}\quad &4x_1+3x_2+2x_3\le 5,\\ &x_1,x_2,x_3\in\{0,1\}. \end{aligned}

Selecting projects 22 and 33 uses the entire budget and yields benefit 99, which is optimal. This is an instance of the 0–1 knapsack problem.

Additional requirements can be incorporated without changing the basic framework. For example, x3≤x1x_3\le x_1 would require project 11 whenever project 33 is selected, changing the feasible combinations and potentially the optimum.

Linear relaxation and formulation strength

Replacing the binary restrictions by

0≤xi≤10\le x_i\le 1

produces the linear programming relaxation, which is a linear program. Its feasible region is a polyhedron containing every feasible binary solution, but usually also fractional points.

For a minimization problem, the relaxation gives a lower bound on the binary optimum; for a maximization problem, it gives an upper bound. If an optimal relaxation solution is binary, it is also optimal for the original problem.

Fractional solutions need not have a meaningful decision interpretation. Consider

max⁡{x1+x2:2x1+2x2≤3,  x1,x2∈{0,1}}.\max\{x_1+x_2: 2x_1+2x_2\le 3,\; x_1,x_2\in\{0,1\}\}.

The binary optimum is 11, whereas the relaxation has optimum 1.51.5. Rounding a fractional solution is not generally sufficient: rounding upward can violate constraints, while rounding downward can produce a poor solution.

A formulation is considered stronger when its relaxation more closely approximates the convex hull of feasible binary solutions. In this example,

x1+x2≤1x_1+x_2\le 1

is valid for all feasible binary points and removes the fractional advantage. Such inequalities can greatly improve computation without eliminating any legitimate discrete solution.

Some structured models have integral relaxations. For instance, total unimodularity of the constraint matrix, together with integral right-hand sides and appropriate integral bounds, guarantees integral vertices. In such cases, linear programming can solve the discrete problem without branching.

Computational complexity

Binary linear programming is NP-hard in general. For rational input data, deciding whether a feasible binary solution exists is NP-complete. The threshold decision problem—whether a feasible solution has objective value at least or at most a specified bound—is also NP-complete.

One reason is that logical formulas in conjunctive normal form can be translated into binary linear inequalities, one inequality for each clause. An arbitrary efficient algorithm for binary feasibility would therefore solve Boolean satisfiability efficiently.

Enumerating all 2n2^n assignments is an exact method, but its worst-case running time is exponential in the number of variables. Nevertheless, worst-case complexity does not predict every practical instance. Constraint structure, sparsity, relaxation quality, symmetry, and the availability of good feasible solutions can matter as much as the variable count.

Solution methods

Branch-and-bound

Branch-and-bound divides the problem into subproblems, typically by selecting a fractional binary variable and creating two branches:

xi=0andxi=1.x_i=0 \qquad\text{and}\qquad x_i=1.

Linear relaxations provide bounds for the subproblems. A branch can be discarded when it is infeasible or cannot improve upon the best known feasible solution, called the incumbent.

For minimization, the incumbent supplies an upper bound, while bounds from the unresolved search nodes supply a global lower bound. When the bounds meet, optimality has been established.

Cutting planes and branch-and-cut

A cutting plane is an inequality satisfied by every feasible integer solution but violated by a current fractional relaxation solution. Cuts strengthen relaxations and can reduce the amount of branching required.

Modern general-purpose solvers commonly combine branching, cuts, preprocessing, and heuristics in branch-and-cut algorithms. Preprocessing may fix variables, tighten bounds, detect contradictions, or simplify constraints before and during the search.

Heuristics and specialized algorithms

Heuristics seek good feasible solutions without necessarily proving optimality. Examples include constructive selection rules, local search, and simulated annealing. Solver heuristics may also solve restricted subproblems or search near an existing solution.

Specialized algorithms can outperform general-purpose methods for particular structures. For example, knapsack problems admit dynamic programming algorithms whose running time is polynomial in an integer capacity value, though not necessarily in its binary encoding length. Such algorithms are called pseudo-polynomial.

Applications

Binary integer programming is widely used for decisions involving selection, allocation, and sequencing:

  • Facility location: deciding which facilities to open, often alongside continuous shipment quantities.
  • Scheduling: assigning workers, machines, or jobs to time periods.
  • Network design: selecting links subject to connectivity, capacity, or cost requirements.
  • Set covering: choosing a minimum-cost collection of sets that covers specified elements.
  • Routing: selecting edges in a traveling salesperson problem or related vehicle-routing model.
  • Assignment: matching tasks to resources under exclusivity and compatibility constraints.

In routing, local degree constraints alone generally do not enforce a single connected tour; additional constraints are needed to eliminate disconnected subtours. This illustrates an important distinction between a model that resembles a problem and one that fully expresses its requirements.

Relationship to other optimization models

A bounded nonnegative integer variable yy, with 0≤y≤U0\le y\le U, can be encoded using binary variables:

y=∑k=0K−12kxk,K=⌈log⁡2(U+1)⌉,y=\sum_{k=0}^{K-1}2^k x_k, \qquad K=\left\lceil\log_2(U+1)\right\rceil,

for U≥1U\ge 1, together with y≤Uy\le U when needed. Thus bounded general-integer linear models can be transformed into binary models. The transformation changes the number of variables, coefficient sizes, and relaxation behavior, so it does not automatically improve computational performance.

Binary quadratic optimization uses an objective such as x⊤Qx+c⊤xx^\top Qx+c^\top x. It may be reformulated using product linearizations, but it is not itself a binary linear program. Likewise, restricting variables to two values does not make a problem an instance of convex optimization: the binary feasible domain is generally nonconvex.

Practical limitations

Model quality strongly influences solution difficulty. Weak relaxations, excessive big-M constants, and interchangeable decisions can produce large search trees. Symmetry-breaking constraints may remove equivalent representations, but must preserve at least one representative of every relevant solution class.

Optimization software normally uses floating-point arithmetic and numerical feasibility tolerances. A reported binary value can therefore differ slightly from an exact integer, and optimality may be reported within a specified gap rather than as exact equality of mathematical bounds. Solver status, objective bounds, and tolerances are distinct parts of interpreting a computational result.

Finally, an optimal solution is optimal only for the stated model and data. Binary decisions can represent choices precisely, but the formulation does not by itself account for omitted constraints, uncertain inputs, or objectives that were not encoded.