Combinatorial Optimization and Decision Support

Introduction

Many managerial decisions involve selecting, sequencing, assigning, or routing discrete alternatives. Examples include assigning employees to shifts, choosing delivery routes, selecting projects, balancing an investment portfolio, and allocating limited inventory across facilities. These are combinatorial optimization problems: the number of possible decisions grows rapidly as the number of choices increases.

Quantum computing is relevant because several quantum methods naturally address difficult discrete optimization problems. Quantum annealing seeks low-energy solutions of an Ising or QUBO model; the Quantum Approximate Optimization Algorithm (QAOA) uses a gate-based quantum computer; and hybrid solvers combine classical optimization with quantum subroutines. These methods do not automatically produce better business decisions. Their value must be assessed against solution quality, computational cost, data quality, interpretability, constraints, and operational feasibility.

This chapter develops practical formulations for routing, scheduling, allocation, portfolio selection, and supply-chain decisions. It also explains how managers should evaluate annealing, QAOA, and hybrid approaches.

Learning objectives

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

1. Explain combinatorial optimization, binary variables, QUBO models, and Ising models.
2. Translate business objectives and constraints into quadratic penalty formulations.
3. Formulate routing, scheduling, allocation, portfolio, and supply-chain problems.
4. Distinguish quantum annealing, QAOA, and hybrid solution workflows.
5. Interpret feasibility, objective value, scalability, and operational risk.
6. Evaluate whether a quantum approach is appropriate for managerial decision support.

1. Combinatorial optimization as a decision model

A decision model has four main elements:

• Decision variables: choices controlled by the organization.
• Objective function: a measure to minimize or maximize.
• Constraints: conditions that feasible decisions must satisfy.
• Parameters: known or estimated data, such as costs, distances, demand, or processing times.

A general binary optimization model can be written as:

Here, x_i indicates whether option i is selected, f(x) is the objective, and g_r(x) ≤ b_r represents constraint r. Binary variables are especially useful when a decision is yes/no, such as whether a vehicle uses an arc or whether a project is selected.

A common quadratic objective is:

The coefficients h_i are linear biases and J_ij represent pairwise interactions. The units of all terms must be consistent; for example, every term may represent dollars or a normalized cost. A lower value is conventionally treated as better in a QUBO minimization model.

1.1 QUBO formulation

A Quadratic Unconstrained Binary Optimization model is:

x is a binary vector and Q is a coefficient matrix. Depending on convention, off-diagonal coefficients may be stored once or twice. Therefore, the implementation convention must be documented. If a symmetric matrix is used, the cross-term contribution is represented through both Q_ij and Q_ji.

Constraints are incorporated into the objective using penalty terms. If the desired constraint is g(x)=0, a quadratic penalty is:

where P > 0 is a penalty weight. Any infeasible solution incurs a positive cost. The penalty should be large enough to discourage violations but not so large that it overwhelms meaningful differences in the original objective.

For an inequality such as ∑ᵢxᵢ ≤ 1, a slack variable may be required. For a simple one-selection constraint, the penalty is:

Expanding the square produces linear and quadratic terms because xᵢ² = xᵢ for binary variables.

1.2 Ising formulation

An Ising model uses spin variables s_i ∈ {−1,+1}:

The objective is to find a spin assignment with minimum energy. QUBO and Ising variables are related by:

Thus, a binary zero becomes spin −1 and a binary one becomes spin +1. Substitution converts one representation into the other, although the resulting coefficients and constant offset change. The constant offset does not affect which solution is optimal.

1.3 Penalty selection

Penalty calibration is a central modelling issue. Suppose the original objective is cost C(x) and a constraint violation has penalty P. A practical starting rule is to choose P larger than the greatest plausible improvement in C(x) obtained by violating that constraint. This is a sufficient heuristic in many finite binary models, but it is not universally optimal.

Very small penalties produce attractive but infeasible solutions. Excessively large penalties create poor numerical scaling and can make the original business objective insignificant. Penalties should be tested through sensitivity analysis, and the final solution must always be checked against the original constraints.

2. Core application models

2.1 Assignment and allocation

Suppose workers i = 1,…,n are assigned to tasks j = 1,…,m. Let x_ij=1 when worker i performs task j, and let c_ij be the cost or negative benefit of that assignment.

The assignment objective is:

If every worker receives one task and every task receives one worker, use:

The full QUBO is the assignment cost plus these penalties. If a worker cannot perform a task, the corresponding variable can be removed or assigned a large cost. Capacity allocation follows the same pattern, but a capacity constraint such as ∑ᵢaᵢxᵢ ≤ B generally requires slack variables or a carefully designed encoding.

2.2 Scheduling

Scheduling assigns jobs to time slots or machines. Let x_jt=1 if job j starts in time slot t. The requirement that job j starts exactly once is:

To prevent two jobs from occupying the same machine and time slot, use:

For a soft preference, such as avoiding late completion, add a weighted cost:

where w_jt is the lateness, overtime, energy, or dissatisfaction cost of assigning job j to slot t. Hard constraints receive sufficiently strong penalties; preferences should normally receive smaller business weights.

Dependencies require additional modelling. If job A must precede job B, assignments that place B too early can be penalized. In practice, time-indexed models are easiest to explain, while precedence and machine-dependent processing times can substantially increase the number of variables.

2.3 Routing and vehicle routing

For a travelling-salesperson-style route, let x_ij=1 when the route travels directly from location i to location j. Let d_ij be distance or travel cost.

The travel objective is:

Each location must have one outgoing and one incoming arc:

These conditions alone can produce disconnected subtours. A subtour-elimination mechanism is therefore required. One option is to use position variables y_ik, where location i occupies route position k, with exactly one location per position and one position per location. Another option is to add explicit subtour constraints iteratively in a classical preprocessing loop. Vehicle capacity, time windows, multiple vehicles, and depot-return conditions add further variables and penalties.

A routing model should distinguish distance, travel time, fuel, emissions, and service-level costs. A shortest route is not necessarily the best managerial route if it violates delivery windows or creates excessive driver overtime.

2.4 Portfolio selection

Let x_i ∈ {0,1} indicate whether asset i is selected. Let r_i be expected return and σ_ij be the covariance between assets i and j. A binary mean–variance model can be written as:

Here 0 ≤ λ ≤ 1 controls the trade-off between risk and return. The covariance matrix must use consistent return units, such as decimal monthly returns; σ_ij then has squared-return units, while r_i has return units. In practice, risk and return should be scaled or calibrated before combining them.

To select exactly k assets, add:

Budget, sector, liquidity, and regulatory constraints can be represented similarly. A continuous portfolio-weight model is not directly binary; it requires discretization or a different optimization formulation. Discretization introduces approximation error and should be reported.

2.5 Supply-chain decisions

Supply-chain problems often combine facility selection, supplier allocation, production, inventory, transportation, and service levels. A simplified binary facility-location model uses y_j=1 if facility j opens and x_ij=1 if customer i is served by facility j. With opening cost F_j and service cost c_ij, the objective is:

Each customer must be assigned once:

A customer can be assigned only to an open facility. This implication can be penalized using:

Capacity constraints such as total demand assigned to facility j not exceeding K_j require either slack variables, binary capacity encodings, or decomposition. Real supply chains also include uncertain demand, lead times, disruptions, and contractual requirements. A deterministic QUBO is therefore often one scenario within a broader stochastic or robust planning process.

3. Quantum solution approaches

3.1 Quantum annealing

Quantum annealing maps an Ising objective to a physical or simulated energy landscape. A system is initialized in an easily prepared state and gradually changes toward a problem Hamiltonian whose low-energy states encode good solutions. Repeated runs generate samples rather than a guaranteed exact optimum.

Important operational terms include:

• Embedding: mapping the logical problem graph onto available hardware connectivity.
• Chain: physical variables used to represent one logical variable.
• Chain break: disagreement among physical qubits representing one logical variable.
• Anneal schedule: the time-dependent progression from initial to problem Hamiltonian.
• Sample: one candidate solution returned by a run.

Embedding overhead can increase the number of physical qubits and introduce noise. A low-energy sample may still violate constraints if penalties are poorly calibrated. Post-processing, repair heuristics, and classical local search are therefore common.

3.2 QAOA

QAOA is a gate-based variational algorithm. A cost Hamiltonian encodes the QUBO, while a mixer Hamiltonian explores candidate states. At depth p, a parameterized state is prepared using alternating cost and mixer operators:

Here C is the cost Hamiltonian, B is usually a mixing Hamiltonian, γ_l and β_l are variational parameters, and n is the number of logical qubits. A classical optimizer adjusts these parameters using measured objective values.

Increasing p can improve expressiveness but increases circuit depth and susceptibility to noise. QAOA is not automatically superior to classical methods; its practical performance depends on hardware quality, connectivity, parameter optimization, and problem structure.

3.3 Hybrid solvers

A hybrid workflow divides responsibility between classical and quantum computation:

Figure: A hybrid workflow from managerial data to validated decision support.

A hybrid system may use classical preprocessing, quantum sampling, classical repair, and conventional benchmarking. This is often the most realistic approach at diploma level because business models are larger and messier than current quantum hardware can handle directly.

4. Evaluating solution quality

A solver should not be evaluated only by whether it is labelled “quantum.” Important measures include:

• Feasibility rate: proportion of returned samples satisfying all hard constraints.
• Objective value: original business cost or benefit, excluding artificial penalties.
• Optimality gap: difference between a candidate and a trusted lower or upper bound. For minimization, a common relative gap is (z − z*)/|z*| when z* ≠ 0, where z is the candidate value and z* is a benchmark or known optimum.
• Time to solution: includes modelling, compilation, queueing, execution, decoding, and repair where relevant.
• Robustness: stability under changed demand, costs, and solver seeds.
• Energy and financial cost: hardware access, cloud execution, and operational consequences.
• Interpretability: ability to explain why a decision was recommended.

A fair comparison uses the same data, constraints, stopping rule, and post-processing for quantum and classical methods. Small benchmark instances should usually be solved exactly to establish a reference optimum. Larger instances can be compared with strong classical heuristics, mixed-integer programming, local search, or constraint programming.

5. Illustrative case: regional delivery planning

Background

The following is a fictional illustrative case. A food distributor serves four retail outlets from one depot. Each outlet must be visited once, and the company wants to minimize travel distance while avoiding disconnected routes.

Problem

The locations are depot 0 and stores 1–4. A distance matrix is available, with d_ij=d_ji and d_ii=0. The company initially considers arc variables x_ij, where x_ij=1 means that the vehicle travels from i to j.

Analysis and formulation

The travel objective is ∑_i≠jd_ijx_ij. Incoming and outgoing degree penalties ensure that every location has exactly one predecessor and successor. However, the model could return two cycles, for example depot–1–depot and 2–3–4–2. Such a result is infeasible for one vehicle even though every location has the correct degree.

The planning team therefore uses position variables y_ik, where k=0,…,4 is the position in a five-stop tour. They add:

The first term places each location in one position; the second fills each position with one location. Consecutive-position transition variables or equivalent quadratic couplings connect the selected positions to travel distances. The depot is fixed at the first and last position through hard fixing or strong penalties.

Approach

The distributor compares three methods:

1. A classical exact solver for a small reference instance.
2. A quantum annealing sampler using several penalty values and classical repair.
3. A hybrid solver that decomposes the route and applies local improvement.

Each candidate is checked for duplicate visits, depot return, subtours, maximum route length, and delivery-time feasibility. The original distance is recalculated after penalties are removed.

Outcome

The quantum sampler produces several low-energy routes, but some contain broken chains and infeasible position assignments. After repair, the best route matches the classical reference on the small instance. On a larger instance, the hybrid method finds a feasible route quickly, but its distance is not proven optimal. Management therefore adopts the hybrid solution as a planning recommendation rather than as an unquestionable optimum.

Learning points

The case demonstrates four principles. First, the business constraints determine the model structure. Second, a low QUBO energy is not sufficient evidence of operational feasibility. Third, subtour prevention must be explicit. Fourth, the correct managerial comparison is against validated alternatives, not against an abstract quantum label.

6. Managerial, ethical, and governance considerations

Quantum optimization changes neither the responsibility of decision makers nor the need for accountable governance. Input data may contain employee performance records, customer locations, supplier prices, or investment information. Access controls, encryption, retention policies, and contractual review are essential when cloud quantum services are used.

Optimization can also embed unfairness. A scheduling model that minimizes labour cost may systematically assign undesirable shifts to a particular group. A routing model that minimizes distance may reduce service quality in remote communities. Managers should identify affected stakeholders, test outcomes across groups, and include fairness or service constraints where appropriate.

Models should be auditable. Document the data source, variable definitions, penalty values, solver settings, random seeds where applicable, feasibility checks, and approval authority. Human review remains necessary when data are uncertain or when decisions affect safety, employment, access to essential goods, or regulated financial activity.

7. Best-practice implementation workflow

A professional implementation normally follows these steps:

1. Define the business decision and the unit of value.
2. Separate hard constraints from preferences.
3. Choose binary variables that have clear operational meaning.
4. Build and test a classical mathematical model first.
5. Convert constraints into QUBO penalties or use a solver-supported constrained formulation.
6. Scale coefficients while preserving relative priorities.
7. Test small instances exhaustively or with an exact method.
8. Run quantum, classical, and hybrid methods under comparable conditions.
9. Decode samples, repair violations, and recompute the original objective.
10. Conduct sensitivity, stress, fairness, and governance checks.
11. Present several feasible alternatives when uncertainty is material.
12. Monitor decisions in operation and update the model as conditions change.

The most important practical skill is not merely writing a QUBO. It is translating a managerial problem into a defensible, testable, and actionable decision process.

Challenges and limitations

Current quantum optimization faces important limitations. Available devices have restricted connectivity, finite precision, noise, and limited effective problem size. Embedding can increase physical resource requirements. Penalty tuning is problem-dependent. QAOA circuits become difficult to execute as depth increases, while parameter optimization can be unstable. Sampling methods provide candidate solutions but generally do not prove global optimality.

Business data introduce additional difficulties. Demand forecasts may be wrong, travel times may vary, and correlations in financial data may be estimated poorly. A sophisticated optimizer applied to unreliable data can produce a precisely calculated but inappropriate decision. Finally, total workflow cost—not only quantum processing time—may dominate any claimed advantage.

Contemporary developments

Research and industry practice increasingly emphasize hybrid decomposition, warm starts, adaptive penalty strategies, error mitigation, and problem-specific mixers. Quantum-inspired classical algorithms, tensor methods, and specialized hardware may provide value even when fault-tolerant quantum computers are unavailable. The practical question is therefore broader than “Can quantum computers solve this problem?” It is “Does a quantum-enabled workflow improve the quality, speed, cost, or resilience of a real decision compared with credible alternatives?”

Chapter Summary

Combinatorial optimization represents discrete managerial choices through variables, objectives, and constraints. QUBO models express binary decisions using linear and quadratic terms, while Ising models use spins in {−1,+1}. Constraints are commonly enforced through quadratic penalties, but penalty calibration and post-solution feasibility checks are essential.

Routing, scheduling, allocation, portfolio selection, and supply-chain planning can all be formulated using these ideas. Quantum annealing samples low-energy states, QAOA uses parameterized gate circuits, and hybrid solvers combine quantum and classical methods. Evaluation must consider feasibility, original objective value, optimality gap, runtime, robustness, cost, interpretability, and governance. Quantum methods are decision-support tools, not substitutes for sound modelling, reliable data, ethical review, or managerial judgement.

Key Terms

QUBO: Quadratic Unconstrained Binary Optimization using variables in {0,1}.

Ising model: An optimization model using spin variables in {−1,+1}.

Binary variable: A variable restricted to zero or one.

Spin variable: A variable restricted to −1 or +1.

Objective function: A mathematical measure to minimize or maximize.

Constraint: A condition that feasible decisions must satisfy.

Penalty term: An added objective term that discourages constraint violations.

Penalty weight: The coefficient controlling the severity of a violation.

Combinatorial optimization: Optimization over a finite or discrete set of alternatives.

Embedding: Mapping a logical problem onto hardware connectivity.

Chain: Physical variables representing one logical variable.

Chain break: Inconsistent values among physical variables in a chain.

Quantum annealing: An energy-minimization approach based on an evolving quantum system.

QAOA: A gate-based variational algorithm for approximate combinatorial optimization.

Hybrid solver: A workflow combining classical and quantum computation.

Feasibility: Satisfaction of all required constraints.

Optimality gap: Difference between a candidate solution and a reference bound or optimum.

Subtour: A disconnected cycle in a routing solution.

Mean–variance model: A portfolio model balancing expected return and covariance-based risk.

Decision support: Analytical assistance for human managerial decisions.

Review Questions

Short Answer Questions

1. What is the difference between a QUBO variable and an Ising spin variable?
2. Why are penalty terms used in an unconstrained QUBO model?
3. What is a subtour in vehicle routing?
4. Name three criteria, apart from objective value, for evaluating a quantum optimization solver.
5. Why must a QUBO solution be checked against the original business constraints?

Long Answer Questions

1. Explain how an assignment problem can be transformed into a QUBO, including the role of one-selection constraints.
2. Compare quantum annealing, QAOA, and hybrid solvers in terms of representation, execution, and practical limitations.
3. Describe how a portfolio-selection problem can combine return, covariance risk, and a cardinality constraint.
4. Explain why routing models require subtour prevention in addition to incoming and outgoing degree constraints.
5. Discuss ethical, governance, and data-quality risks in quantum-enabled managerial decision support.

Analytical / Application Questions

1. A manager must select exactly three projects from a set of binary project variables. Write a quadratic penalty enforcing this requirement and explain how it would be combined with project costs and benefits.
2. Design a QUBO formulation for assigning four employees to four shifts when each employee must receive one shift and each shift must be filled once. Identify the principal variables, objective coefficients, and penalty terms.
3. A hybrid solver returns a very low-energy portfolio that violates its budget constraint. Diagnose at least three possible causes and propose a validation and remediation procedure.

Multiple Choice Questions with Answers

Question 1

Which transformation connects a binary QUBO variable to an Ising spin?

A. sᵢ = xᵢ/2

B. sᵢ = 2xᵢ − 1

C. sᵢ = xᵢ + 1

D. sᵢ = 1 − 2xᵢ²

Correct Answer: B. sᵢ = 2xᵢ − 1

Question 2

What is the main purpose of the term P(∑ᵢxᵢ − k)²?

A. To enforce selection of exactly k items

B. To maximize the number of selected items without limit

C. To remove all quadratic interactions

D. To convert spins into continuous variables

Correct Answer: A. To enforce selection of exactly k items

Question 3

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

A. They prohibit every route

B. They eliminate distance data

C. They may allow disconnected subtours

D. They require continuous variables

Correct Answer: C. They may allow disconnected subtours

Question 4

In a binary portfolio model, what does σᵢⱼ normally represent?

A. Asset purchase price

B. Covariance between asset returns

C. Number of available shares

D. A routing distance

Correct Answer: B. Covariance between asset returns

Question 5

Which statement best describes QAOA?

A. A purely classical sorting algorithm

B. A gate-based variational quantum algorithm

C. A method that requires no objective function

D. A fixed classical penalty rule

Correct Answer: B. A gate-based variational quantum algorithm

Question 6

What is a chain break in quantum annealing?

A. A violated financial budget

B. A disconnected depot

C. Disagreement among physical variables representing one logical variable

D. A classical proof of optimality

Correct Answer: C. Disagreement among physical variables representing one logical variable

Question 7

For minimization, which result is generally preferable when all constraints are satisfied?

A. A higher original business cost

B. A lower original business cost

C. A larger penalty regardless of feasibility

D. A solution with the most variables

Correct Answer: B. A lower original business cost

Question 8

What is a major danger of choosing penalties that are too small?

A. All variables become continuous

B. Feasible solutions may be rejected automatically

C. Infeasible solutions may appear attractive

D. The objective becomes independent of data

Correct Answer: C. Infeasible solutions may appear attractive

Question 9

Which practice provides the fairest comparison between quantum and classical solvers?

A. Use different constraints for each solver

B. Compare only the solver labels

C. Use the same data, constraints, stopping rule, and post-processing

D. Ignore feasibility and compare raw energy only

Correct Answer: C. Use the same data, constraints, stopping rule, and post-processing

Question 10

A hybrid solver is best described as one that:

A. Uses only quantum hardware and no classical computation

B. Combines classical procedures with quantum subroutines or sampling

C. Avoids all validation after optimization

D. Solves only continuous problems

Correct Answer: B. Combines classical procedures with quantum subroutines or sampling