[Coin-lpsolver] determining infeasibility in ClpInterior
Erling D. Andersen
e.d.andersen at mosek.com
Fri Nov 17 08:02:33 EST 2006
Hi
Now I am not totally familiar with the interior-point alg. implemented in CLP.
But at least the usually primal-dual alg. cannot deal with primal and/or dual infeasible problems
in a theoretical sound way. One way to solve the problem is to use the
primal-dual homogeneous algorithm described in
http://www.mosek.com/homepages/e.d.andersen/papers/linopt.pdf
for instance (see section 5.8) and the references therein.
MOSEK which is callable from OSI implements the homogeneous interior-point algorithm.
See www.mosek.com if you are interested.
I should admit I am the author of MOSEK.
Best regards
Erling
>----------------------------------------------------------------------
>
>Message: 1
>Date: Fri, 17 Nov 2006 00:49:10 +0000
>From: Kish Shen <kish.shen at crosscoreop.com>
>Subject: [Coin-lpsolver] determining infeasibility in ClpInterior
>To: coin-lpsolver at list.coin-or.org
>Message-ID: <200611170049.10508.kish.shen at crosscoreop.com>
>Content-Type: text/plain; charset="us-ascii"
>
>Hi,
>
>I have been testing out ClpInterior with some test cases, and for the following simple problem:
>
>objective: min(X)
>
>subject to:
>
>X + Y >= 3
>X + Y <= 2
>X - Y = 0
>
>which is obviously infeasible, and when I solve the problem with Clp's Simplex, this is indeed
>what I get. However, when I solve the problem with ClpInterior, I get a solution (with X and
>Y = 1).
>
>Looking at the code:
>
> lpd->lp->interiormodel->setCholesky(cholesky);
> lpd->lp->interiormodel->primalDual();
> // Barrier done
>
> if (lpd->lp->interiormodel->isProvenOptimal())
> {
> // Do crossover if optimal...
> .....
> }
>
>where lpd->lp->interiormodel is a ClpInterior *, the isProvenOptimal() method returns true.
>I assume it should not?
>
>--Kish Shen
>
>
>
>------------------------------
>
>Message: 2
>Date: Fri, 17 Nov 2006 03:23:01 +0000
>From: Kish Shen <kish.shen at crosscoreop.com>
>Subject: [Coin-lpsolver] determining unbounded problems with
> ClpInterior
>To: coin-lpsolver at list.coin-or.org
>Message-ID: <200611170323.01100.kish.shen at crosscoreop.com>
>Content-Type: text/plain; charset="us-ascii"
>
>Hi,
>
>In another test I am trying with ClpInterior, an unbounded problem:
>
>objective: maximise(X)
>
>subject to:
> X +Y >= 3
> X - Y = 0
>
>When I tried to solve this with ClpInterior, I was unable to determine that this problem was
>unbounded. Is there anyway I can do this?
>
>Another issue with this problem: I get a lot of messages like:
>
>large perturbation 1e+06
>large diagonal 1.12199e+31
>large diagonal 1.12199e+31
>
>when solving this problem. These messages seem to be printed directly to std::cout, rather
>going through the normal coin message handling -- should they be printed directly like this?
>
>Thanks in advance for any help!
>
>--Kish Shen
>
>
>
>------------------------------
>
>Message: 3
>Date: Fri, 17 Nov 2006 04:40:17 -0500
>From: John J Forrest <jjforre at us.ibm.com>
>Subject: Re: [Coin-lpsolver] determining infeasibility in ClpInterior
>Cc: coin-lpsolver at list.coin-or.org
>Message-ID:
> <OF53192280.BA7FF3BC-ON85257229.0033B418-85257229.00351F4F at us.ibm.com>
>Content-Type: text/plain; charset=US-ASCII
>
>It is a known defect that the Clp barrier does not detect infeasibility or
>unboundedness correctly. It is on my list of the 100 things most wanted
>:-)
>
>On getting solutions use dualRowSolution() and/or primalColumnSolution()
>and check feasibility (either by hand or by checkSolution();
>
>messages should be out by default on trunk and branches/devel
>
>John Forrest
>
>
>
> Kish Shen
> <kish.shen at crossc
> oreop.com> To
> Sent by: coin-lpsolver at list.coin-or.org
> coin-lpsolver-bou cc
> nces at list.coin-or
> .org Subject
> [Coin-lpsolver] determining
> infeasibility in ClpInterior
> 11/16/06 07:49 PM
>
>
>
>
>
>
>
>
>
>Hi,
>
>I have been testing out ClpInterior with some test cases, and for the
>following simple problem:
>
>objective: min(X)
>
>subject to:
>
>X + Y >= 3
>X + Y <= 2
>X - Y = 0
>
>which is obviously infeasible, and when I solve the problem with Clp's
>Simplex, this is indeed
>what I get. However, when I solve the problem with ClpInterior, I get a
>solution (with X and
>Y = 1).
>
>Looking at the code:
>
> lpd->lp->interiormodel->setCholesky(cholesky);
> lpd->lp->interiormodel->primalDual();
> // Barrier done
>
> if (lpd->lp->interiormodel->isProvenOptimal())
> {
> // Do crossover if optimal...
> .....
> }
>
>where lpd->lp->interiormodel is a ClpInterior *, the isProvenOptimal()
>method returns true.
>I assume it should not?
>
>--Kish Shen
>
>_______________________________________________
>Coin-lpsolver mailing list
>Coin-lpsolver at list.coin-or.org
>http://list.coin-or.org/mailman/listinfo/coin-lpsolver
>
>
>
>
>------------------------------
>
>Message: 4
>Date: Fri, 17 Nov 2006 23:26:31 +1100
>From: "Ricky O'Brien" <rickob at internode.on.net>
>Subject: [Coin-lpsolver] Problem with COIN MIP solver
>To: <coin-lpsolver at list.coin-or.org>
>Message-ID: <000001c70a43$9df53d50$0301a8c0 at ob003f6r4o96u1>
>Content-Type: text/plain; charset="us-ascii"
>
>Skipped content of type multipart/alternative-------------- next part --------------
>A non-text attachment was scrubbed...
>Name: 2006-01-01 0330.zip
>Type: application/octet-stream
>Size: 86218 bytes
>Desc: not available
>Url : http://list.coin-or.org/pipermail/coin-lpsolver/attachments/20061117/64a521e3/2006-01-010330.obj
>
>------------------------------
>
>_______________________________________________
>Coin-lpsolver mailing list
>Coin-lpsolver at list.coin-or.org
>http://list.coin-or.org/mailman/listinfo/coin-lpsolver
>
>
>End of Coin-lpsolver Digest, Vol 25, Issue 6
>********************************************
*************************************************************************
MOSEK ApS
C/O Symbion Science Park
Fruebjergvej 3, Boks 16
DK-2100 Copenhagen O
Denmark
Phone (work): +45 3917 9907
Mobile-phone: +45 2362 9520
Fax: +45 3917 9823
Email: e.d.andersen at mosek.com
Skype: erling.d.andersen
Homepage: http://erling.andersen.name
http://www.mosek.com/homepages/e.d.andersen/
*************************************************************************
More information about the Clp
mailing list