Question

How does adding a valid inequality in a cutting-plane method change the feasible region of a linear relaxation without removing integer-feasible solutions?

Accepted Answer

A cutting-plane method improves a linear program by adding a valid inequality, which is a new linear constraint that tightens the feasible region of the linear relaxation. The linear relaxation is the version of an integer programming problem where integer requirements are removed, allowing variables to take any fractional value. The valid inequality acts as a boundary that cuts off parts of the continuous space that contain only fractional solutions, effectively shrinking the feasible region. Crucially, the inequality is defined such that it never excludes any point that satisfies the original integer requirements. By removing fractional corners of the feasible region while preserving all integer-feasible points, the method forces the optimal solution of the linear relaxation to move closer to the true integer optimum. For example, if a linear relaxation allows a fractional point such as x equals 1.5, a valid inequality might state that x must be less than or equal to 1, thereby slicing away the portion of the region where x equals 1.5 without eliminating the integer-feasible point where x equals 1. This process iteratively shapes the feasible region to be as tight as possible around the integer points, making it easier for solvers to identify the optimal integer solution.

Home → All Courses → Science and Mathematics Courses → Decision Science and Optimization → Flashcard

How does adding a valid inequality in a cutting-plane method change the feasible region of a linear relaxation without removing integer-feasible solutions?