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 <[email protected]>:
> Send Help-glpk mailing list submissions to
> [email protected]
>
> 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
> [email protected]
>
> You can reach the person managing the list at
> [email protected]
>
> 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: ??????????? ??????? <[email protected]>
> To: [email protected]
> Subject: [Help-glpk] MIP problems
> Message-ID:
> <CANrGraLRc7fdQhnd5x+38RZCr1Vx2oYm+M2Zq-+OB0wE=
> [email protected]>
> 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" <[email protected]>
> To: ??????????? ??????? <[email protected]>, "[email protected]"
> <[email protected]>
> Subject: Re: [Help-glpk] MIP problems
> Message-ID: <04B026E012A010408111AFE9C67000A1238B735A3B@owgusdfwmbx03>
> 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: [email protected] [mailto:
> [email protected]] On Behalf Of
> ??SS??????S ?O????S
> Sent: Monday, March 07, 2016 8:02 AM
> To: [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.
> -------------- 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
> [email protected]
> https://lists.gnu.org/mailman/listinfo/help-glpk
>
>
> End of Help-glpk Digest, Vol 160, Issue 4
> *****************************************
>
_______________________________________________
Help-glpk mailing list
[email protected]
https://lists.gnu.org/mailman/listinfo/help-glpk
