4

In the paper "Some NP-complete problems in linear programming" (https://doi.org/10.1016/0167-6377(82)90006-2), there are several proofs given to show that testing for degeneracy in LPs is NP-complete. I don't understand the proof in section 4. Are they saying that their reduction only produces binary y values? Or are they introducing a binary variable (and thus invalidating their proof)? The statement of "the standard trick..." -- what is this trick? Does it have a name? Is someone able to write out this "combined system (5)" for me? What does it look like?

enter image description here

Brannon
  • 900
  • 2
  • 12
  • 1
    The "standard trick" is here (but reverse the roles of $x$ and $y$): https://or.stackexchange.com/questions/39/how-to-linearize-the-product-of-a-binary-and-a-non-negative-continuous-variable – RobPratt Apr 20 '22 at 15:44

0 Answers0