One of the most fruitful notion of generalized solution in optimization and combinatorics is linear programming relaxation. Quoting from the wikipedia article: In mathematics, the linear programming relaxation of a 0-1 integer program is the problem that arises by replacing the constraint that each variable must be 0 or 1 by a weaker constraint, that each variable belong to the interval [0,1].
Gil Kalai
- 24.7k
- 38
- 235
- 327