Re: [Help-glpk] Help-glpk Digest, Vol 160, Issue 4

[Renan Silva]

For Binary Integer problems try: Karp, R. M. (1972). Reducibility among combinatorial problems.

and for MIP try: Papadimitriou, C. and Steiglitz, K. (1982). Combinatorial Optimization: Algo-
rithms and Complexity.

The general mip problem is NP-{Hard/Complete}

2016-03-07 14:00 GMT-03:00 <address@hidden>:

Send Help-glpk mailing list submissions to
        address@hidden

To subscribe or unsubscribe via the World Wide Web, visit
        https://lists.gnu.org/mailman/listinfo/help-glpk
or, via email, send a message with subject or body 'help' to
        address@hidden

You can reach the person managing the list at
        address@hidden

When replying, please edit your Subject line so it is more specific
than "Re: Contents of Help-glpk digest..."


Today's Topics:

   1. MIP problems (??????????? ???????)
   2. Re: MIP problems (Meketon, Marc)


----------------------------------------------------------------------

Message: 1
Date: Mon, 7 Mar 2016 15:02:10 +0200
From: ??????????? ???????       <address@hidden>
To: address@hidden
Subject: [Help-glpk] MIP problems
Message-ID:
        <CANrGraLRc7fdQhnd5x+38RZCr1Vx2oYm+M2Zq-+OB0wE=address@hidden>
Content-Type: text/plain; charset="utf-8"

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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.gnu.org/archive/html/help-glpk/attachments/20160307/7d5e8a92/attachment.html>

------------------------------

Message: 2
Date: Mon, 7 Mar 2016 09:46:15 -0600
From: "Meketon, Marc" <address@hidden>
To: ??????????? ???????         <address@hidden>, "address@hidden"
        <address@hidden>
Subject: Re: [Help-glpk] MIP problems
Message-ID: <address@hidden>
Content-Type: text/plain; charset="utf-8"

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: help-glpk-bounces+marc.meketon=address@hidden [mailto:help-glpk-bounces+marc.meketon=address@hidden] On Behalf Of ??SS??????S ?O????S
Sent: Monday, March 07, 2016 8:02 AM
To: address@hidden
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.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.gnu.org/archive/html/help-glpk/attachments/20160307/9fcaad95/attachment.html>

------------------------------

_______________________________________________
Help-glpk mailing list
address@hidden
https://lists.gnu.org/mailman/listinfo/help-glpk


End of Help-glpk Digest, Vol 160, Issue 4
*****************************************