linear programming line removal optimal solution

2018-08-03

An answer to this question on Stack Overflow.

Question

How would I prove the constraints in line 35.19 are redundant in this linear program in that if we remove them in lines (35.17) – (35.20), any optimal solution to the linear program must satisfy x(v)≤1 for each v∈V. LP

I think I need to use the relaxation version of linear program but am not sure. Beyond that I am not sure how I would prove this.

Answer

You're already looking at a relaxed version of the program, otherwise your variables would be constrained to being members of a set.

Likely you need to consider the dual of this program, which will convert >= constraints into <= constraints.