= Linear programming relaxation
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.
Back to article page
