[Top][All Lists]

[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

reply via email to

[Prev in Thread] Current Thread [Next in Thread]