Let’s discuss the assignment problem, perhaps one of the simplest network flow problems. It is a zero-one (binary) integer program, and if you look at the
literature at the formulation of the assignment problem, it always has an explicit constraint that the variables must be {0,1}. It is considered to be an integer program.
If an interior point algorithm that follows the central path is used to solve the relaxation of an assignment problem, then often a non-integer solution is
found because (usually) there are multiple optimum present. [Using an extreme-point algorithm will, due to the totally unimodular nature of the basis, result in an integer solution.] Point is that solving the assignment problem as an LP by itself is no guarantee
that you solve the IP problem.
Because of that, in my opinion, the assignment problem is not an LP problem, it is an IP problem.
My larger point is that there are many problems that have an Integer Programming formulation, but can be solved in polynomial time. Just because a problem
can have an IP formulation does not mean it is NP-hard.
Not sure if this is the appropriate place to discuss this – by itself it does not have anything to do with GLPK.
From: address@hidden [mailto:address@hidden
Sent: Monday, March 07, 2016 11:00 AM
To: Meketon, Marc
Cc: ΤΑΣΣΟΠΟΥΛΟΣ ΙΩΑΝΝΗΣ; address@hidden
Subject: Re: [Help-glpk] MIP problems
Network flow problems are LP, not MIP. Integer Programming is NP-Hard.
MIP problems are both. Depends on the problem… Network flow problems are MIP problems that are solved in polynomial time, and Knapsack problems are MIP problems
which are NP-hard.
I have been aware that MIP problems are NP-Complete or even NP-Hard.
Does any one know a reference (perhaps a published paper) in which it is proven that MIP problems are NP- Complete or NP- Hard?
Thank you very much for your time and for any answer.
This e-mail and any attachments may be confidential or legally privileged. If you received this message in error or are not the intended recipient, you should destroy
the e-mail message and any attachments or copies, and you are prohibited from retaining, distributing, disclosing or using any information contained herein. Please inform us of the erroneous delivery by return e-mail. Thank you for your cooperation.
_______________________________________________
Help-glpk mailing list
address@hidden
https://lists.gnu.org/mailman/listinfo/help-glpk