The Challenge of Infeasibility in Optimization
In the realm of mathematical optimization, dealing with infeasible problems presents a unique set of challenges. When a model yields no solution, it signifies that the constraints are contradictory. While this is a clear indicator of an unachievable state, simply knowing a problem is infeasible is often not enough. For complex optimization problems, especially those solved using decomposition techniques like Benders Decomposition, understanding *why* a problem is infeasible is crucial for guiding the search towards a feasible region. This is where the concept of feasibility cuts becomes indispensable.
Benders Decomposition is a powerful technique for solving large-scale optimization problems by decomposing them into a master problem and one or more subproblems. The master problem typically handles the "big" decisions, while the subproblems deal with the "linked" or "dependent" variables. When the master problem proposes a set of decisions, the subproblem is solved. If the subproblem is feasible, it returns information to the master problem, often in the form of an objective value or a gradient. However, if the subproblem is infeasible, it means the current decisions from the master problem cannot be satisfied by the linked variables. Without a mechanism to learn from this infeasibility, the decomposition process can stall or become inefficient.
This is the core of what Part II of our exploration into Benders Decomposition addresses: how to generate and use "feasibility cuts" derived from the infeasibility of the subproblem. These cuts provide the master problem with information about which of its decisions lead to an infeasible subproblem, thereby pruning the search space and accelerating convergence to a feasible solution.
Farkas' Lemma: The Foundation for Feasibility Cuts
The theoretical underpinning for generating feasibility cuts in Benders Decomposition is Farkas' Lemma. This fundamental result in convex analysis and linear programming provides a condition for the existence of a solution to a system of linear inequalities. In simpler terms, Farkas' Lemma states that a system of linear equations $Ax = b$ with $x e 0$ has no solution if and only if there exists a vector $y$ such that $y^T A = 0$ and $y^T b > 0$. This duality between primal infeasibility and dual feasibility is what enables us to derive meaningful information from an infeasible system.
When a Benders subproblem is found to be infeasible, it means the current proposed solution from the master problem, let's call it $ar{x}$, leads to an unresolvable system of constraints in the subproblem. Let the subproblem be represented as:
Minimize $c^T y$ subject to $W y e d$, $ar{x}$ (fixed)
If this subproblem is infeasible for a given $ar{x}$, it means there is no $y$ that satisfies the constraints. Farkas' Lemma, in its various forms, can be applied here. A common formulation for systems of inequalities states that the system $Ay e b$ has no solution $y e 0$ if and only if there exists a vector $ u e 0$ such that $ u^T A = 0$ and $ u^T b < 0$. (Note: the sign conventions can vary based on the specific formulation of the lemma and the problem structure.)
In the context of Benders Decomposition, we are interested in a condition that proves the infeasibility of the subproblem given the master problem's variables. If we consider the dual of the subproblem, an infeasible primal often corresponds to an unbounded dual. However, for Benders, we want a cut that constrains the *master problem's* variables. Farkas' Lemma helps us find a vector (let's call it $ u$) from the dual space of the subproblem such that when this vector is applied to the constraints that depend on the master problem's variables, it yields a positive (or negative, depending on formulation) value, while the part of the constraint independent of the master problem variables sums to zero. This $ u$ then forms the coefficients of a Benders cut that will be added to the master problem.
Constructing Feasibility Cuts
A feasibility cut derived from Farkas' Lemma essentially states that for the problem to be feasible, a certain linear combination of the master problem's variables must satisfy a particular inequality. This inequality is derived from the dual solution that proves the primal subproblem's infeasibility.
Let's consider the capacitated facility location problem (CFLP) as a prime example. In CFLP, we decide which facilities to open and how to assign customers to these open facilities to minimize total costs (opening costs + transportation costs), subject to demand and capacity constraints. A typical Benders decomposition for CFLP might have the master problem decide which facilities to open, and the subproblem decide the customer assignments for a given set of open facilities.
Suppose the master problem decides to open a subset of facilities, $I_{open}$. The subproblem then tries to assign customers to these facilities. If, for a given $I_{open}$, the subproblem finds that it's impossible to satisfy all customer demands without violating capacity constraints or opening costs (if they are implicitly handled), the subproblem is infeasible. This infeasibility arises because the combination of open facilities $I_{open}$ is insufficient or poorly configured to meet demand. Farkas' Lemma allows us to find a set of dual variables associated with the capacity and demand constraints that, when aggregated, form a cut. This cut will be an inequality involving the master problem's decision variables (which facilities are open). It effectively says, "For any set of open facilities $I_{open}$, this inequality must hold to avoid the infeasibility we just encountered."
The general form of a feasibility cut added to the master problem is:
$ u^T ( ext{constraints involving } ar{x}) e ext{something}$
Where $ u$ is the vector of dual multipliers from the infeasible subproblem, and $ar{x}$ represents the current (infeasible) solution from the master problem. The specific form of the inequality depends on the problem structure. For CFLP, a feasibility cut might look like:
$\sum_{i \in I} \alpha_i x_i \ge 1$
where $x_i$ are binary variables in the master problem indicating whether facility $i$ is open, and $\alpha_i$ are coefficients derived from the dual solution. This cut is added to the master problem to prevent it from proposing the same or similar infeasible combinations of open facilities in future iterations.
Learning from Infeasibility
The power of feasibility cuts lies in their ability to guide the optimization process away from regions of the decision space that are known to be infeasible. Unlike optimality cuts (which are generated when the subproblem is feasible but the current solution is suboptimal), feasibility cuts are generated solely from infeasible subproblems. They are not about improving an objective function; they are about finding *any* feasible solution.
Consider the process iteratively:
- The master problem proposes a set of decisions (e.g., which facilities to open).
- The subproblem is solved with these decisions.
- If the subproblem is infeasible, Farkas' Lemma is used to derive a feasibility cut.
- This cut is added to the master problem. The master problem then re-solves, generating a new set of decisions that will not violate this new constraint (and thus avoid the previously identified infeasibility).
- If the subproblem is feasible, an optimality cut is generated, and the process continues until convergence.
The surprising detail here is that the process of learning from *infeasibility* is as critical as learning from optimality. Without feasibility cuts, a Benders decomposition could get stuck cycling through infeasible master problem solutions, never reaching a point where the subproblem can be solved successfully. These cuts effectively "learn" the shape of the feasible region by identifying and excluding infeasible zones.
Application to Capacitated Facility Location
The capacitated facility location problem is a classic example where Benders Decomposition with feasibility cuts shines. The problem's structure naturally lends itself to this decomposition: a strategic decision (where to build facilities) handled by the master problem, and an operational decision (how to route goods/customers) handled by the subproblem.
When the master problem suggests a set of facilities to open, the subproblem must determine if it's possible to serve all customers from these facilities, respecting their capacities. If, for instance, the total capacity of the proposed open facilities is less than the total demand, or if the optimal assignment of customers to facilities still results in unmet demand due to localized capacity shortages, the subproblem will be infeasible. The resulting feasibility cut will then impose a constraint that, for example, requires a larger total capacity to be opened or a different combination of facilities to be selected in future iterations.
This iterative refinement ensures that the master problem progressively learns the conditions under which a feasible assignment of customers to facilities is possible, eventually converging to an optimal set of facility locations and assignments. The effectiveness of Benders Decomposition, especially for large-scale problems like CFLP, is heavily reliant on the intelligent generation and application of these feasibility cuts, making them a cornerstone of the algorithm's success.