[Clp] CLP finds feasible model infeasible

Sat Jun 23 18:17:38 EDT 2012

Having small numbers in the objective and bounds is in practice not the
biggest problem, they will typical fall below feasibility tolerance and do
not induce an extra pivot. Small (or huge) numbers in the A matrix is much
more a concern. But I would also in general recommend to remove something
considered zero, which is represented by a tiny number.

On situation where tiny numbers can be a pain is in the automatic scaling
process, which can have a hard time judging if a number can be ignored or
not, these numbers may blow up to become significant after the scaling is
applied.

On Sat, Jun 23, 2012 at 10:35 PM, Nils Löhndorf <nils at loehndorf.com> wrote:

> Thanks for taking such a close look. The units of measure in the objective
> are all in EUR per 1000m^3 of water. Do you think I could solve the problem
> by rounding the coefficients to 0.01? Still, how do I know what would be
> the right scale?
>
>
> On Sat, Jun 23, 2012 at 9:59 PM, William H. Patton <pattonwh at comcast.net>wrote:
>
>>  The issue is still something about the units of measure for future vale
>> when compared to xx_flow and reservoir.
>> The objective coefficients ar between 20 and 200 or so  much like vars
>> genflow and pumpflow of the solution.
>> You are trying to get some balance about keeping water for the future
>> against using it now.
>>
>> Maybe in the  future rows  the rhs in millions cubic meters above the
>> minimum alternative auto_constraint_000048
>> But your flows ar constrained to a couple thousand cubic meters.   So you
>> should measure the futervalue wit  respect to those thousand cubic meters
>> scale.
>>
>> auto_constraint_000046: -reservoir0_22 +genflow_0_23 +spill_0_23
>> -pumpflow_0_23 +reservoir0_23 = 123.06493568;
>> auto_constraint_000047: -reservoir1_22 -genflow_0_23 -spill_0_23
>> +pumpflow_0_23 +genflow_1_23 +spill_1_23 +reservoir1_23 = 32.327515162;
>> // finish end of draw fill step 23    0_23 = 2797.  1_23 = 362.
>>
>> It is pretty clear that a rational scale for futurevalue is  around 500
>> to 5000  match the range of 0_23, 1_23 and the multipliers in the 4
>> constraints below
>>    try 1000 on each row.
>> auto_constraint_000048: -249.797613 reservoir0_23 -152.774953
>> reservoir1_23 +     * 1.0e3 *futureValue <= 0;
>> auto_constraint_000049: -1.10468e-012 reservoir0_23 +futureValue <=
>> 2615187.7031;
>> auto_constraint_000050: -183.116445 reservoir0_23 -61.0535182
>> reservoir1_23 +futureValue <= 48602.113987;
>> auto_constraint_000051: -169.716135 reservoir0_23 -21.0387706
>> reservoir1_23 +futureValue <= 100590.21035;
>>
>> I do not see any particular bad scale  of the tiny thing -1.10468e-012
>> reservoir0_23  but certainly it is wise to drop ( =0) numbers smaller than
>> say 0.01 in this problem.
>>
>>
>> Here is a screen shot sorted by value of the solution
>>
>>
>>
>> On 6/23/2012 5:31 AM, Nils Löhndorf wrote:
>>
>> Hi,
>>
>>  I have created another model formulation that crashes. I have redefined
>> the objective function and removed the buy/sell variables, which were a
>> legacy from another more complex formulation. I have also  tightened the
>> bounds of futureValue, so the RHS value have become a lot smaller.
>>
>>  This formulation behaves a lot better, but CLP still crashes. I suppose
>> it must be a numerical problem, because it works when I set the coefficient
>> of reservoir_0_23 in auto_constraint_49 to 0.0 instead of -1.10468e-12.
>> Also, turning off scaling helps. Is there some rule of thumb that I can
>> safely round a model coefficient to zero, as it would be treated as zero by
>> the optimizer anyways?
>>
>>  Thanks. Nils
>>
>>
>>
>>  On Thu, Jun 21, 2012 at 7:46 PM, Bo Jensen <jensen.bo at gmail.com> wrote:
>>
>>> Reposting this reply, since it bounced on my other email address, sorry
>>> for the double posting if it went through :
>>>
>>> Nils,John,
>>>
>>>  The two numbers are probably exactly equal in your running
>>> application, you loose precision on negative number writing the file
>>> because it makes room for the - sign. I have debugged these issues before,
>>> where a linear dependency checker failed because of this. I hope the file
>>> is not written with our software, because I think they should have equal
>>> precision no matter the sign :-)
>>>
>>>
>>>  On Thu, Jun 21, 2012 at 5:56 PM, John Forrest <
>>> john.forrest at fastercoin.com> wrote:
>>>
>>>>  Nils,
>>>>
>>>> Something to do with scaling.
>>>>
>>>> By fiddling about I can get it to be primal infeasible OR dual
>>>> infeasible with scaling.
>>>>
>>>> Looking more closely Clp is correct and all the other codes are wrong!
>>>>
>>>> You have sell/buy variables e.g.
>>>>
>>>>     sell_23 OBJROW 44.66755905  auto_constraint_000069 1.
>>>>     buy_23 OBJROW  -44.667559  auto_constraint_000069  -1.
>>>>
>>>> So the code wants to buy an infinite amount and then sell it at a small
>>>> profit.
>>>>
>>>> This was on about half the sell/buy pairs.  When I made all those bad
>>>> ones equal cost then it was fine.
>>>>
>>>> John Forrest
>>>>
>>>> On 21/06/12 15:49, Nils Löhndorf wrote:
>>>>
>>>>  Dear CLP mailing list members,
>>>>
>>>>  I have been testing CLP as part of a cutting planes algorithm to
>>>> solve stochastic optimization problems. My problem is that CLP frequently
>>>> finds a problem infeasible although the problem is definitely feasible. I
>>>> have tested the same model with other solvers such as Gurobi, Xpress and
>>>> Sulum, where I did not encounter this problem.
>>>>
>>>>  I have attached the mps file of a prototypical LP. When I read the
>>>> file from the console and solve the problem using "clp
>>>> maximize_infeasible.mps -max -dualsimplex", it returns "primal infeasible".
>>>> I have found out that with some LPs like the one attached, I just need to
>>>> increase the dual tolerance, e.g. using "clp maximize_infeasible.mps -max
>>>> -dualT 1.0 -dualsimplex". However, this does not always work.
>>>>
>>>>  Does anyone have an idea what is wrong here or what I have to do with
>>>> my model to avoid this behavior?
>>>>
>>>>  Best regards
>>>> Nils
>>>>
>>>>
>>>>  --
>>>>  Dr. Nils Löhndorf
>>>> Institut für Produktionsmanagement
>>>> Wirtschaftsuniversität Wien
>>>> Nordbergstraße 15, 1090 Wien, Austria
>>>> http://prodman.wu.ac.at
>>>> +43 1 31336 5629 <%2B43%201%2031336%205629>
>>>> nils.loehndorf at wu.ac.at
>>>>
>>>>
>>>>
>>>>  _______________________________________________
>>>> Clp mailing listClp at list.coin-or.orghttp://list.coin-or.org/mailman/listinfo/clp
>>>>
>>>>
>>>>
>>>> _______________________________________________
>>>> Clp mailing list
>>>> Clp at list.coin-or.org
>>>> http://list.coin-or.org/mailman/listinfo/clp
>>>>
>>>>
>>>
>>> _______________________________________________
>>> Clp mailing list
>>> Clp at list.coin-or.org
>>> http://list.coin-or.org/mailman/listinfo/clp
>>>
>>>
>>
>>
>> _______________________________________________
>> Clp mailing listClp at list.coin-or.orghttp://list.coin-or.org/mailman/listinfo/clp
>>
>>
>>
>>
>
> _______________________________________________
> Clp mailing list
> Clp at list.coin-or.org
> http://list.coin-or.org/mailman/listinfo/clp
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://list.coin-or.org/pipermail/clp/attachments/20120624/c321ec09/attachment.html>