[Symphony] Issue: get No solution in Symphony
Vladyslav Kolbasin
marcell at insart.com
Tue Apr 5 02:23:56 EDT 2011
Thanks a lot!
We will try to use CPLEX 12.2 for research too.
> The fact that one of your basis matrices has a condition number of
> 10^18 means there is almost no chance of an accurate solution. This is
> why you are having trouble.
We haven't enough knowledge of any solver's inner workings, but it is
some explanation of what there is happening.
Thanks, Vladyslav
On Mon, 4 Apr 2011 23:08:57 -0400, Ted Ralphs <ted at Lehigh.EDU> wrote:
> I ran your problem through CPLEX 12.2, which has an option to analyze
> the stability of the problem. Here is the output for your model:
>
> MILP objective -3.4859040232e+04
> MILP solution norm |x| (Total, Max) 6.91504e+03 5.75850e+02
> MILP solution error (Ax=b) (Total, Max) 1.01438e-11 8.81073e-13
> MILP x bound error (Total, Max) 0.00000e+00 0.00000e+00
> MILP x integrality error (Total, Max) 0.00000e+00 0.00000e+00
> MILP slack bound error (Total, Max) 2.11658e-08 2.11657e-08
>
> Branch-and-cut subproblem optimization:
> Max condition number: 7.4102e+18
> Percentage of stable bases: 3.9%
> Percentage of suspicious bases: 0.0%
> Percentage of unstable bases: 92.5%
> Percentage of ill-posed bases: 3.6%
> Attention level: 0.313901
>
> The fact that one of your basis matrices has a condition number of
> 10^18 means there is almost no chance of an accurate solution. This is
> why you are having trouble.
>
> Cheers,
>
> Ted
>
> On Tue, Mar 29, 2011 at 6:31 PM, Ted Ralphs <ted at lehigh.edu> wrote:
>> Most likely, the constraint matrix is ill-conditioned, which means
>> that it will be very difficult to get a precise answer in fixed
>> precision. In that case, there may not be a lot the solver can do. As
>> Menal indicated, even the commercial solvers don't agree on the
>> solution to this instance. You probably have to improve the model
>> somehow before handing it to the solver. You might be able to use the
>> conditionNumber() subroutine in the CoinFactorization class in
>> CoinUtils if you want to get an idea of the conditioning of your
>> constraint matrix.
>>
>> Cheers,
>>
>> Ted
>>
>> On Tue, Mar 29, 2011 at 4:33 PM, Menal Guzelsoy <megb at lehigh.edu> wrote:
>>> The MPS instance is not 'stable'. It seems that the LP solver gets
>>> stuck in solving one of the subproblems. If you run it with other
>>> solvers, you will get different results. Gurobi even gives a warning
>>> that the final solution violates some of the constraints for the
>>> solver's tolerance value.
>>>
>>>> 1) Is it possible that saving MPS file occured with lose accuracy ?
>>>
>>> Correct. LP and MPS formats write the constants up to some certain
>>> digits. If you compare these two files, you will see that the
>>> coefficients are not exactly same.
>>>
>>>> 2) What about simplest solution i wrote? How in this case does LP can
>>>> be infeasible?
>>>
>>> The LP solver is not an exact solver. You do not deal with perfect
>>> zeros but values with small errors which are accumulated in
>>> constraints. For instance, the values x1=5e-8, x2=6e-8 violate the
>>> constraint x1+x2 = 0 for a tolerance value 1e-7 even though you would
>>> assume x1 and x2 zeros. The issue gets worse if you have large
>>> coefficients in the constraint.
>>>
>>>> 3) How mixing variables and constraints can affect or not affect this
>>>> issue? (wrote about this in first letter)
>>>
>>> Mixing variables and constraints gives a different constraint matrix
>>> which would yield a different factorization and a different path
>>> followed through simplex iterations.
>>>
>>> Menal.
>>>
>>> Menal Guzelsoy
>>> 1610 4620455
>>>
>>>
>>>
>>> On Tue, Mar 29, 2011 at 1:16 PM, Vladyslav Kolbasin <marcell at insart.com> wrote:
>>>>
>>>> Menal,
>>>>
>>>> It is strange: if I load LP task from MPS file (using sym_read_mps()) i
>>>> sent to you
>>>> then i don't have issue with NO_SOLUTION. Rather i don't get it at
>>>> once.
>>>> But symphony stops somewhere during solving and it seems do nothing or
>>>> get into infinite loop - don't know exactly.
>>>> Here is last part of log:
>>>>
>>>> ......
>>>>
>>>> **** Starting iteration 12 ****
>>>>
>>>> The LP value is: -33794.044 [0,9]
>>>>
>>>> Now displaying the relaxed solution ...
>>>> Row effectiveness: rownum: 798 ineff: 0 deletable: 0
>>>>
>>>> Receiving/creating cuts...
>>>>
>>>> Cuts in the local pool: 0
>>>>
>>>>
>>>> In iteration 12, before calling branch()
>>>> ... no cuts were added.
>>>> Now displaying final relaxed solution...
>>>>
>>>> TM: node 59: uind:WRT(0,0) nf:N/A cind:WRT(0,0)
>>>> bvar:EXP evar:WRT brow:WRT erow:WRT
>>>> Branching on variable C0000896
>>>> children: [-33771.536, 3,13] [39065007122.593, 3,21]
>>>> Generating node 61 from 59...
>>>> Generating node 62 from 59...
>>>> Decided to dive...
>>>> *************************************************
>>>> * Now processing NODE 61 LEVEL 20
>>>> *************************************************
>>>>
>>>>
>>>>
>>>> **** Starting iteration 13 ****
>>>>
>>>> The LP value is: -33771.536 [0,14]
>>>>
>>>> Now displaying the relaxed solution ...
>>>> Row effectiveness: rownum: 798 ineff: 0 deletable: 0
>>>>
>>>> Receiving/creating cuts...
>>>>
>>>> Cuts in the local pool: 0
>>>>
>>>>
>>>> In iteration 13, before calling branch()
>>>> ... no cuts were added.
>>>> Now displaying final relaxed solution...
>>>>
>>>> feasibility pump: cuts discarded = 4
>>>> fp: norm_c = 7071.125299
>>>> feasibility pump: starting iteration 0, time used = 0.00
>>>> fp: solve lp 0
>>>> fp: norm = 141.421356
>>>> feasibility pump: starting iteration 1, time used = 0.00
>>>> fp: solve lp 1
>>>> fp: norm = 141.421356
>>>> feasibility pump: starting iteration 2, time used = 0.01
>>>> fp: solve lp 2
>>>> fp: norm = 141.421356
>>>> feasibility pump: starting iteration 3, time used = 0.01
>>>> fp: solve lp 3
>>>> fp: norm = 141.421356
>>>> feasibility pump: starting iteration 4, time used = 0.02
>>>> fp: solve lp 4
>>>> fp: norm = 141.421356
>>>> feasibility pump: starting iteration 5, time used = 0.02
>>>> fp: solve lp 5
>>>> fp: norm = 141.421356
>>>> feasibility pump: starting iteration 6, time used = 0.02
>>>> fp: solve lp 6
>>>> fp: norm = 141.421356
>>>> feasibility pump: starting iteration 7, time used = 0.02
>>>> fp: same as 6
>>>> fp: flipping
>>>> fp: flipping 26
>>>> fp: solve lp 7
>>>> fp: norm = 141.421356
>>>> feasibility pump: starting iteration 8, time used = 0.04
>>>> fp: solve lp 8
>>>> fp: norm = 141.421356
>>>> feasibility pump: starting iteration 9, time used = 0.04
>>>> fp: same as 8
>>>> fp: flipping
>>>> fp: flipping 22
>>>> fp: solve lp 9
>>>> fp: norm = 141.421356
>>>> feasibility pump: starting iteration 10, time used = 0.06
>>>> fp: solve lp 10
>>>> fp: norm = 141.421356
>>>> feasibility pump: starting iteration 11, time used = 0.06
>>>> fp: same as 10
>>>> fp: flipping
>>>> fp: flipping 23
>>>> fp: solve lp 11
>>>> fp: norm = 141.421356
>>>> feasibility pump: starting iteration 12, time used = 0.08
>>>> fp: solve lp 12
>>>> fp: norm = 141.421356
>>>> feasibility pump: starting iteration 13, time used = 0.10
>>>> fp: same as 12
>>>> fp: flipping
>>>> fp: flipping 27
>>>> fp: solve lp 13
>>>> fp: norm = 141.421356
>>>> feasibility pump: starting iteration 14, time used = 0.12
>>>> fp: solve lp 14
>>>> fp: norm = 141.421356
>>>> feasibility pump: starting iteration 15, time used = 0.12
>>>> fp: same as 14
>>>> fp: flipping
>>>> fp: flipping 26
>>>> fp: solve lp 15
>>>> fp: norm = 141.421356
>>>> feasibility pump: starting iteration 16, time used = 0.14
>>>> fp: solve lp 16
>>>> fp: norm = 141.421356
>>>>
>>>>
>>>> I didn't get any logs after this place, besides i set time_limit and it
>>>> was expired a lot.
>>>>
>>>>> ... My guess is that the constraint matrix that you create is not well defined (check
>>>>> the fractional constants in MPS file) ...
>>>>
>>>> I don't understand good MPS format good, but
>>>> What about simplest solution i wrote? How in this case does LP can be
>>>> infeasible even if errors are in some constants?
>>>> Structure of my LP is so that all zeros is always possible solution.
>>>>
>>>> SO:
>>>>
>>>> 1) Is it possible that saving MPS file occured with lose accuracy ?
>>>> 2) What about simplest solution i wrote? How in this case does LP can
>>>> be infeasible?
>>>> 3) How mixing variables and constraints can affect or not affect this
>>>> issue? (wrote about this in first letter)
>>>>
>>>> Vladyslav
>>>>
>>>>
>>>>
>>>> On Tue, 29 Mar 2011 07:35:22 -0400, Menal Guzelsoy <megb at lehigh.edu>
>>>> wrote:
>>>>> Vladyslav,
>>>>>
>>>>> I could not replicate the error. Can you try reading the problem from
>>>>> these files and see if you are still getting the error? My guess is
>>>>> that the constraint matrix that you create is not well defined (check
>>>>> the fractional constants in MPS file) and the LP solver declares the
>>>>> problem infeasible due to some tolerance issues.
>>>>>
>>>>> Menal.
>>>>>
>>>>> Menal Guzelsoy
>>>>> 1610 4620455
>>>>>
>>>>>
>>>>>
>>>>> On Tue, Mar 29, 2011 at 6:19 AM, Vladyslav Kolbasin
>>>>> <marcell at insart.com> wrote:
>>>>>>
>>>>>> Here is problem in both formats. It is rather large, but on smaller
>>>>>> problems i couldn't reproduce it.
>>>>>>
>>>>>> Also simplest solution i know in it:
>>>>>> variables:
>>>>>> x0 = 250
>>>>>> x396 = 500
>>>>>> x813 = 1
>>>>>> x886 = 1
>>>>>> all others = 0
>>>>>>
>>>>>> Thanks a lot. Vladyslav
>>>>>>
>>>>>> On Mon, 28 Mar 2011 13:42:57 -0400, Menal Guzelsoy <megb at lehigh.edu>
>>>>>> wrote:
>>>>>>> Can you send us the problem in LP or MPS format?
>>>>>>>
>>>>>>> Menal Guzelsoy
>>>>>>> 1610 4620455
>>>>>>>
>>>>>>>
>>>>>>>
>>>>>>> On Mon, Mar 28, 2011 at 1:11 PM, Vladyslav Kolbasin
>>>>>>> <marcell at insart.com> wrote:
>>>>>>>>
>>>>>>>> No i didn't set common bounds (upper_bound & lower_bound or
>>>>>>>> ..._bound_estimate)
>>>>>>>>
>>>>>>>> I tryed to set them (upper_bound & lower_bound) in wide range - nothing
>>>>>>>> changed and i still have NO_SOLUTION
>>>>>>>>
>>>>>>>>
>>>>>>>> Thanks a lot.
>>>>>>>>
>>>>>>>> On Mon, 28 Mar 2011 11:32:14 -0400, Ted Ralphs <tkralphs at Lehigh.EDU>
>>>>>>>> wrote:
>>>>>>>>> If you would be so kind as the post your inquiry to the mailing list,
>>>>>>>>> we will try to get you an answer. Fomr the output, it looks as thought
>>>>>>>>> you must be setting an a priori upper bound and the solver is not able
>>>>>>>>> to imprve on that.
>>>>>>>>>
>>>>>>>>> Cheers,
>>>>>>>>>
>>>>>>>>> Ted
>>>>>>>>>
>>>>>>>>> On Mon, Mar 28, 2011 at 11:29 AM, Vladyslav Kolbasin
>>>>>>>>> <marcell at insart.com> wrote:
>>>>>>>>>>
>>>>>>>>>>
>>>>>>>>>> Good Day!
>>>>>>>>>>
>>>>>>>>>> I'm using RSymphony (package that uses Symphony for R).
>>>>>>>>>> I'm running rather large LP problems : about 1000-3000 variables and
>>>>>>>>>> 800-2000 constraints.
>>>>>>>>>>
>>>>>>>>>> For some my test-cases i get return code 226 (NO_SOLUTION). But i know
>>>>>>>>>> that there are simple solutions and may be rather complex too.
>>>>>>>>>>
>>>>>>>>>> I set param verbosity to 140 and get such return:
>>>>>>>>>>
>>>>>>>>>>
>>>>>>>>>>
>>>>>>>>>> Skipping Preprocessor
>>>>>>>>>> Problem has
>>>>>>>>>> 834 constraints
>>>>>>>>>> 1065 variables
>>>>>>>>>> 4366 nonzero coefficients
>>>>>>>>>>
>>>>>>>>>> Solving...
>>>>>>>>>>
>>>>>>>>>> granularity set at 0.000001
>>>>>>>>>>
>>>>>>>>>> TM: tree size: 0 , 0
>>>>>>>>>>
>>>>>>>>>> ****************************************************
>>>>>>>>>> * Now processing NODE 0 LEVEL 0 (from TM)
>>>>>>>>>> ****************************************************
>>>>>>>>>>
>>>>>>>>>> Diving set to 2
>>>>>>>>>>
>>>>>>>>>>
>>>>>>>>>>
>>>>>>>>>> **** Starting iteration 1 ****
>>>>>>>>>>
>>>>>>>>>> solving root lp relaxation
>>>>>>>>>> Terminating due to high cost -- fathoming node (no more cols to check)
>>>>>>>>>>
>>>>>>>>>>
>>>>>>>>>> ****************************************************
>>>>>>>>>> * Branch and Cut Finished *
>>>>>>>>>> * Now displaying stats and best solution found... *
>>>>>>>>>> ****************************************************
>>>>>>>>>> .....
>>>>>>>>>>
>>>>>>>>>>
>>>>>>>>>>
>>>>>>>>>>
>>>>>>>>>>
>>>>>>>>>> Also if i do some mixing constraints & variables then get solution - it is
>>>>>>>>>> most strange issue.
>>>>>>>>>>
>>>>>>>>>>
>>>>>>>>>>
>>>>>>>>>> Please Can you help me:
>>>>>>>>>> - explain why i can't get solution
>>>>>>>>>> - advise any params (or may be combination) that can help me to get any
>>>>>>>>>> solution (already tryed some from "LP parameters" and some others)
>>>>>>>>>>
>>>>>>>>>> Thanks a lot.
>>>>>>>>
>>>>>>>> _______________________________________________
>>>>>>>> Symphony mailing list
>>>>>>>> Symphony at list.coin-or.org
>>>>>>>> http://list.coin-or.org/mailman/listinfo/symphony
>>>>>>>>
>>>>>>
>>>>
>>>>
>>>
>>>
>>> _______________________________________________
>>> Symphony mailing list
>>> Symphony at list.coin-or.org
>>> http://list.coin-or.org/mailman/listinfo/symphony
>>>
>>
>>
>>
>> --
>> Dr. Ted Ralphs
>> Associate Professor, Lehigh University
>> (610) 628-1280
>> ted 'at' lehigh 'dot' edu
>> coral.ie.lehigh.edu/~ted
>>
More information about the Symphony
mailing list