Large-Scale Optimization and Decomposition

Introduction

Many business analytics models are difficult not because their mathematical structure is obscure, but because their scale is enormous. A supply-chain design model may contain millions of shipment, facility, and time-period variables. A workforce-planning model may combine binary staffing decisions with detailed scheduling constraints. A telecommunications or energy model may involve a network with thousands of nodes, time periods, and scenarios. Even when such models are linear or mixed-integer linear programs, direct solution can be computationally expensive.

Large-scale optimization addresses this challenge by exploiting structure. Rather than treating a model as one undifferentiated problem, decomposition methods divide it into smaller problems that can be solved sequentially or in parallel. The principal methods considered in this chapter are Lagrangian relaxation, Benders decomposition, Dantzig–Wolfe decomposition, column generation, parallel computing, and model reformulation.

The central principle is to replace one difficult computation with a coordinated collection of simpler computations while preserving, or suitably approximating, the original decision problem.

Learning Objectives

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

1. Explain why large-scale optimization models require specialized computational methods.
2. Formulate and interpret Lagrangian relaxations and their dual bounds.
3. Distinguish Benders decomposition from Dantzig–Wolfe decomposition and column generation.
4. Derive the principal master and subproblem relationships in decomposition algorithms.
5. Select appropriate decomposition strategies for business analytics applications.
6. Explain how parallel computing and model reformulation improve performance.
7. Evaluate numerical, managerial, governance, and implementation limitations.

1. Why Large-Scale Optimization Requires Decomposition

Consider a mixed-integer optimization model:

Here, x may represent strategic binary decisions, y operational decisions, A and B are constraint matrices, and c, d, and b are parameter vectors. The feasible sets X and Y may include integrality and logical restrictions.

A model becomes computationally large through several mechanisms:

• Many variables: millions of arcs, products, customers, or scenarios.
• Many constraints: capacity, balance, service, regulatory, and logical restrictions.
• Combinatorial structure: binary and integer variables create an exponentially large search space.
• Dense coupling: decisions made in one business unit affect many others.
• Time and uncertainty: multiple periods and scenarios multiply the model dimension.
• Weak formulations: poor linear relaxations create large branch-and-bound trees.

A conventional solver may still solve some large models effectively. Decomposition is most valuable when the model has identifiable structure, such as a small set of linking constraints connecting otherwise separable subsystems.

A useful conceptual partition is:

The sets X_i contain local constraints, while the linking constraint Σᵢ Aᵢxᵢ ≤ b couples the subsystems. If the linking constraint were removed, the problem would separate into m independent subproblems. Decomposition methods exploit precisely this relationship.

2. Structural Ideas Behind Decomposition

2.1 Partitioning decisions

A decomposition normally identifies two types of decisions:

• Complicating or linking decisions: decisions that connect otherwise independent parts of the model.
• Local decisions: decisions that can be optimized independently once linking information is fixed or priced.

For example, in facility-location planning, facility-opening decisions may be strategic and linking, while customer assignments can be optimized conditionally for each facility configuration.

2.2 Relaxation and restriction

Two fundamental operations are used.

A relaxation enlarges the feasible region by removing or weakening constraints. Its optimal objective value provides a bound. For a minimization problem, a relaxation gives a lower bound on the original optimum; for a maximization problem, it gives an upper bound.

A restriction reduces the feasible region, usually by imposing a particular structure. It can produce a feasible solution to the original problem, thereby giving an incumbent bound. Decomposition algorithms coordinate bounds from relaxations with feasible solutions from restricted or reconstructed models.

2.3 Master problems and subproblems

A master problem coordinates global decisions, prices, or combinations of patterns. A subproblem evaluates local decisions, generates improving variables, or identifies violated constraints. The master and subproblem interact iteratively.

The iteration terminates when no improving variable or violated valid inequality can be found, or when a practical stopping rule is reached.

3. Lagrangian Relaxation

3.1 Basic formulation

Suppose the problem is

where g(x) ≤ 0 are difficult coupling constraints and X represents the remaining feasible restrictions. Introduce nonnegative multipliers λ ≥ 0 and define the Lagrangian:

The Lagrangian relaxation solves

For any λ ≥ 0, q(λ) is a lower bound on the original minimization problem, because every feasible original solution satisfies g(x) ≤ 0, and therefore λᵀg(x) ≤ 0. The best Lagrangian bound is obtained from the dual problem:

The function q(λ) is concave but generally nondifferentiable. The Lagrangian dual optimum can be strictly below the primal optimum, especially for integer programs. This difference is the duality gap.

3.2 Interpretation of multipliers

A multiplier λ_j is a shadow price for relaxing constraint j. In a continuous differentiable setting, it approximates the change in the optimal objective value resulting from a marginal change in the right-hand side. In integer models, this interpretation is more cautious because value functions can be discontinuous and nonconvex.

If a capacity constraint is violated by a candidate solution, increasing its multiplier penalizes that violation. The method therefore converts a hard feasibility restriction into an economic penalty.

3.3 Subgradient optimization

Let x^k minimize the Lagrangian for multipliers λ^k. A subgradient of q at λ^k is

A common update for a maximization of the dual function is

where α_k ≥ 0 is a step size. The projection max{0,·} preserves nonnegative multipliers. A practical step size may be based on the gap between an incumbent primal value UB and the current dual value q(λ^k):

where 0 < θ ≤ 2 is a tuning parameter and the denominator is positive. This rule is meaningful when UB ≥ q(λ^k). If the subgradient is zero, the multiplier update is unnecessary at that iteration.

Subgradient methods are attractive because each iteration can be inexpensive, but they may oscillate, converge slowly, and provide weak primal solutions. Bundle methods and stabilized multiplier schemes can improve practical behavior.

3.4 Illustrative example

Suppose a minimization model has a local feasible set X and one coupling constraint x₁ + x₂ ≤ 10. If a Lagrangian solution gives x₁ + x₂ = 13, then the violation is 3. With current multiplier λ = 2 and step size α = 0.5, the update is

The larger multiplier makes future violations more costly. This calculation illustrates the mechanism; it does not by itself guarantee convergence to a primal-feasible solution.

3.5 Applications and limitations

Lagrangian relaxation is useful in vehicle routing, scheduling, network design, assignment, unit commitment, and facility location. It is particularly attractive when relaxing a small number of constraints causes the remaining problem to decompose by product, customer, machine, or time period.

Its limitations include:

• the duality gap in integer programming;
• difficulty recovering high-quality feasible solutions;
• sensitivity to multiplier and step-size strategies;
• instability caused by oscillating subproblem solutions;
• possible loss of meaningful interpretation when penalties become very large.

4. Benders Decomposition

4.1 Principle

Benders decomposition is fundamentally a row-generation method. It is most natural when variables can be divided into complicating variables y and relatively easy continuous variables x. Consider the linear program

For a fixed y, the subproblem in x is

The master problem chooses y and an approximation θ of the subproblem cost. Benders cuts are added to ensure that θ is a valid lower approximation.

4.2 Optimality and feasibility cuts

The dual of the fixed-y subproblem is, in a standard inequality form,

If the subproblem is feasible and has an optimal dual solution u^r, the corresponding optimality cut is

This cut states that the master must account for at least the subproblem cost implied by dual solution u^r.

If the subproblem is infeasible, a ray v^r of its dual feasible region produces a feasibility cut of the form

The exact sign and form depend on the primal and dual conventions. The essential purpose is to exclude master solutions that make the operational subproblem infeasible.

The Benders master begins with the original constraints involving y, a variable θ, and possibly a lower bound on θ. It repeatedly solves, checks the subproblem, and adds a feasibility or optimality cut.

4.3 Algorithmic sequence

1. Solve the restricted master problem.
2. Fix the master variables y^r.
3. Solve the corresponding subproblem.
4. If infeasible, generate a feasibility cut.
5. If feasible, generate an optimality cut if the current θ underestimates the subproblem value.
6. Update bounds and repeat until the gap is acceptable.

Benders decomposition is especially effective when the number of complicating variables is moderate and the subproblem is large but tractable.

4.4 Logic-based Benders decomposition

Classical Benders relies on linear programming duality. Logic-based Benders decomposition generalizes the method by deriving cuts from inference, scheduling logic, constraint programming, or problem-specific arguments. This is valuable when the subproblem is an integer program or a combinatorial scheduling model for which ordinary LP dual cuts are weak or unavailable.

5. Dantzig–Wolfe Decomposition and Column Generation

5.1 Principle

Dantzig–Wolfe decomposition is fundamentally a column-generation method. It is useful when the feasible region of a subsystem has many extreme points or patterns, while the number of coupling constraints is comparatively small.

Consider

Assume the feasible solutions of X can be represented as convex combinations of extreme points p. For simplicity, let P denote the set of feasible patterns. Then

The resulting restricted master uses one variable λ_p for each pattern. In practice, P is too large to enumerate, so only a subset of columns is included initially.

5.2 Pricing problem

Let π be dual variables associated with the coupling constraints and σ the dual variable associated with the convexity constraint. For a minimization master, the reduced cost of pattern p typically has the form

where c_p is the pattern cost and a_p is its contribution to the coupling constraints. The pricing problem searches for a pattern with negative reduced cost. If one exists, it is added to the restricted master. If none exists, the current restricted master solution is optimal for the LP relaxation, subject to the correctness of the pricing problem.

The signs of reduced costs depend on the chosen primal and dual conventions; the operational rule is invariant: add a column that improves the restricted master objective.

5.3 Column-generation sequence

1. Construct a feasible initial restricted master.
2. Solve its LP relaxation.
3. Obtain dual prices.
4. Solve the pricing problem using those prices.
5. Add an improving column if found.
6. Repeat until no improving column exists.
7. Apply branching, stabilization, or an integer master method if an integer solution is required.

5.4 Branch-and-price

Column generation solves an LP relaxation. If the solution is fractional and integrality is required, branch-and-price combines column generation with branch-and-bound. The pricing problem must be solved at each relevant node, and branching decisions must be designed so that the pricing problem remains tractable.

5.5 Example: cutting-stock interpretation

A manufacturer cuts large rolls into customer-required widths. A pattern describes one feasible cutting arrangement, and a column represents that pattern. The restricted master determines how many times each pattern should be used. The pricing problem searches for a new cutting pattern whose material use and dual value produce negative reduced cost. This avoids listing every possible pattern in advance.

Column generation is also common in crew scheduling, vehicle routing, bin packing, fleet assignment, and telecommunications network design.

6. Comparing the Main Decomposition Methods

The methods are not mutually exclusive. A model can use Benders decomposition at the outer level and column generation inside a subproblem. Lagrangian bounds may be used to strengthen a branch-and-bound algorithm, while reformulation may improve all components.

7. Parallel Computing in Decomposition

Decomposition frequently creates independent subproblems. If subproblem i requires time t_i, sequential processing takes approximately

With p identical processors and perfect balanced parallel execution, the ideal time is approximately

The speedup is

and the parallel efficiency is

In practice, communication, synchronization, task imbalance, and serial master work reduce performance. Amdahl’s law gives a simple upper bound when a fraction s of computation is serial:

This formula assumes a fixed workload and ideal parallel execution of the nonserial part. It demonstrates why accelerating subproblems alone cannot eliminate a serial master bottleneck.

Practical parallel designs include:

• solving independent Lagrangian subproblems concurrently;
• evaluating Benders subproblems for scenarios in parallel;
• running multiple pricing problems concurrently;
• using asynchronous cut or column generation;
• parallel branch-and-bound;
• distributing scenario or geographic blocks across cloud nodes.

Parallel implementations require careful attention to reproducibility, numerical tolerances, memory use, processor failures, and synchronization. More processors can also produce diminishing returns or even slower performance if communication dominates.

8. Model Reformulation

Reformulation changes the representation of a model without changing its intended feasible decisions or objective meaning. A strong formulation can substantially reduce solution time.

8.1 Variable elimination and aggregation

If a variable is uniquely determined by an equality, it may be substituted out. Aggregation can reduce the number of constraints, but it may also destroy useful structure or weaken bounds. Elimination should therefore be evaluated computationally rather than applied automatically.

8.2 Tight bounds and big-M values

A logical implication may be represented using a big-M constraint, such as

where z ∈ {0,1} and M is a valid upper bound on x. The value of M must be sufficiently large for correctness but not unnecessarily large. Excessive values cause weak LP relaxations and numerical instability.

Indicator constraints, perspective formulations, and disjunctive programming can provide stronger or more numerically reliable alternatives.

8.3 Symmetry breaking

If interchangeable facilities or machines create equivalent solutions, symmetry can cause redundant search. Constraints that impose an ordering, such as nondecreasing facility usage, can eliminate equivalent branches without removing genuinely distinct solutions.

8.4 Valid inequalities

A valid inequality is satisfied by every feasible solution but may cut off fractional solutions of the relaxation. Examples include cover inequalities, flow cuts, subtour-elimination constraints, and capacity cuts. Strong valid inequalities improve bounds and reduce the search tree.

8.5 Scaling and numerical quality

Coefficients should be scaled so that their magnitudes are not needlessly separated by many orders. Poor scaling may produce inaccurate feasibility tests, unstable dual prices, and misleading termination gaps. Units should remain meaningful: converting kilograms to tonnes or dollars to thousands of dollars can improve numerical conditioning when done consistently.

9. Integrated Illustrative Case: Regional Distribution Network

The following is a fictional illustrative case designed to show how methods can be combined.

Background

A retailer serves 18,000 stores from potential distribution centers over a five-year horizon. Decisions include opening centers, assigning stores, selecting transportation lanes, and determining inventory flows under seasonal demand scenarios. The model contains binary facility decisions, continuous flows, capacity constraints, service-level requirements, and scenario-specific recourse.

Problem

A direct mixed-integer model contains approximately 2.4 million variables and 1.7 million constraints. A standard solve reaches a feasible solution quickly but leaves a large optimality gap after several hours. Management requires a solution within 30 minutes and needs a defensible bound on quality.

Analysis

Facility-opening decisions link the network globally. Conditional on those decisions, transportation and inventory decisions separate by scenario and region. The structure suggests Benders decomposition, with facility decisions in the master and operational flows in scenario-region subproblems.

However, each regional transportation subproblem itself contains a huge number of feasible route patterns. Enumerating all routes would be impractical. Column generation is therefore embedded within selected subproblems.

Approach and solution

1. The master chooses facility openings and an approximation of total recourse cost.
2. Scenario-region subproblems are solved in parallel.
3. Infeasible subproblems generate feasibility cuts, identifying facility configurations that cannot satisfy service or capacity requirements.
4. Feasible subproblems generate Benders optimality cuts.
5. Within each transportation subproblem, a restricted master selects route columns.
6. Pricing problems generate routes with negative reduced cost.
7. A primal heuristic repairs fractional or infeasible master solutions to obtain an incumbent plan.
8. Facility symmetry is reduced by ordering equivalent candidate sites.
9. Capacity bounds and transportation costs are scaled consistently.

Outcome

In an illustrative computational experiment, the integrated method produces a feasible plan within eight minutes and improves the bound until the relative gap is below the organization’s five-percent tolerance. The exact numerical outcome depends on data, hardware, solver settings, and implementation quality; decomposition is not guaranteed to outperform a monolithic model in every instance.

Learning points

• Decomposition should follow model structure rather than organizational labels alone.
• Parallel subproblems can reduce elapsed time, but the master may remain a bottleneck.
• Column generation is valuable when route or schedule enumeration is impossible.
• Feasible-solution heuristics are important because bounds alone do not provide an implementable plan.
• Management should receive both a solution and a quality statement, such as an optimality gap or a justified stopping criterion.

10. Practical Implementation and Governance

A reliable implementation begins with profiling the monolithic model. Record numbers of variables and constraints, matrix sparsity, integrality structure, solve times, root relaxation quality, and bottleneck subproblems. Then test a decomposition prototype on reduced data.

Important design choices include:

• selecting a decomposition that creates genuinely easier subproblems;
• constructing a feasible initial master for column generation;
• stabilizing dual prices when columns oscillate;
• retaining useful cuts and removing inactive ones carefully;
• using warm starts when master problems change incrementally;
• monitoring primal and dual bounds separately;
• defining termination by an explicit relative or absolute gap;
• validating the final solution in the original, not only decomposed, model.

For a minimization problem, a common relative gap is

where UB is the value of a feasible incumbent and LB is a valid lower bound. The denominator convention prevents instability when objective values are near zero. Organizations should document whether reported gaps are absolute, relative, solver-reported, or heuristic estimates.

Governance issues are significant. A decomposition algorithm may return a feasible but nonoptimal plan. Decision-makers must understand the stopping rule, data assumptions, scenario coverage, and sensitivity to penalties or multipliers. In regulated contexts, audit trails should preserve model versions, input data, solver settings, generated cuts or columns when material, and the final validation results.

Ethical concerns arise when optimization allocates scarce capacity, labor, healthcare resources, or delivery priority. Decomposition improves computation but does not resolve fairness, privacy, or accountability questions. Objectives and constraints should be reviewed for discriminatory proxies, unacceptable service disparities, and incentives that shift harm to less visible stakeholders.

11. Contemporary Developments

Modern large-scale optimization increasingly combines mathematical programming with data and computing systems. Relevant developments include:

• distributed optimization over cloud infrastructure;
• machine-learning predictions embedded in optimization pipelines;
• learning-assisted branching, pricing, and cut selection;
• scenario reduction for stochastic programs;
• robust and distributionally robust optimization;
• GPU acceleration for suitable linear-algebra operations;
• hybrid constraint-programming and mixed-integer programming systems;
• digital twins that repeatedly solve optimization models as conditions change.

Machine learning can predict promising columns, branching variables, or multiplier initializations, but predictions should remain subordinate to mathematical validity. A learned heuristic may suggest a column; it must not be accepted as a valid proof of optimality unless its reduced cost and feasibility are verified. Similarly, an approximate solution should not be presented as optimal merely because a predictive model generated it.

Challenges and Limitations

Large-scale decomposition has several general limitations:

1. Decomposition overhead: Repeated master and subproblem solves may exceed the cost of a direct solve.
2. Weak bounds: A poor relaxation can produce slow convergence.
3. Degeneracy: Multiple dual solutions can cause unstable column generation.
4. Integer recourse: Classical Benders cuts may be insufficient when subproblems are integer.
5. Tail-off: Improvements may become very small after many iterations.
6. Implementation complexity: Specialized pricing, cut management, and parallel coordination require expertise.
7. Numerical instability: Large penalties, weak big-M values, and poor scaling can compromise reliability.
8. Data uncertainty: An exact solution to an inaccurate model may still be a poor business decision.

Consequently, algorithm selection should consider total decision quality, including computational time, robustness, interpretability, implementation risk, and governance—not only the mathematical objective value.

Chapter Summary

Large-scale optimization exploits structure to solve models that are too costly or unwieldy for direct computation. Lagrangian relaxation removes coupling constraints and prices their violations, producing dual bounds through multiplier optimization. Benders decomposition separates complicating variables from operational recourse and iteratively generates feasibility and optimality cuts. Dantzig–Wolfe decomposition represents feasible subsystem decisions as patterns, while column generation creates only the variables that can improve a restricted master. Branch-and-price extends this approach to integer solutions.

Parallel computing can accelerate independent subproblems, but communication, imbalance, and serial master work limit speedup. Model reformulation—including tight bounds, valid inequalities, symmetry breaking, variable elimination, and numerical scaling—often determines whether a decomposition method succeeds. Effective applications combine structural analysis, mathematical validity, computational engineering, feasible-solution heuristics, and transparent governance. The final goal is not merely to solve a large model, but to produce a defensible, implementable, and appropriately qualified decision.

Key Terms

Lagrangian relaxation: A method that relaxes constraints and penalizes their violation with multipliers.

Lagrangian dual: The problem of maximizing the lower-bound function generated by a Lagrangian relaxation.

Multiplier: A nonnegative price associated with a relaxed inequality constraint.

Subgradient: A generalized gradient used to update multipliers for a nondifferentiable dual function.

Duality gap: The difference between a primal feasible objective and a valid dual bound.

Benders decomposition: A row-generation method separating master variables from subproblem recourse.

Benders optimality cut: A constraint requiring the master to account for subproblem cost.

Benders feasibility cut: A constraint excluding master decisions that make a subproblem infeasible.

Logic-based Benders: Benders decomposition using problem-specific inference rather than only LP duality.

Dantzig–Wolfe decomposition: A reformulation based on representing feasible solutions as combinations of patterns.

Column generation: Iterative addition of improving variables to a restricted master problem.

Pricing problem: The subproblem that searches for a column with improving reduced cost.

Branch-and-price: Branch-and-bound combined with column generation.

Master problem: The coordinating problem in a decomposition algorithm.

Subproblem: A local problem used to evaluate, price, or generate information for the master.

Valid inequality: A constraint satisfied by every feasible solution that can strengthen a relaxation.

Big-M formulation: A logical formulation using a sufficiently large constant to link variables and conditions.

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

Parallel efficiency: Speedup divided by the number of processors.

Model reformulation: A mathematically equivalent or strengthened representation intended to improve computation.

Review Questions

Short Answer Questions

1. Why can removing linking constraints cause a large optimization model to decompose?
2. What is the purpose of a Lagrangian multiplier?
3. Distinguish a Benders feasibility cut from a Benders optimality cut.
4. What does a pricing problem do in column generation?
5. Why can an excessively large big-M value be harmful?

Long Answer Questions

1. Derive the Lagrangian relaxation and dual problem for a generic minimization model with coupling inequalities. Explain the meaning of the resulting bound.
2. Describe the complete sequence of a classical Benders decomposition algorithm, including the role of the subproblem dual.
3. Explain how Dantzig–Wolfe decomposition transforms a huge variable space into a restricted master and pricing problem.
4. Compare Lagrangian relaxation, Benders decomposition, and column generation in terms of what is relaxed or generated and when each is appropriate.
5. Discuss how parallel computing, reformulation, stabilization, and governance jointly affect the success of large-scale optimization.

Analytical / Application Questions

1. A minimization model has an incumbent value of 1,250 and a valid lower bound of 1,175. Calculate the relative gap using (UB − LB)/max{1, |UB|}. Explain whether a five-percent tolerance has been met.
2. A company’s planning model has facility-opening decisions and independent regional transportation subproblems. Recommend a decomposition architecture and justify whether Benders, column generation, or a hybrid method is appropriate.
3. A parallel algorithm has a serial fraction of 0.10. Using Amdahl’s law, calculate the maximum theoretical speedup with 8 processors and explain why actual speedup may be lower.

Multiple Choice Questions with Answers

Question 1

For a minimization problem, what type of bound is normally produced by a Lagrangian relaxation?

A. An upper bound on every feasible solution

B. A lower bound on the original optimum

C. An exact integer solution in every iteration

D. A feasibility certificate only

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

Question 2

Which decomposition method primarily generates rows or cuts for a master problem?

A. Benders decomposition

B. Column generation

C. Subgradient descent

D. Symmetry breaking

Correct Answer: A. Benders decomposition

Question 3

In column generation, what is the purpose of the pricing problem?

A. To verify financial prices

B. To search for an improving column

C. To remove all integer variables

D. To calculate processor speedup

Correct Answer: B. To search for an improving column

Question 4

A Benders feasibility cut is generated when:

A. The restricted master has no objective function

B. The subproblem is infeasible for the current master decision

C. The pricing problem finds a negative reduced cost

D. All variables are continuous

Correct Answer: B. The subproblem is infeasible for the current master decision

Question 5

For a minimization restricted master, a column with negative reduced cost generally:

A. Can improve the LP objective

B. Proves integer optimality immediately

C. Must be deleted

D. Shows that the model is infeasible

Correct Answer: A. Can improve the LP objective

Question 6

If the serial fraction is 0.10, Amdahl’s law gives the maximum speedup with 8 processors as approximately:

A. 2.00

B. 4.71

C. 7.20

D. 8.00

Correct Answer: B. 4.71

Question 7

Which is a likely consequence of using an unnecessarily large big-M value?

A. A stronger linear relaxation

B. Improved numerical stability

C. A weaker relaxation and possible numerical difficulties

D. Automatic elimination of all binary variables

Correct Answer: C. A weaker relaxation and possible numerical difficulties

Question 8

Branch-and-price combines column generation with:

A. Branch-and-bound

B. Monte Carlo simulation only

C. Inventory aggregation only

D. A feasibility-only heuristic

Correct Answer: A. Branch-and-bound

Question 9

In a decomposition model, linking constraints are important because they:

A. Make all subproblems identical

B. Connect otherwise separable subsystems

C. Always eliminate integrality

D. Guarantee zero duality gap

Correct Answer: B. Connect otherwise separable subsystems

Question 10

An incumbent value is 1,250 and a valid lower bound is 1,175. The relative gap using the incumbent in the denominator is:

A. 4%

B. 5%

C. 6%

D. 75%

Correct Answer: C. 6%