[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [Help-glpk] MIP problems
|
From: |
Michael Hennebry |
|
Subject: |
Re: [Help-glpk] MIP problems |
|
Date: |
Mon, 7 Mar 2016 11:36:21 -0600 (CST) |
|
User-agent: |
Alpine 1.00 (DEB 882 2007-12-20) |
On Mon, 7 Mar 2016, ΤΑΣΣΟΠΟΥΛΟΣ ΙΩΑΝΝΗΣ wrote:
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?
MILP can solve satisfiability, the seminal NP-complete problem.
As noted by others, special cases of MILP are not necessarily NP-complete.
E.g. LP and assignment.
--
Michael address@hidden
"Sorry but your password must contain an uppercase letter, a number,
a haiku, a gang sign, a heiroglyph, and the blood of a virgin."
-- someeecards