Binary integer programming is a form of mathematical optimization in which every decision variable is restricted to the values and . 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
Here:
- is the vector of binary decision variables;
- specifies their contributions to the objective function;
- is a constraint matrix;
- 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 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 representing true and representing false.
Selection constraints
For a set of alternatives, common requirements include:
More generally, selects exactly alternatives.
Implication and exclusion
The statement “selecting requires selecting ” becomes
Mutual exclusion becomes
The complement of a binary variable is . Thus a logical clause such as “ is true, or is false, or is true” can be expressed as
This translation connects binary programming with Boolean satisfiability.
Products of binary variables
A product , where and are binary, can be represented exactly by linear constraints:
These constraints force to equal the product even if 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,
enforces when . When , the constraint is intended to become redundant.
The constant , 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 , , and , and require resources , , and , respectively. With a resource budget of , define if project is selected. The model is
Selecting projects and uses the entire budget and yields benefit , 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, would require project whenever project is selected, changing the feasible combinations and potentially the optimum.
Linear relaxation and formulation strength
Replacing the binary restrictions by
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
The binary optimum is , whereas the relaxation has optimum . 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,
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 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:
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 , with , can be encoded using binary variables:
for , together with 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 . 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.