tag:blogger.com,1999:blog-3722233.post6364865158369002106..comments2022-09-27T13:51:30.964-05:00Comments on Computational Complexity: There are two different definitions of Integer Programming. Why? Lance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger6125tag:blogger.com,1999:blog-3722233.post-55476016661536317452022-09-21T05:51:56.668-05:002022-09-21T05:51:56.668-05:00My impression (from ordinary linear programming, b...My 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.<br /><br />But 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.Jonathanhttps://www.blogger.com/profile/04699323493832882000noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-32561660415627242032022-09-20T22:28:42.843-05:002022-09-20T22:28:42.843-05:00My personal guess is that x>=0 is mostly just g...My 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 .Tim Knoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-78500481570344470572022-09-20T20:55:28.856-05:002022-09-20T20:55:28.856-05:00There are also several different, so-called "...There 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?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-36646023733203652442022-09-20T07:27:31.007-05:002022-09-20T07:27:31.007-05:00With emphasizes the connection to lp (which needs ...With 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?Data Finnovationhttps://www.blogger.com/profile/13458274082472782987noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-17643987827675282942022-09-20T07:27:26.895-05:002022-09-20T07:27:26.895-05:00Similarly if you don't want x>=0 but the mo...Similarly 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.Lance Fortnowhttps://www.blogger.com/profile/06752030912874378610noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-44166927698934113182022-09-20T06:58:24.081-05:002022-09-20T06:58:24.081-05:00Ax \leq b can capture x >= 0Ax \leq b can capture x >= 0Unknownhttps://www.blogger.com/profile/17017097307300614331noreply@blogger.com