1 Answers
In mathematics, the relaxation of a integer linear program is the problem that arises by removing the integrality constraint of each variable.
For example, in a 0–1 integer program, all constraints are of the form
The relaxation of the original integer program instead uses a collection of linear constraints
The resulting relaxation is a linear program, hence the name. This relaxation technique transforms an NP-hard optimization problem into a related problem that is solvable in polynomial time ; the solution to the relaxed linear program can be used to gain information about the solution to the original integer program.
4 views
Answered