Reformulation

From Glossary

Jump to: navigation, search

Obtaining a new formulation of a problem that is in some sense better, but equivalent to a given formulation. For example, consider the packing constraint: at most 1 element can be selected from LaTeX: \textstyle \left \{1, \dots, n \right \}. Letting LaTeX: x_j be the associated binary variable, the following formulations have the same feasibility region:

  1. LaTeX: 
x_i + x_j \le 1 \mbox{ for all } i < j, j=2, \dots,n;
  2. LaTeX: 
x_1 + x_2 + \dots + x_n \le 1.

Formulation 2 is better because its LP relaxation is sharper: the relaxed region for 2 is a proper subset of the relaxed region for 1.


Views
Personal tools