Integer and Mixed-Integer Optimization

Introduction and Context

Many managerial decisions are not divisible. A firm either opens a distribution centre or does not; a machine is either purchased or not; a project is selected or rejected; a worker is assigned to a shift; and a vehicle route either uses an arc or does not. Continuous linear programming is powerful for allocating divisible resources, but it can produce fractional decisions that have no operational meaning. Integer optimization addresses this problem by requiring selected variables to take integer or binary values.

A mixed-integer optimization model contains both continuous and discrete variables. It can represent capacity expansion, facility location, scheduling, portfolio selection, product configuration, pricing, network design, and many other business analytics applications. Its main difficulty is computational: linear programming is generally tractable at large scale, whereas integer optimization is usually NP-hard in the worst case. Consequently, formulation quality, relaxation strength, valid inequalities, and algorithm design are central to practical performance.

This chapter develops the modelling language of discrete optimization and explains the principal exact solution methods: branch-and-bound and branch-and-cut. It also examines applications and the managerial implications of using optimization models when decisions involve indivisibilities, logical dependencies, uncertainty, and governance constraints.

Learning Objectives

By the end of this chapter, you should be able to:

1. Distinguish continuous, integer, binary, and mixed-integer variables.
2. Formulate logical, fixed-charge, implication, either-or, and piecewise-linear relationships.
3. Explain the role of the LP relaxation and interpret integrality gaps.
4. Construct and interpret valid inequalities.
5. Describe branch-and-bound, branch-and-cut, incumbent solutions, bounds, and optimality gaps.
6. Formulate scheduling, facility-location, and portfolio-selection models.
7. Evaluate modelling assumptions, computational limitations, and governance risks.

1. Discrete Decisions and Model Structure

A generic mixed-integer linear program (MILP) 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 B are constraint matrices, and b is a vector of resource limits. Some integer variables may be binary, meaning yᵢ ∈ {0,1}. The objective and constraints are linear, but the feasible set is discrete in at least some dimensions.

A pure integer program has all decision variables integer. A binary program has only zero–one variables. A mixed-integer program combines continuous, general-integer, and binary variables. The model is a MILP only when all expressions are linear. Products such as xy, where both x and y are decision variables, require nonlinear or reformulated modelling.

1.1 Variable types

The domain is part of the model, not an implementation detail. Omitting integrality can change the meaning of the decision and may lead to infeasible real-world recommendations.

1.2 Binary variables as logical statements

A binary variable y can encode a proposition:

• y = 1: a facility is opened;
• y = 0: the facility is closed.

If x is production and facility capacity is U, the constraint

means that production is impossible when y = 0 and cannot exceed U when y = 1. This is a fundamental linking constraint. The value U should be a valid, tight upper bound rather than an arbitrarily enormous number.

A selection constraint such as “select exactly k projects” is

“At most k” uses ≤ k, while “at least k” uses ≥ k.

1.3 Logical relationships

If project A requires project B, with binary variables y_A and y_B, use

If A and B cannot both be selected, use

If at least one of A and B must be selected, use

If exactly one must be selected, use equality to 1. If activity C can occur only when both A and B occur, use

If C occurs whenever both A and B occur, the converse is also needed:

For a logical “or,” such as C permitted when A or B is selected, the precise formulation depends on whether “or” is inclusive and whether C must be selected. Logical constraints should therefore be translated explicitly rather than relying on informal wording.

2. Fixed Charges and Semi-Continuous Decisions

Many activities incur a fixed cost whenever they are activated, in addition to a variable operating cost. Let x be output, y indicate activation, F be the fixed cost, and c be variable cost per unit. With maximum capacity U:

If a minimum operating level L is required once activated, use

This is a semi-continuous decision: x is either zero or lies between L and U. The fixed-charge formulation is widely used in facility location, transportation, production setup, cloud-resource activation, and retail store selection.

A common modelling error is to include F in the objective without linking it to activity. In that case the solver may pay the fixed cost regardless of whether the operation is used, or may avoid it while still allowing positive flow. The binary variable and linking constraints must enforce the intended economics.

Big-M modelling

A conditional constraint “if y = 1, then aᵀx ≤ b” can be represented as

When y = 1, the original restriction applies. When y = 0, M relaxes it. M must be large enough to preserve every feasible solution, but not so large that it causes numerical instability and a weak relaxation. Deriving M from variable bounds is preferable to guessing.

Modern optimization solvers may provide indicator constraints, which express such logic directly. They can improve readability and sometimes computational performance, although the solver may internally convert them to equivalent formulations.

3. Piecewise-Linear Modelling

Costs and revenues often change by interval. Suppose the cost of quantity x is represented by a convex piecewise-linear function with breakpoints (q₀,c₀), …, (q_K,c_K). A convex-combination formulation uses weights λ_k:

For a convex piecewise-linear function, this formulation is valid when adjacent breakpoints are enforced, commonly through special ordered sets of type 2 (SOS2) or binary interval variables. Without adjacency restrictions, the weights may combine non-neighbouring breakpoints and represent an unintended chord.

An incremental formulation uses segment variables z_k and binary variables y_k. If segment k has length Δ_k and slope s_k, then

Additional ordering constraints, such as y_{k+1} ≤ y_k, ensure that earlier segments are filled before later segments. This formulation is especially useful when the marginal cost changes by successive blocks.

Piecewise-linear models are approximations when the underlying function is nonlinear. Breakpoints should be selected using business knowledge and error analysis. A model that approximates a steep penalty poorly may produce systematically misleading decisions.

4. Relaxations, Bounds, and the Integrality Gap

The LP relaxation of a MILP removes integer restrictions while retaining linear constraints. For a maximization problem, the relaxation gives an upper bound on the integer optimum; for a minimization problem, it gives a lower bound. The relaxed solution may be fractional and operationally infeasible, but it is computationally valuable.

For a maximization problem, if z_IP is the integer optimum and z_LP is the LP-relaxation optimum, then

For minimization, z_LP ≤ z_IP. The integrality gap can be expressed, for a positive minimization optimum, as

or, when the integer optimum is unknown during solution, by comparing an incumbent and a bound. Definitions vary across software and problem types, so the reporting convention must be stated.

A relaxation is strong when its bound is close to the integer optimum. Strong formulations reduce the search required by branch-and-bound. Adding valid inequalities can strengthen a relaxation without removing any feasible integer solution.

Example: a weak formulation

Suppose two facilities have binary opening variables y₁ and y₂, and demand allocation x₁ and x₂. If demand is 100 and each facility has capacity 100, the constraints

are correct. In the relaxation, y₁ = y₂ = 0.5 and x₁ = x₂ = 50 is feasible. If opening costs are large, this fractional solution may be substantially more attractive than any real solution. Tighter capacity, demand, and assignment inequalities can improve the bound.

5. Valid Inequalities and Formulation Strength

A valid inequality is satisfied by every feasible integer solution. It may cut off fractional relaxation points while preserving all legitimate integer solutions. Examples include:

• Cover inequalities in knapsack problems;
• Clique inequalities for mutually incompatible selections;
• Subtour-elimination constraints in routing;
• Symmetry-breaking constraints;
• Strengthened linking and capacity constraints.

If a knapsack constraint is ∑ᵢ aᵢyᵢ ≤ b and a subset C has ∑_{i∈C} aᵢ > b, then all items in C cannot be selected. The cover inequality

is valid. A cover is minimal if no proper subset is itself a cover; minimal covers often yield more useful cuts.

Symmetry occurs when multiple solutions are equivalent under relabelling, such as identical machines or facilities. A constraint such as

can force identical facilities to be opened in a canonical order, reducing duplicate search. It is valid only when the facilities are genuinely interchangeable.

Good formulation practice includes scaling coefficients, tightening variable bounds, eliminating redundant variables, avoiding unnecessary big-M values, and testing the LP relaxation before full solution.

6. Branch-and-Bound and Branch-and-Cut

Branch-and-bound solves a discrete model by systematically partitioning the feasible region. At each node:

1. Solve a relaxation.
2. Obtain a bound from the relaxation.
3. Fathom the node if it is infeasible, its bound is no better than the incumbent, or its relaxation solution is integral.
4. Otherwise branch on a fractional variable, creating subproblems such as y_j ≤ 0 and y_j ≥ 1.

The incumbent is the best feasible integer solution found. The global bound is obtained from active nodes. For a maximization problem, if the best active-node upper bound is U and the incumbent value is L, an optimality gap may be reported as

This is a common practical convention, not a universal definition. For minimization, the analogous expression uses the incumbent upper bound and relaxation lower bound.

Branch-and-cut adds valid inequalities, called cuts, during the search. A cut removes fractional solutions from a relaxation but does not remove feasible integer solutions. Commercial solvers combine presolve, heuristics, cutting planes, branching rules, primal improvement, and parallel search.

Branching decisions may be selected using fractional closeness, estimated bound improvement, pseudo-costs, or strong branching. Good branching can dramatically reduce the tree. Heuristics may find high-quality incumbents early, which improves pruning even before proving optimality.

A solver result must be interpreted carefully:

A time-limit solution is not automatically optimal. The incumbent, bound, gap, runtime, and solver tolerances should be recorded.

7. Applications

7.1 Facility location

Let I be candidate facilities and J be customers. Let y_i indicate whether facility i opens, x_ij be the quantity shipped from i to j, f_i be the opening cost, c_ij be unit shipping cost, d_j be customer demand, and u_i be facility capacity. A capacitated facility-location model is

The first constraint serves all demand. The second prevents shipments from closed facilities and imposes capacity. If customers must be assigned to one facility rather than split, introduce binary assignment variables a_ij and use ∑ᵢ a_ij = 1 and x_ij ≤ d_j a_ij.

The model supports strategic trade-offs between fixed infrastructure cost and variable distribution cost. Extensions include multiple products, service-level limits, opening budgets, emissions, resilience requirements, and uncertain demand.

7.2 Scheduling

Suppose jobs j ∈ J must be assigned to one of several machines m ∈ M. Let x_jm = 1 if job j is assigned to machine m, and p_j be its processing time. Assignment requires

For a basic makespan model, let C be the maximum completion time. A capacity-based approximation is

This is valid when each machine processes its assigned jobs sequentially and no release dates or precedence interactions alter the total load. To model job sequencing exactly, pairwise ordering variables may be required. If z_jk,m = 1 means job j precedes job k on machine m, disjunctive constraints can be written using a carefully bounded M. Scheduling models can also include setup times, worker availability, overtime, deadlines, and sequence-dependent costs.

7.3 Portfolio selection

Let y_i be a binary variable indicating whether asset i is selected and w_i be its continuous portfolio weight. With expected return r_i, transaction or selection cost f_i, and total investment normalized to 1:

Here U_i is an investment upper bound and K is the maximum number of holdings. The model is mixed-integer because weights are continuous but selection is discrete. If risk is represented by a quadratic variance term, the problem becomes a mixed-integer quadratic program rather than a MILP. A linear risk proxy, such as scenario loss or absolute deviation, can preserve linearity.

Expected returns and risk estimates are uncertain. A mathematically optimal portfolio under unstable estimates may be economically fragile, so robust constraints, turnover limits, stress tests, and governance review are important.

8. Illustrative Case: Regional Distribution Network

Background

A retailer must decide which of three candidate fulfilment centres to open. Annual demand is 900 units, distributed among three customer zones. Facility capacities are 600, 500, and 700 units, with fixed annual costs of 24, 18, and 20 monetary units respectively. Shipping costs differ by origin and destination. The retailer wants to minimize fixed opening and shipping costs while serving all demand.

Problem formulation

Let y_i indicate opening facility i and x_ij be units shipped from facility i to zone j. The facility-location model above is used with demand constraints, capacity-linking constraints, nonnegative shipment variables, and binary opening variables.

Suppose a preliminary solution opens facilities 2 and 3, with total shipping cost 31 and fixed cost 38. Its objective is therefore 69 monetary units. A feasible solution opening facilities 1 and 2 has shipping cost 36 and fixed cost 42, giving 78. The first solution is better among these two, but it is not necessarily optimal until the solver proves that no other feasible combination and allocation has objective below 69.

Relaxation and interpretation

In the LP relaxation, y variables may be fractional. A solution such as y₁ = 0.4 and y₂ = 0.8 can partially exploit capacity at a fractional fixed cost. This is not an implementable network, but it gives a lower bound for the minimization problem. If the relaxation objective is 61 and the best integer solution is 69, the relative gap using the incumbent denominator is

The solver branches on a fractional opening variable, for example y₂. One child imposes y₂ = 0, and the other imposes y₂ = 1. Each child is solved or further branched. If a node's lower bound is at least 69, it cannot improve the incumbent and is pruned.

Managerial analysis

The mathematical model identifies a cost-efficient network, but management should examine demand uncertainty, facility lead times, labour availability, lease conditions, and service resilience. If a single facility failure would create unacceptable disruption, a redundancy constraint may be required. For example, a customer zone could be required to have access to at least two opened facilities, subject to appropriate capacity definitions. Such a constraint increases cost but may improve continuity.

Learning points

The case illustrates four principles: fixed costs require binary activation variables; capacity must be linked to activation; a feasible solution is not necessarily proven optimal; and the objective should include operational risks that matter to the business, not merely visible monetary costs.

9. Challenges, Governance, and Contemporary Practice

Computational challenges

Integer models may have enormous search trees. Difficulty is affected by the number of binaries, weak relaxations, symmetry, large coefficient ranges, poor big-M values, and highly constrained or highly degenerate structure. More variables do not always imply a harder model; a strong formulation with many variables may solve faster than a compact but weak formulation.

Data and modelling risk

An optimizer can produce a precise answer to an incorrectly specified problem. Demand forecasts, costs, capacities, correlations, processing times, and service requirements should be validated. Analysts should conduct sensitivity analysis by varying key parameters and identify decisions that remain stable.

Ethical and regulatory considerations

Discrete optimization may allocate staff, credit, healthcare resources, or delivery access. If protected characteristics are correlated with model inputs, an apparently neutral objective can generate discriminatory outcomes. Governance should include documented objectives, data provenance, fairness checks, explainable constraints, human review, audit trails, and an appeal process where decisions affect individuals. Regulatory requirements may also mandate record retention, model validation, or restrictions on automated decisions.

AI and solver technology

Machine learning can improve forecasts, parameter estimation, branching guidance, and heuristic solution construction, but it does not remove the need for a valid optimization model. Learned predictions should be separated from optimization assumptions, monitored for drift, and tested under out-of-distribution scenarios. Optimization software increasingly supports automatic reformulation, conflict refinement, decomposition, parallel search, and explainable solution diagnostics. These tools assist modelling but do not replace professional judgement.

Best practices

1. State the decision, objective, units, horizon, and feasibility assumptions clearly.
2. Use the smallest valid upper bounds and derive big-M values analytically.
3. Test the model on small instances whose solutions can be checked independently.
4. Inspect the LP relaxation and integrality gap.
5. Add valid inequalities only when their validity is established.
6. Use realistic tolerances and report incumbent, bound, gap, and status.
7. Perform sensitivity, scenario, and stress analysis.
8. Separate mathematical optimality from business acceptability.
9. Document data sources, model versions, solver settings, and human overrides.
10. Reassess the model when operating conditions or regulations change.

Chapter Summary

Integer and mixed-integer optimization model decisions that are indivisible, conditional, or combinatorial. Binary variables represent selection and logic; integer variables represent counts; continuous variables represent divisible quantities. Linking constraints connect operating levels to activation decisions, while fixed-charge and semi-continuous formulations capture setup economics. Piecewise-linear formulations approximate changing costs and revenues.

The LP relaxation supplies bounds but may contain fractional decisions. Integrality gaps measure the distance between relaxed and integer solutions. Strong formulations, tight bounds, valid inequalities, symmetry breaking, and good branching improve computational performance. Branch-and-bound partitions the feasible region, while branch-and-cut strengthens relaxations during the search. Solver status and optimality gaps must be interpreted rather than assumed.

Facility location, scheduling, and portfolio selection demonstrate the broad applicability of MILP. In professional practice, model quality depends not only on algorithms but also on data validity, uncertainty analysis, risk representation, ethical safeguards, documentation, and managerial review.

Key Terms

Integer variable: A decision variable restricted to integer values.

Binary variable: A variable restricted to 0 or 1.

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

LP relaxation: The model obtained by removing integer restrictions.

Integrality gap: The difference between an integer optimum and its relaxation bound.

Linking constraint: A constraint connecting an activity variable to an activation variable.

Fixed charge: A cost incurred when an activity is activated, regardless of volume.

Semi-continuous variable: A variable equal to zero or bounded within a positive interval.

Big-M: A sufficiently large constant used to model conditional logic.

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

Piecewise-linear function: A function represented by connected linear segments.

Valid inequality: A constraint satisfied by every feasible integer solution.

Cover inequality: An inequality derived from a subset that cannot be selected together.

Symmetry breaking: Constraints that remove equivalent representations of the same solution.

Relaxation bound: An objective bound obtained from a less restrictive model.

Incumbent: The best feasible integer solution currently known.

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

Branch-and-cut: Branch-and-bound enhanced with valid cutting inequalities.

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

Presolve: Automated simplification and tightening performed before or during optimization.

Review Questions

Short Answer Questions

1. What distinguishes a binary variable from a general integer variable?
2. Why is the constraint x ≤ Uy used in fixed-charge models?
3. Define the LP relaxation of a mixed-integer program.
4. What is the purpose of a valid inequality?
5. Why can an excessively large big-M value be harmful?

Long Answer Questions

1. Explain how binary variables model logical relationships, using examples of implication, mutual exclusion, and exact selection.
2. Describe branch-and-bound, including relaxation bounds, incumbents, branching, and fathoming.
3. Compare breakpoint and incremental formulations for piecewise-linear functions.
4. Formulate and explain a capacitated facility-location model.
5. Discuss why a solver's “feasible” result should not be interpreted as a proof of optimality.

Analytical / Application Questions

1. A firm pays a fixed setup cost whenever production is positive and must produce between 200 and 1,000 units when active. Formulate the binary-continuous constraints and explain each bound.
2. A portfolio may contain at most five of ten assets, with each selected asset receiving between 4% and 30% of investment. Formulate the selection and linking constraints.
3. A minimization model has an incumbent value of 1,250 and a proven lower bound of 1,190. Calculate the incumbent-based relative optimality gap and explain what it means for management.

Multiple Choice Questions with Answers

Question 1

Which variable domain represents a yes-or-no decision?

A. x ≥ 0

B. x ∈ ℤ

C. x ∈ {0,1}

D. l ≤ x ≤ u with x continuous

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

Question 2

In the constraint 0 ≤ x ≤ Uy, what does y = 0 imply?

A. x must equal U

B. x must equal 0

C. x may exceed U

D. x must be fractional

Correct Answer: B. x must equal 0

Question 3

For a maximization MILP, the LP relaxation objective is generally what relative to the integer optimum?

A. A lower bound

B. An upper bound

C. Always equal

D. Unrelated

Correct Answer: B. An upper bound

Question 4

Which constraint models mutual exclusion of binary decisions y₁ and y₂?

A. y₁ + y₂ = 2

B. y₁ − y₂ = 1

C. y₁ + y₂ ≤ 1

D. y₁ + y₂ ≥ 1

Correct Answer: C. y₁ + y₂ ≤ 1

Question 5

What is the main purpose of a valid inequality?

A. To remove feasible integer solutions

B. To strengthen the relaxation without removing feasible integer solutions

C. To make all variables continuous

D. To guarantee a unique objective value

Correct Answer: B. To strengthen the relaxation without removing feasible integer solutions

Question 6

In branch-and-bound, a node can be pruned when its bound is not better than the incumbent because

A. the node contains no variables

B. it cannot produce an improved feasible solution

C. the LP relaxation is always infeasible

D. all binary variables have already been removed

Correct Answer: B. it cannot produce an improved feasible solution

Question 7

A fixed-charge objective usually contains which expression?

A. F + cx regardless of activation

B. Fy + cx

C. F/x + c

D. F − cy only

Correct Answer: B. Fy + cx

Question 8

If a minimization model has incumbent 100 and lower bound 90, the incumbent-based gap is

A. 5%

B. 9%

C. 10%

D. 90%

Correct Answer: C. 10%

Question 9

Which application most directly uses binary facility-opening variables and continuous shipment variables?

A. Capacitated facility location

B. Simple mean calculation

C. Unconstrained regression

D. Inventory counting only

Correct Answer: A. Capacitated facility location

Question 10

Why should big-M values be as tight as valid bounds permit?

A. To increase the number of fractional solutions

B. To weaken the relaxation deliberately

C. To reduce numerical problems and strengthen the relaxation

D. To eliminate all binary variables

Correct Answer: C. To reduce numerical problems and strengthen the relaxation