Alice and Bob have the following conversation.

===============================

ALICE: In your book you define INT PROG as, given a matrix A and vectors b,c,

find the integer vector x such that Ax\le b and c DOT x is maximized.

This is not correct! You also need x\ge 0.

BOB: Really? I always heard it without that extra constraint, though I am

sure they are equivalent and both NP-complete (Alice nods).

Where did you see it defined with that extra constraint?

ALICE:

Chapter of a book at an MIT website

The book *Graphs, Networks and Algorithms* by Dieter Jungnickel

Bob, do you have examples where they do not use that extra constraint.

BOB:

Lecture notes from Lehigh Univ.

The book *Parameterized Complexity Theory* by Flum and Grohe

The book *Computers and Intractability : A Guide to the Theory of NP-Completeness* by Garey and Johnson

ALICE: Both of our lists are impressive. So now what?

--------------------------------------------------------------------

(This is Bill again.)

What indeed!

1) Why are there two definitions of Int Prog?

2) When is it good to use which one?

Ax \leq b can capture x >= 0

ReplyDeleteSimilarly if you don't want x>=0 but the model requires it, use two new vectors, y and z, and replace each x_i with y_i-z_i.

ReplyDeleteWith emphasizes the connection to lp (which needs the condition) even though it's not needed np-wise for the discrete case. On that basis solver/practitioner docs would include it but not theory work. Maybe?

ReplyDeleteThere are also several different, so-called "standard" or "canonical" forms for LP. You typically just use whichever equivalent definition is more convenient for the application at hand. Why is that a problem?

ReplyDeleteMy personal guess is that x>=0 is mostly just getting copied from LP so IP that IP == LP+integral variable constraints. Compare https://en.wikipedia.org/wiki/Linear_programming and https://en.wikipedia.org/wiki/Integer_programming. The x>=0 does help in the pedagogy of LP. The operations for simplex start needing several [mostly uninteresting] case splits if you try to explain them without simplifications. For example, x>=0 gets used by both the entering and leaving variable selection in the wiki description: https://en.wikipedia.org/wiki/Simplex_algorithm#Algorithm .

ReplyDeleteMy impression (from ordinary linear programming, but why would integer programming be different?) is that the x >= 0 constraints are very convenient when you formulate the dual linear program and prove the duality theorems relating the dual LP to the primal LP. I've tried fiddling with how to do duality when you omit the x >= 0 constraints, and the proofs grew longer and less readable.

ReplyDeleteBut maybe somebody has figured out an equally elegant way to prove the standard duality results without the x >= 0 constraints? If anyone knows a reference to that, I would like to read it, please.