Remove the integrality requirements from an integer program while retaining its linear inequalities and variable bounds. Every original feasible point remains feasible. Thus the relaxed optimum is an upper bound for a maximization problem and a lower bound for a minimization problem. An optimal relaxed feasible point need not have integer coordinates. Variable bounds that were implied only by an informal declaration such as binary must be made explicit before removing integrality.
Articles by others on the same topic
Linear programming relaxation is a technique used in optimization, particularly in the context of integer programming and combinatorial optimization problems. The primary goal of this technique is to simplify a complex integer programming problem into a linear programming one, which is generally easier to solve. Here's how it works: 1. **Original Problem**: Typically, an integer programming problem involves variables that are restricted to take only integer values (e.g., binary variables that can either be 0 or 1).