Reduced cost

In linear programming, the reduced cost of a decision variable, often denoted as \bar{c}_j, measures the change in the objective function value per unit increase in that variable from its current bound (typically zero for non-basic variables), while keeping all other variables fixed at their optimal values.^[1] It is computed as \bar{c}_j = c_j - \sum_{i=1}^m y_i a_{ij}, where c_j is the original objective coefficient for variable x_j, y_i are the shadow prices (dual variables) for the constraints, and a_{ij} are the constraint coefficients.^[1] For basic variables in the optimal solution, the reduced cost is always zero, as they are already at positive levels contributing to optimality.^[2] Reduced costs play a central role in sensitivity analysis within the simplex method, helping analysts assess how perturbations in objective coefficients affect the optimal solution.^[3] Specifically, for a non-basic variable in a maximization problem, a negative reduced cost indicates the amount by which the coefficient must increase to make the variable enter the basis and potentially improve the objective; conversely, in minimization problems, a positive reduced cost shows the deterioration if the variable is forced into the solution.^[2] This concept also equates to the shadow price of the variable's nonnegativity constraint, providing insight into the marginal cost of relaxing bounds on decision variables.^[1] In practice, reduced costs are output by solvers like Excel's Solver or specialized optimization software, aiding decision-makers in resource allocation, production planning, and other applications by quantifying the opportunity cost of excluding a variable from the active solution.^[3] For instance, if a product's reduced cost is -2 in a profit maximization model, its selling price must rise by at least $2 per unit to justify production.^[1] Zero reduced costs for non-basic variables signal multiple optimal solutions, allowing flexibility in implementation without changing the objective value.^[2]

Fundamentals

Definition

In linear programming, the reduced cost of a variable represents the change in the objective function value per unit increase in that variable when it is introduced into the solution at its current non-basic level. Specifically, it quantifies the amount by which the objective coefficient of a non-basic variable must be altered for that variable to become basic and enter the solution at a positive value, thereby improving the objective function. This measure is computed within the framework of the simplex method, where variables are classified as basic (included in the current solution) or non-basic (set to zero). The interpretation of reduced cost varies depending on whether the problem is a maximization or minimization, and the sign convention used. In maximization problems, a positive reduced cost for a non-basic variable indicates the potential increase in the objective value (e.g., profit) if that variable were allowed to enter the basis, signaling that the current solution is suboptimal. Conversely, in minimization problems, a negative reduced cost signifies the potential decrease in the objective value (e.g., cost) upon introducing the variable, again pointing to suboptimality if such a value exists.^[1] For basic variables in an optimal solution, the reduced cost is always zero, as these variables are already at levels that do not allow further improvement in the objective function without violating constraints. Non-basic variables, however, may have non-zero reduced costs that guide the optimization process toward feasibility and optimality. Consider a simple maximization problem with objective function z = 3x_1 + 2x_2, subject to constraints like x_1 + x_2 \leq 4 and non-negativity. Suppose the current basic feasible solution has x_1 = 4, x_2 = 0, yielding z = 12. If the reduced cost for x_2 is -1, introducing x_2 would decrease z by 1 unit per unit of x_2, confirming optimality as no better solution exists by pivoting x_2 into the basis.^[1]

Mathematical Formulation

In linear programming, the reduced cost is formulated within the standard primal problem of minimizing the objective \mathbf{c}^T \mathbf{x} subject to the equality constraints \mathbf{Ax} = \mathbf{b} and non-negativity \mathbf{x} \geq \mathbf{0}, where \mathbf{A} \in \mathbb{R}^{m \times n} is the coefficient matrix, \mathbf{b} \in \mathbb{R}^m is the right-hand-side vector, \mathbf{c} \in \mathbb{R}^n is the cost vector, and \mathbf{x} \in \mathbb{R}^n are the decision variables.^[4] The associated dual problem is to maximize \mathbf{b}^T \mathbf{y} subject to \mathbf{A}^T \mathbf{y} \leq \mathbf{c}, where \mathbf{y} \in \mathbb{R}^m represents the dual variables or shadow prices.^[4] The reduced cost for the j-th variable x_j at an optimal solution is defined as \bar{c}_j = c_j - \mathbf{a}_j^T \mathbf{y}, where \mathbf{a}_j is the j-th column of \mathbf{A} and \mathbf{y} is the optimal dual solution.^[4] In vector notation, the full reduced cost vector is \bar{\mathbf{c}} = \mathbf{c} - \mathbf{A}^T \mathbf{y}.^[4] By strong duality, \bar{c}_j \geq 0 for all j corresponding to nonbasic variables at optimality in the minimization problem, ensuring no further improvement is possible.^[4] Within the simplex method, the reduced costs are derived from the current basic feasible solution, where the basis matrix \mathbf{B} consists of columns of \mathbf{A} for the basic variables, and \mathbf{c}_B are the corresponding costs. The shadow prices are \mathbf{y}^T = \mathbf{c}_B^T \mathbf{B}^{-1}, so \bar{c}_j = c_j - \mathbf{c}_B^T \mathbf{B}^{-1} \mathbf{a}_j for nonbasic j.^[5] In the simplex tableau, these reduced costs appear as the coefficients in the objective row (row 0) for the nonbasic variables, specifically as c_j - z_j where z_j = \mathbf{c}_B^T \mathbf{B}^{-1} \mathbf{a}_j.^[5] For maximization problems, the reduced cost convention aligns similarly but with the objective sense reversed; a positive reduced cost for a nonbasic variable indicates that increasing it would improve (increase) the objective value, signaling a direction for basis improvement.^[6] This formulation ensures that the optimality conditions tie directly to the dual feasibility \mathbf{A}^T \mathbf{y} \leq \mathbf{c} (for minimization) or \mathbf{A}^T \mathbf{y} \geq \mathbf{c} (for maximization).^[4]

Role in the Simplex Method

Entering Variable Selection

In the simplex method applied to maximization problems, the entering variable is selected from the nonbasic variables by identifying the one with the most positive reduced cost, as this indicates the largest potential increase in the objective function value per unit increase in that variable.^[7] The reduced costs are computed for all nonbasic variables using the current basis, typically via the formula \bar{c}_j = c_j - \pi^T A_j, where \pi are the simplex multipliers (dual variables) and A_j is the column for variable j, but in tableau form, the negative of the reduced costs appear in the objective row.^[8] The optimal pivot strategy, often called Dantzig's rule, involves calculating all reduced costs and choosing the most positive one to enter the basis, which theoretically accelerates convergence by maximizing improvement per iteration.^[7] However, this full pricing step becomes computationally expensive in large problems with many variables, as it requires updating and evaluating reduced costs for potentially thousands of nonbasics, leading to high per-iteration time complexity. In practice, approximations mitigate this expense, such as partial pricing (scanning nonbasics in a fixed order until a positive reduced cost is found) or advanced heuristics like the Devex rule, which prioritizes variables likely to yield steep improvements based on historical pivots.^[9] Consider a simple maximization example: maximize Z = 40x_1 + 30x_2 subject to x_1 + x_2 \leq 12, $2x_1 + x_2 \leq 16, x_1, x_2 \geq 0. Introducing slacks s_1, s_2 \geq 0, the initial tableau is:

Basic	x_1	x_2	s_1	s_2	RHS
s_1	1	1	1	0	12
s_2	2	1	0	1	16
Z	40	30	0	0	0

The reduced costs appear in the Z row: 40 for x_1 and 30 for x_2. The most positive is 40, so x_1 is selected as the entering variable. The minimum ratio test on the pivot column (quotients 12/1=12 and 16/2=8) identifies s_2 as leaving, with pivot at 2. After pivoting, the new tableau has x_1 basic, updated reduced costs (now 10 for x_2), and Z=320.^[10] To avoid cycling in degenerate linear programs, where the simplex method might loop infinitely without progress, anti-cycling rules incorporate reduced costs into variable selection. Bland's rule, for instance, chooses the entering variable as the eligible nonbasic (positive reduced cost) with the smallest index and the leaving variable similarly among minimum-ratio ties, ensuring the algorithm terminates in a finite number of steps without cycles.^[11] This rule maintains computational simplicity while guaranteeing non-cycling behavior, though it may lead to more iterations than aggressive strategies like Dantzig's.^[12]

Optimality Conditions

In the simplex method applied to maximization problems in linear programming, a basic feasible solution is deemed optimal when all reduced costs for non-basic variables in the final tableau are less than or equal to zero. This condition indicates that increasing any non-basic variable would not improve (and might worsen) the objective function value, as the reduced cost \bar{c}_j = c_j - \pi^T A_j \leq 0 for each non-basic column j, where \pi are the simplex multipliers (dual variables) and A_j is the constraint column for variable j. For minimization problems, the optimality criterion reverses: all reduced costs must be greater than or equal to zero to ensure no further decrease in the objective is possible.^[13] A reduced cost of exactly zero for a non-basic variable signals the presence of multiple optimal solutions, as introducing that variable into the basis at a positive level would yield an alternative basic feasible solution with the same objective value. This occurs because the variable lies on the boundary of the dual feasible region, allowing degeneracy in the sense of non-unique bases without changing the optimum. In contrast, strictly negative reduced costs (for maximization) in a tableau confirm a unique optimum, as any deviation would degrade the solution.^[14] Reduced costs play a key role in confirming overall optimality by ensuring dual feasibility alongside primal feasibility, with complementary slackness providing the linkage. Specifically, the non-negativity of reduced costs (in the maximization convention, interpreted as \pi^T A_j - c_j \geq 0) satisfies the dual constraints, while complementary slackness holds because basic variables (with positive values) have zero reduced costs, and non-basic variables (at zero) permit positive reduced costs without violation. This pairwise condition—that a primal variable is positive only if its corresponding reduced cost is zero, and vice versa—guarantees that the primal and dual solutions align at the optimum.^[15] To illustrate the transition to optimality, consider a maximization problem solved via the simplex method. In an initial or intermediate suboptimal tableau, the objective row (showing reduced costs) might appear as:

Basis	x1	x2	x3	s1	s2	RHS
s1	1	1	0	1	0	4
s2	2	1	1	0	1	5
z	3	1	4	0	0	0

Here, positive reduced costs (3 for x_1, 1 for x_2, 4 for x_3) indicate the solution is not optimal, prompting selection of an entering variable (e.g., x_3). After pivoting operations, the final optimal tableau could be:

Basis	x1	x2	x3	s1	s2	RHS
x3	1/2	1/2	1	1/2	0	2.5
s2	3/2	1/2	0	-1/2	1	1.5
z	-1	-2	0	-1	0	10

Now, all reduced costs for non-basics (-1 for x_1, -2 for x_2, -1 for s_1) are non-positive, confirming optimality with z = 10. If a non-basic reduced cost were zero here, pivoting on it would reveal an alternate optimum.^[13]

Interpretations

Economic Interpretation

In linear programming, the reduced cost of a non-basic variable represents the marginal value associated with its objective coefficient, specifically indicating how much that coefficient must improve (for a maximization problem) before the variable becomes economically viable to introduce into the optimal solution. For instance, a negative reduced cost signifies that increasing the variable by one unit would decrease the objective value by the absolute amount of the reduced cost, reflecting the net penalty or shortfall in contribution relative to resource costs. This interpretation arises from the reduced cost's role as the shadow price on the non-negativity constraint for that variable, quantifying the imputed cost of forcing the activity into production.^[16]^[17] In the context of resource allocation, particularly for non-basic variables held at zero in the optimal solution, the reduced cost measures the minimum incentive required to justify allocating additional resources to that activity. It embodies the threshold at which the marginal benefit of the activity equals the opportunity cost of the resources it consumes, ensuring that only activities with non-positive reduced costs (in maximization) are excluded without regret. This guides decision-makers in evaluating whether scarce resources, such as labor or materials, should be diverted to an underutilized option, preventing inefficient expansions.^[18]^[16] A practical example occurs in production planning, where reduced costs determine the profit threshold for introducing a new product line. Consider a furniture manufacturer optimizing chair and bench production subject to wood and labor constraints; if the reduced cost for tables is -$0.30, the profit per table must rise by at least $0.30 to make table production worthwhile, as this would offset the resource opportunity cost and enter the optimal mix without reducing overall profit. Such analysis helps firms assess market-driven changes, like price adjustments, to expand product offerings efficiently.^[18] Non-zero reduced costs directly connect to opportunity costs by quantifying the foregone benefits of not engaging the variable, equivalent to the net loss in objective value from maintaining it at zero. In economic terms, this represents the implicit penalty for exclusion, derived from the difference between the variable's direct contribution and the shadow-priced value of its resource demands, thereby highlighting trade-offs in constrained environments.^[17]^[16]

Sensitivity Analysis

In linear programming sensitivity analysis, reduced costs quantify the robustness of an optimal solution to perturbations in the objective function coefficients, particularly by indicating the extent to which a non-basic variable's coefficient can change before it becomes eligible to enter the basis.^[2] Specifically, for a maximization problem, a non-basic variable x_j remains non-basic as long as the change in its coefficient c_j does not increase its reduced cost \bar{c}_j above zero, preserving the current basis's optimality.^[16] This leverages the economic interpretation of reduced costs as the marginal improvement needed for a variable to contribute positively to the objective. The allowable range for c_j of a non-basic variable is determined directly from its reduced cost: in a maximization problem, c_j can increase by up to -\bar{c}_j (where \bar{c}_j < 0) without altering the basis, while decreases are typically unbounded as they further deter the variable from entering the basis.^[16] For instance, if \bar{c}_j = -1.5, the coefficient can be increased by at most 1.5 units before x_j enters the basis upon re-optimization.^[2] These ranges are computed by ensuring that the updated reduced costs for all non-basic variables remain non-positive after the perturbation. Solvers like Excel's provide sensitivity reports that illustrate these ranges numerically; consider a product mix problem maximizing profit $4x_1 + 6x_2 subject to constraints, where the optimal basis has x_1 basic and x_2 non-basic with \bar{c}_2 = -2. The report would show that c_2 (the coefficient for x_2) has an allowable increase of 2 (to 8) and unlimited decrease, meaning the basis remains optimal for c_2 \leq 8.^[16] A key limitation is that reduced costs inform sensitivity only for non-basic variables' objective coefficients; for basic variables, changes affect the dual prices and thus the reduced costs of multiple variables, often requiring a full re-optimization or tableau adjustment to determine ranges rather than a simple bound.^[2]

Advanced Applications

In Duality Theory

In linear programming, reduced costs are integral to duality theory. Consider the primal problem formulated as a maximization: \max \mathbf{c}^T \mathbf{x} subject to A \mathbf{x} \leq \mathbf{b}, \mathbf{x} \geq \mathbf{0}. The associated dual is \min \mathbf{y}^T \mathbf{b} subject to \mathbf{y}^T A \geq \mathbf{c}^T, \mathbf{y} \geq \mathbf{0}, where \mathbf{y} is the vector of dual variables (shadow prices). The reduced cost for the j-th primal variable, consistent with the standard definition \bar{c}_j = c_j - \mathbf{y}^T A_j, must satisfy \bar{c}_j \leq 0 for all j at primal optimality in a maximization problem. This condition is equivalent to the dual feasibility requirement \mathbf{y}^T A_j \geq c_j, as the dual constraint slacks are -\bar{c}_j \geq 0.^[16]^[19] Complementary slackness links the optimal solutions of the primal and dual, as per the strong duality theorem. For optimal \mathbf{x}^* and \mathbf{y}^*, x_j^* (\mathbf{y}^{*T} A_j - c_j) = 0 for each j, meaning \bar{c}_j = 0 if and only if x_j^* > 0 (since \bar{c}_j \leq 0). Thus, positive primal variables correspond to tight dual constraints (zero reduced cost), while non-zero reduced costs (negative in maximization) imply the primal variable is at its bound (zero). This ensures equality of the primal and dual objectives: \mathbf{c}^T \mathbf{x}^* = \mathbf{y}^{*T} \mathbf{b}.^[16]^[19] From the dual viewpoint, the negative reduced costs -\bar{c}_j quantify the slack in the dual constraints, indicating by how much \mathbf{y}^T A_j exceeds c_j. A negative \bar{c}_j (non-zero) reflects excess in the dual constraint for that variable, highlighting the margin of dual feasibility. This symmetry underscores the connection between primal optimality (non-positive reduced costs) and dual feasibility.^[20]^[21] To illustrate, consider the primal: \max 6x_1 + 14x_2 + 13x_3 subject to \frac{1}{2}x_1 + 2x_2 + x_3 \leq 24, x_1 + 2x_2 + 4x_3 \leq 60, x_1, x_2, x_3 \geq 0. The optimal solution is x_1^* = 36, x_2^* = 0, x_3^* = 6, with objective 294. The dual is \min 24y_1 + 60y_2 subject to \frac{1}{2}y_1 + y_2 \geq 6, $2y_1 + 2y_2 \geq 14, y_1 + 4y_2 \geq 13, y_1, y_2 \geq 0, with optimal y_1^* = 11, y_2^* = 0.5, objective 294. The reduced costs are \bar{c}_1 = 6 - (11 \cdot 0.5 + 0.5 \cdot 1) = 0, \bar{c}_2 = 14 - (11 \cdot 2 + 0.5 \cdot 2) = -9, \bar{c}_3 = 13 - (11 \cdot 1 + 0.5 \cdot 4) = 0. Here, \bar{c}_2 < 0 corresponds to x_2^* = 0, and zero reduced costs align with positive x_1^* and x_3^*, confirming complementary slackness. The dual slacks for the second constraint are zero, matching the binding primal constraints.^[16]

Extensions to Other Optimization Problems

In integer programming, reduced costs from the linear programming relaxation are used in branch-and-bound algorithms for variable fixing and bound tightening. Reduced cost fixing leverages complementary slackness from optimal dual solutions to eliminate variables that cannot improve the objective beyond the current primal bound, strengthening the formulation and reducing the search space. Modern mixed-integer programming solvers like CPLEX incorporate enhanced reduced cost fixing techniques, often through presolving, to improve efficiency on benchmarks like MIPLIB.^[22] In network flow problems, reduced costs are adapted using node potentials in algorithms like the successive shortest path method for minimum cost flows. Node potentials \pi(v) define reduced edge costs as \tilde{c}(u \to v) = c(u \to v) + \pi(u) - \pi(v), which preserve shortest path distances while ensuring non-negativity for efficient computation with Dijkstra's algorithm rather than Bellman-Ford. Potentials are updated after each flow augmentation using distances from the latest shortest path tree, maintaining non-negative reduced costs and yielding a time complexity of O(B E \log V), where B is the total flow value. This extends the economic interpretation of reduced costs to capacitated networks, aiding optimality verification without negative cycles. In interior-point methods for linear programming, primal-dual frameworks produce analogs to reduced costs via dual multipliers and barrier terms, which measure deviations from optimality and guide steps toward centrality. Primal-dual interior-point algorithms compute Newton directions incorporating scaled dual variables, similar to reduced costs, to diminish the duality gap and follow the central path parameterized by the barrier \mu. These provide sensitivity insights akin to simplex reduced costs, assessing perturbation impacts across barrier subproblems. In contrast to the simplex method, interior-point approaches trace smooth interior paths, with the barrier enforcing strict feasibility and self-concordance enabling polynomial convergence.