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: [email protected] [mailto:[email protected]]
Sent: Monday, March 07, 2016 11:00 AM
To: Meketon, Marc
Cc: ΤΑΣΣΟΠΟΥΛΟΣ ΙΩΑΝΝΗΣ; [email protected]
Subject: Re: [Help-glpk] MIP problems
Network flow problems are LP, not MIP. Integer Programming is NP-Hard.
Giorgio
On 07 Mar 2016, at 23:46, Meketon, Marc
<[email protected]<mailto:[email protected]>> wrote:
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.
From:
[email protected]<mailto:[email protected]>
[mailto:[email protected]] On Behalf Of
??SS??????S ?O????S
Sent: Monday, March 07, 2016 8:02 AM
To: [email protected]<mailto:[email protected]>
Subject: [Help-glpk] MIP problems
Hi to everyone,
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.
Ioannis Tassopoulos
________________________________
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
[email protected]<mailto:[email protected]>
https://lists.gnu.org/mailman/listinfo/help-glpk
________________________________
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
[email protected]
https://lists.gnu.org/mailman/listinfo/help-glpk
