[Clp] Infeasible LP that causes slow performance or possible cycling

[John Forrest]

Aleksandr,

Stand alone clp has no problems, but I can reproduce the problem using 
OsiClp.

Primal simplex tries to do a one phase solve - giving a large weight to 
infeasibilities.  If the problem seems infeasible, it will increase this 
weight until it thinks it is large enough to declare infeasibility.  In 
this case it got to the point where it got a fake result.  Also in this 
case, the code was being stupid as there was no objective function so it 
should have given up at once.

I have modified code to look at objective values and give up earlier if 
they are not very large.

I think this is perfectly safe.  At present the maximum cost given to an 
infeasibility before giving up is  MAX_INFEASIBILITY_COST (1.0e18).  If 
this is defined as 1.0e18 (default) then these extra tests are done.  To 
keep to previous behaviour add -DMAX_INFEASIBILITY_COST=1.000001e18 (or 
whatever) in configure.

John Forrest

On 14/10/17 18:14, Aleksandr M. Kazachkov wrote:
> Hi all,
>
> I have an LP that is (almost certainly) primal infeasible, but Clp 
> (revision 2282) seems to struggle with it when presolve is on, not 
> solving within an hour, and perhaps cycling indefinitely. The LP is 
> linked below both in LP format and IEEE hex MPS format.
>
> LP format: 
> https://drive.google.com/file/d/0B6wQ0pEa5jXyTnFVSnktb2JxbEU/ 
> <https://urldefense.proofpoint.com/v2/url?u=https-3A__drive.google.com_file_d_0B6wQ0pEa5jXyTnFVSnktb2JxbEU_view-3Fusp-3Dsharing&d=DwMFaQ&c=Ngd-ta5yRYsqeUsEDgxhcqsYYY1Xs5ogLxWPA_2Wlc4&r=js2M0T-3OIMIVDvokcKjokJbk0F8QOCd0mT4FsVFE88&m=2IFJgxpEvPYQQjAKYcB7hMhWUOwpxxlG3K9IVmiCFgk&s=iHX3JP4MIuAcSVCZyaJu1dWsg-wFF4dfy445wglaYx0&e=>
> IEEE hex MPS format: 
> https://drive.google.com/file/d/0B6wQ0pEa5jXyR0txVmREcngybXM/ 
> <https://urldefense.proofpoint.com/v2/url?u=https-3A__drive.google.com_file_d_0B6wQ0pEa5jXyR0txVmREcngybXM_&d=DwMFaQ&c=Ngd-ta5yRYsqeUsEDgxhcqsYYY1Xs5ogLxWPA_2Wlc4&r=js2M0T-3OIMIVDvokcKjokJbk0F8QOCd0mT4FsVFE88&m=2IFJgxpEvPYQQjAKYcB7hMhWUOwpxxlG3K9IVmiCFgk&s=uCDAgO-laXY5NSb0Ase-KfR9ud7584dCLAXCLC1v0Ms&e=>
>
> The commands from which I encounter the error are:
> solver->readLp("solverSlow.lp");
> solver->setHintParam(OsiDoPresolveInInitial, 1);
> solver->initialSolve();
>
> If I save the LP with normal or extra precision (instead of with IEEE 
> hex), then primal infeasibility is declared within ten seconds or so. 
> Similarly, if the line setting OsiDoPresolveInInitial to 1 is 
> commented out, the model solves quickly. The full model with presolve 
> on is what causes trouble, and in particular, the issue is encountered 
> during postsolve. There is a step in which, during postsolve, the log 
> transitions from
>
>
> Clp0006I 1  Obj 0 Primal inf 10.365599 (1)
>
>
> to
>
>
> Clp0006I 201  Obj 4.203557e-12 Primal inf 131157.64 (2351)
>
>
> and this latter type of entry is the one that continues indefinitely.
>
> I am looking for advice on what parameter to set or cleaning of the LP 
> to do in advance, as well as reporting the experience in case 
> something can be changed in Clp to handle this type of case.
>
> Here are some properties of this LP.
> 1. There are 4823 constraints, 668 variables, and 318711 non-zeroes in 
> the coefficient matrix.
> 2. The coefficient range is 0.000178573 to 1155.46. The RHS for each 
> row is either 0 or 1, and all constraints are >=.
> 3. The objective is all-zeroes.
> 4. There are many free variables.
>
> I can imagine that the coefficient range may cause numerical 
> instability, but it does not seem so terribly bad at first glance. 
> Something I have encountered before is when coefficients are not small 
> themselves, but the differences between the coefficients are very 
> small, then some solvers encounter issues. The behavior I see may be 
> related to this, as there are such "similar" coefficients in this 
> model, and it is also suggested by the fact that saving the model with 
> different precision so dramatically changes things.
>
> Thank you in advance for your help,
> Aleksandr Kazachkov
>
>
> _______________________________________________
> Clp mailing list
> Clp at list.coin-or.org
> https://urldefense.proofpoint.com/v2/url?u=https-3A__list.coin-2Dor.org_mailman_listinfo_clp&d=DwICAg&c=Ngd-ta5yRYsqeUsEDgxhcqsYYY1Xs5ogLxWPA_2Wlc4&r=js2M0T-3OIMIVDvokcKjokJbk0F8QOCd0mT4FsVFE88&m=2IFJgxpEvPYQQjAKYcB7hMhWUOwpxxlG3K9IVmiCFgk&s=yYEDcr71ZDilo36vHuZt1iJK2EWSaqQR03y3F25B6H0&e=


-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://list.coin-or.org/pipermail/clp/attachments/20171016/ff7c1e66/attachment.html>