<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
</head>
<body text="#000000" bgcolor="#FFFFFF">
<div class="moz-cite-prefix">Aleksandr,<br>
<br>
Stand alone clp has no problems, but I can reproduce the problem
using OsiClp.<br>
<br>
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.<br>
<br>
I have modified code to look at objective values and give up
earlier if they are not very large.<br>
<br>
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.<br>
<br>
John Forrest<br>
<br>
On 14/10/17 18:14, Aleksandr M. Kazachkov wrote:<br>
</div>
<blockquote type="cite"
cite="mid:CABsukBnBZ00gneeVg2o8vxR_Hw6qmQDWZEJMqD83xy49gJz=5g@mail.gmail.com">
<meta http-equiv="Context-Type" content="text/html; charset=UTF-8">
<div dir="ltr">Hi all,
<div><br>
</div>
<div>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.</div>
<div><br>
</div>
<div>LP format: <a
href="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="
moz-do-not-send="true">https://drive.google.com/file/d/0B6wQ0pEa5jXyTnFVSnktb2JxbEU/</a></div>
<div>IEEE hex MPS format: <a
href="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="
moz-do-not-send="true">https://drive.google.com/file/d/0B6wQ0pEa5jXyR0txVmREcngybXM/</a></div>
<div><br>
</div>
<div>The commands from which I encounter the error are:</div>
<div>solver->readLp("solverSlow.lp");<br>
</div>
<div>solver->setHintParam(OsiDoPresolveInInitial, 1);</div>
<div>solver->initialSolve();</div>
<div><br>
</div>
<div>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</div>
<div>
<p><br>
</p>
<p>Clp0006I 1 Obj 0 Primal inf 10.365599 (1)</p>
<p><br>
</p>
to
<p><br>
</p>
<p>Clp0006I 201 Obj 4.203557e-12 Primal inf 131157.64 (2351)</p>
<p><br>
</p>
and this latter type of entry is the one that continues
indefinitely.</div>
<div><br>
</div>
<div>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.</div>
<div><br>
</div>
<div>
<div>Here are some properties of this LP.</div>
<div>1. There are 4823 constraints, 668 variables, and 318711
non-zeroes in the coefficient matrix. </div>
<div>2. The coefficient range is 0.000178573 to 1155.46. The
RHS for each row is either 0 or 1, and all constraints are
>=.</div>
<div>3. The objective is all-zeroes. </div>
<div>4. There are many free variables.</div>
</div>
<div><br>
</div>
<div>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.</div>
<div><br>
</div>
<div>Thank you in advance for your help,</div>
<div>Aleksandr Kazachkov</div>
</div>
<br>
<fieldset class="mimeAttachmentHeader"></fieldset>
<br>
<pre wrap="">_______________________________________________
Clp mailing list
<a class="moz-txt-link-abbreviated" href="mailto:Clp@list.coin-or.org">Clp@list.coin-or.org</a>
<a class="moz-txt-link-freetext" href="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=">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=</a>
</pre>
</blockquote>
<p><br>
</p>
</body>
</html>