Integer, Binary and Mixed-Integer Programming

Introduction and context

Many operational decisions are indivisible. A warehouse is either opened or not opened; a vehicle is either assigned or not assigned; a project is either selected or rejected; and a worker is scheduled for a particular shift or not. Linear programming is powerful when decision variables can vary continuously, but fractional solutions such as 2.4 warehouses or 0.63 projects may be meaningless. Integer programming extends linear programming by requiring some or all variables to take integer values.

Integer, binary and mixed-integer programming (IP, BIP and MIP) provide a unified language for representing capacity, logical, sequencing, allocation, network and fixed-charge decisions. They are central to facility location, production planning, capital budgeting, workforce scheduling, vehicle routing, supply-chain design and project selection.

The main challenge is computational. The feasible region of a linear program is convex, whereas integrality creates a discrete feasible set. Consequently, solving an integer model requires both mathematical formulation and an algorithm capable of proving optimality or producing a high-quality feasible solution within acceptable time.

Learning objectives

After studying this chapter, you should be able to:

1. Distinguish continuous, integer, binary and mixed-integer variables.
2. Formulate indivisibility, logical implications, mutual exclusion and fixed-charge costs.
3. Build models for facility location, scheduling, routing and capital budgeting.
4. Explain LP relaxation, branch-and-bound, cutting planes and the integrality gap.
5. Interpret solver output, validate solutions and assess managerial limitations.
6. Recognize governance, ethical and implementation issues in discrete optimization.

1. Foundations and terminology

A general mixed-integer linear program can be written as:

Here, x is a vector of continuous variables, y is a vector of integer variables, c and d are objective coefficients, A and G are constraint matrices, and b is a vector of resource limits. The set I identifies variables required to be integer. All relationships are linear, and data are assumed known for the model being solved.

Important special cases are:

An integer variable may represent a count, such as the number of trucks. A binary variable represents a decision with two states: 1 usually means selected, open or active, and 0 means rejected, closed or inactive. A continuous variable may represent tonnes, hours, money or flow.

The objective function measures the criterion to optimize. A maximization model may represent profit, service coverage or contribution; a minimization model may represent cost, distance, lateness or risk. Constraints express scarce resources, demand satisfaction, precedence, policy or physical feasibility.

Integrality and the LP relaxation

The LP relaxation is obtained by removing integer restrictions while retaining all linear constraints. Its optimal objective value provides a bound. For a maximization problem, the LP relaxation value is an upper bound on the integer optimum; for a minimization problem, it is a lower bound. The relaxation is often easier to solve but may produce fractional decisions.

The integrality gap measures the difference between the relaxation and an integer solution. A relative gap may be expressed as:

where z_LP is the relaxation objective value and z_IP is the best known integer objective value. The expression is meaningful when z_IP is nonzero; solvers may use alternative denominators when the objective is zero or negative.

2. Formulation patterns

Good formulation is often more important than selecting a sophisticated algorithm. Variables should have unambiguous meanings, units and domains.

2.1 Indivisible quantities

If xᵢ is the number of units of item i, use:

where ℤ₊ denotes nonnegative integers. If at most one unit can be selected, use xᵢ ∈ {0,1}. If a quantity must be purchased in batches of q units, define an integer variable n and write:

This is preferable to rounding a continuous solution because rounding can violate capacity or demand constraints.

2.2 Logical implications

Let y = 1 if an activity occurs and 0 otherwise. If activity A can occur only when facility B is open, use:

If selecting project A requires project B, the same relationship applies. If selecting A excludes B:

If exactly one of A and B must be selected:

If at least one must be selected:

If activity x can be positive only when y = 1, and x has an upper bound U, use:

This is called an implication or linking constraint. U must be a valid and preferably tight upper bound. An unnecessarily large U creates weak relaxations and numerical difficulties.

2.3 Fixed-charge decisions

Suppose producing any positive amount of product i incurs a fixed setup cost Fᵢ, in addition to variable cost cᵢ per unit. Let xᵢ be production and yᵢ indicate whether production is initiated. A minimization model includes:

The model charges Fᵢ only when yᵢ = 1. The upper bound Uᵢ may be a capacity, demand or technically valid production limit. Fixed-charge models are generally nonconvex in their original economic interpretation and require binary variables for an exact linear representation.

2.4 Minimum activity and semi-continuous variables

If an activity, once activated, must operate at least L and at most U units:

When y = 0, x = 0; when y = 1, L ≤ x ≤ U. This is useful for minimum run lengths, truck loads and production campaigns.

2.5 Either-or constraints and big-M caution

If either constraint 1 or constraint 2 may apply, a binary variable can select the active side. For example, to model x ≤ a or x ≥ b, with b > a, use a binary y and a valid M:

When y = 0, the first inequality imposes x ≤ a and the second is relaxed; when y = 1, the second imposes x ≥ b and the first is relaxed. The value M must be derived from variable bounds. Excessively large M values can cause weak bounds, slow computation and numerical instability. Indicator constraints supplied by modern solvers can be safer, although they are ultimately handled through equivalent computational mechanisms.

3. Core models in operations management

3.1 Facility location and capacity expansion

Let I be customer zones and J candidate facilities. Parameters include demand dᵢ, fixed opening cost fⱼ, unit transportation cost cᵢⱼ, facility capacity Kⱼ and available supply. Let yⱼ = 1 if facility j opens and xᵢⱼ be the quantity shipped from j to customer i. A capacitated facility-location model is:

The capacity-linking constraint prevents shipments from a closed facility. If each customer must be assigned wholly to one facility, replace xᵢⱼ with binary aᵢⱼ and use ∑ⱼaᵢⱼ = 1, with shipment or service constraints linked to aᵢⱼ.

3.2 Scheduling and workforce assignment

Let yₑₜ = 1 if employee e works shift t. If shift t requires rₜ workers and employee e is unavailable in t, set the corresponding variable to zero or impose yₑₜ = 0. A basic model is:

Here cₑₜ is the cost of assigning employee e to shift t and Hₑ is the maximum permitted number of shifts. Rest-period rules can be represented by forbidding incompatible pairs. For example, if employee e cannot work both t and s, add yₑₜ + yₑₛ ≤ 1. Consecutive-shift requirements, skill coverage and fairness constraints can be added, but each should be checked against employment agreements and labor law.

3.3 Capital budgeting

Let yᵢ indicate whether project i is selected, pᵢ its present value, and aᵢₜ its expenditure in period t. If Bₜ is the budget in period t:

Project dependencies are represented by y_A ≤ y_B. If projects A and B are mutually exclusive, y_A + y_B ≤ 1. The model assumes that project values and expenditures are comparable on a consistent basis, normally through discounted cash flow or another approved valuation method.

3.4 Routing and subtour elimination

In a travelling-salesperson formulation, let xᵢⱼ = 1 if the route travels directly from node i to node j. Each node has one incoming and one outgoing arc:

These constraints alone permit disconnected cycles, called subtours. A common Miller–Tucker–Zemlin formulation uses continuous order variables uᵢ and, for nodes i and j other than the depot:

where n is the number of customers and 1 ≤ uᵢ ≤ n − 1. The constraint prevents a selected cycle among a proper subset of customers. Vehicle-routing models additionally require vehicle capacity, route-duration and depot constraints. Care is needed when adapting the formulation to multiple vehicles, time windows or pickup-and-delivery precedence.

4. Solving integer programs

4.1 Branch-and-bound

Branch-and-bound systematically partitions the feasible integer set. The method proceeds as follows:

1. Solve the LP relaxation at the root node.
2. If the solution is integer, it is a candidate incumbent.
3. If a variable y has a fractional value v, create branches y ≤ ⌊v⌋ and y ≥ ⌈v⌉.
4. Solve the relaxation at each child node.
5. Fathom a node if it is infeasible, its bound is no better than the incumbent, or its solution is integer.
6. Continue until every node is fathomed or a prescribed stopping rule is met.

For minimization, a node's lower bound is its LP-relaxation value; a node can be discarded when that lower bound is at least the incumbent objective. For maximization, use upper bounds and discard a node when its bound is no greater than the incumbent. The branching variable and node-selection strategy influence performance but not correctness, provided the tree is completely explored when an exact optimum is claimed.

A solver may report an optimality gap when it stops early. If z_inc is the incumbent and z_bound is the best remaining bound, a common minimization gap is:

The exact convention may differ by software, especially for negative or zero objectives. A reported feasible solution is not automatically proven optimal.

4.2 Cutting planes

A cutting plane is a valid inequality that removes fractional relaxation solutions without excluding any feasible integer solution. If a relaxation yields a fractional point, a solver may add a cut, resolve, and repeat. Examples include cover cuts, clique cuts, Gomory cuts and flow cuts.

The ideal formulation has a strong LP relaxation: its fractional feasible region lies close to the convex hull of feasible integer points. Strong valid inequalities reduce the integrality gap and the number of branch-and-bound nodes. However, too many cuts can increase LP solution time or create numerical problems. Modern commercial and open-source solvers combine presolve, heuristics, branching, cutting planes and primal improvement in a branch-and-cut framework.

4.3 Computational practice

A responsible modeling workflow is:

• define sets, parameters, units and decision variables;
• derive valid bounds before coding;
• formulate the objective and constraints transparently;
• test very small instances by enumeration;
• inspect the LP relaxation and integrality gap;
• validate every returned constraint and business rule;
• record solver version, tolerances, time limit and data;
• distinguish proven optimality from a good feasible solution.

Solver tolerances matter. An integer tolerance may allow a computed value such as 0.9999999 to be treated as 1. A feasibility tolerance may permit tiny constraint violations. These are numerical conventions, not permission to ignore material violations. Post-solution validation should use the organization's operational precision and compliance thresholds.

5. Worked example: fixed-charge production

A firm must supply 80 units. Product A has variable cost 5 per unit, capacity 50 and fixed activation cost 120. Product B has variable cost 7 per unit, capacity 80 and fixed activation cost 40. Let x_A and x_B be production quantities and y_A, y_B binary activation variables.

If only B is opened, x_B = 80 and cost = 7(80) + 40 = 600. If both are opened, the cheapest feasible allocation uses x_A = 50 and x_B = 30, giving cost 5(50) + 7(30) + 120 + 40 = 620. If only A is opened, capacity is insufficient. Therefore the optimal solution is to open B only and produce 80 units, with total cost 600. The example shows why comparing variable costs alone is incorrect: A is cheaper per unit but its fixed charge makes the combined decision less attractive.

6. Illustrative case: regional distribution-centre design

Background

A fictional retail company, Northstar Home, serves four demand regions from three candidate distribution-centre sites. Site 1 has low fixed cost but limited capacity; Site 2 has higher capacity and favorable access to two major regions; Site 3 is expensive but close to remote demand. Management must decide which sites to open and how to allocate regional shipments.

Problem

The company wants to minimize annual fixed facility cost plus transportation cost while meeting each region's demand. It cannot open a site unless its capacity is used through the shipment-linking constraint. Management also requires at least two open sites for resilience.

Analysis and approach

The model uses binary yⱼ variables for opening and continuous xᵢⱼ variables for flows. Demand equalities ensure service, capacity constraints link flows to open sites, and the resilience policy is ∑ⱼ yⱼ ≥ 2. A sensitivity analysis is conducted by changing demand, fixed costs and site capacities. A scenario with a 20% increase in the remote region's demand tests whether the selected network remains feasible.

The LP relaxation may assign fractional opening values, such as y₂ = 0.43. This is useful as a bound but is not an implementable design. Branch-and-bound enforces the actual open/closed decisions. If the best integer solution costs 4.82 million currency units and the best remaining lower bound is 4.79 million, the solution is feasible but not yet proven within a gap of approximately 0.62% using the incumbent denominator.

Outcome and managerial interpretation

The final recommendation should not be based solely on the lowest objective value. Managers should compare service risk, labor availability, emissions, disruption exposure and expansion flexibility. A slightly more expensive network may be preferred if it provides substantial resilience or reduces dependence on a single site. The model should be rerun periodically because demand, freight rates, leases and regulatory constraints change.

Learning points

The case demonstrates the integration of binary location decisions with continuous allocation decisions, the importance of valid capacities, the distinction between a feasible solution and a proof of optimality, and the value of scenario analysis. It also shows that optimization is decision support: governance and managerial judgment remain necessary.

7. Limitations, ethics and contemporary practice

Integer models can be difficult because the number of binary variables may be large, data may be uncertain and logical rules may be incomplete. Deterministic optimization can produce false precision when demand or travel times are forecasts rather than facts. Robust optimization, stochastic programming, rolling-horizon planning and simulation can complement MIP when uncertainty is material.

Fairness and privacy matter in scheduling and allocation. A model that minimizes cost may systematically assign undesirable shifts to a vulnerable group unless fairness constraints and protected attributes are carefully governed. Location models can distribute environmental burdens unevenly across communities. Routing systems using worker or customer data must comply with privacy, labor and data-protection requirements.

Artificial intelligence can assist with demand prediction, parameter estimation, warm starts, heuristic construction and anomaly detection. It should not replace explicit constraints, auditability or human review. Predictions must be separated from optimization assumptions, and model drift must be monitored. In regulated settings, organizations should retain data lineage, objective definitions, constraint rationale, solver logs and approval records.

Best practice includes tight valid bounds, avoidance of arbitrary big-M values, symmetry reduction where appropriate, decomposition for very large structures, warm starts from good feasible solutions, stress testing and independent solution validation. Decomposition methods such as Benders decomposition separate strategic binary decisions from operational recourse; column generation can handle very large route or schedule sets. These are advanced extensions rather than substitutes for a sound base formulation.

Chapter Summary

Integer programming represents decisions that must be whole numbers, while binary programming represents yes/no choices. Mixed-integer programming combines discrete choices with continuous flows, quantities or times. Binary variables express selection, implication, mutual exclusion, activation and fixed charges. Linking constraints connect operational quantities to strategic decisions; tight bounds are essential for computational performance.

Facility location, workforce scheduling, capital budgeting and routing all illustrate the value of MIP. The LP relaxation supplies bounds, while branch-and-bound partitions the search space and cutting planes strengthen relaxations. A solver's feasible solution, optimality proof and reported gap are distinct concepts. Sound practice requires explicit units, validated data, careful numerical tolerances, sensitivity analysis and governance of ethical and regulatory consequences.

Key Terms

Integer variable: A variable restricted to whole-number values.

Binary variable: A variable restricted to 0 or 1.

Mixed-integer program: A model containing both continuous and integer variables.

LP relaxation: The model obtained by removing integer restrictions.

Integrality gap: The difference between a relaxation bound and an integer solution value.

Fixed charge: A cost incurred when an activity is activated, regardless of quantity within its operating range.

Linking constraint: A constraint connecting an activity quantity to a binary activation decision.

Big-M: A sufficiently large valid constant used to model logical conditions.

Indicator constraint: A solver-supported conditional constraint activated by a binary value.

Branch-and-bound: A tree-search method using relaxations and bounds.

Branch-and-cut: Branch-and-bound strengthened with valid inequalities.

Cutting plane: A valid inequality that removes fractional solutions without removing feasible integer solutions.

Incumbent: The best feasible integer solution found so far.

Node: A subproblem in a branch-and-bound tree.

Subtour: A disconnected cycle in a routing solution.

Capacity constraint: A restriction limiting flow, production, service or workload.

Symmetry: Multiple mathematically equivalent representations of the same decision.

Robust optimization: Optimization designed to perform acceptably under uncertainty.

Optimality gap: A measure of the distance between an incumbent and a remaining bound.

Presolve: Automated simplification and strengthening performed before or during solution.

Review Questions

Short Answer Questions

1. Why can a linear-programming solution be operationally infeasible when decisions are indivisible?
2. What is the purpose of a binary linking constraint?
3. Define the LP relaxation and state its bounding role for minimization.
4. Why are excessively large big-M values undesirable?
5. Distinguish a feasible incumbent from a proven optimal solution.

Long Answer Questions

1. Explain the formulation of fixed-charge production, including the role of capacity-linking constraints.
2. Describe branch-and-bound from root relaxation through fathoming, distinguishing minimization and maximization bounds.
3. Develop a capacitated facility-location model and explain the meaning of every variable and constraint.
4. Explain how routing models prevent subtours and why degree constraints alone are insufficient.
5. Discuss how uncertainty, ethics and governance affect the implementation of integer programming in operations management.

Analytical / Application Questions

1. A company must choose projects subject to annual budgets, dependencies and mutual exclusions. Formulate a binary capital-budgeting model and explain how you would test its solution.
2. A hospital needs nurses assigned to shifts with skill coverage, maximum hours and rest requirements. Propose binary variables and at least four classes of constraints.
3. A solver reports an incumbent cost of 1,000 and a best remaining lower bound of 970 for a minimization model. Calculate the relative gap using the incumbent denominator and explain what the result means.

Multiple Choice Questions with Answers

Question 1

Which variable domain represents a yes/no decision?

A. x ≥ 0 continuous

B. x ∈ ℤ₊

C. y ∈ {0,1}

D. y ∈ ℝ

Correct Answer: C. y ∈ {0,1}

Question 2

In a minimization MIP, the LP relaxation objective provides what type of bound?

A. An upper bound on every feasible integer solution

B. A lower bound on the integer optimum

C. The guaranteed integer optimum

D. A feasibility tolerance

Correct Answer: B. A lower bound on the integer optimum

Question 3

Which constraint correctly links production x to an activation binary y with upper bound U?

A. x ≥ Uy

B. x ≤ Uy

C. x = U + y

D. x ≥ U + y

Correct Answer: B. x ≤ Uy

Question 4

If projects A and B are mutually exclusive, which constraint is appropriate?

A. y_A − y_B = 1

B. y_A + y_B ≥ 2

C. y_A + y_B ≤ 1

D. y_A ≤ y_B

Correct Answer: C. y_A + y_B ≤ 1

Question 5

In branch-and-bound, a node can be fathomed when its relaxation is infeasible, its bound is dominated by the incumbent, or its relaxation solution is what?

A. Fractional

B. Integer feasible

C. Unbounded only

D. More expensive than the LP root

Correct Answer: B. Integer feasible

Question 6

A product has variable cost 5, fixed activation cost 120 and 50-unit capacity. What is the cost of producing 50 units after activation?

A. 250

B. 300

C. 370

D. 600

Correct Answer: C. 370

Question 7

Why are degree constraints alone insufficient in a travelling-salesperson model?

A. They prohibit all routes

B. They allow disconnected subtours

C. They require continuous variables

D. They eliminate the depot

Correct Answer: B. They allow disconnected subtours

Question 8

A valid cutting plane should do which of the following?

A. Remove all integer feasible solutions

B. Remove fractional relaxation points while preserving integer feasible points

C. Increase every objective coefficient

D. Relax every capacity constraint

Correct Answer: B. Remove fractional relaxation points while preserving integer feasible points

Question 9

If a minimization incumbent is 1,000 and the best lower bound is 970, what is the incumbent-denominator gap?

A. 0.3%

B. 3%

C. 30%

D. 97%

Correct Answer: B. 3%

Question 10

Which practice generally improves MIP computational performance?

A. Use arbitrary extremely large M values

B. Ignore variable bounds

C. Derive tight valid bounds

D. Round the LP solution without rechecking constraints

Correct Answer: C. Derive tight valid bounds