There are two different definitions of Integer Programming. Why?
Peter Cameron's Blog 2022-09-19
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?