[Symphony] Issue: get No solution in Symphony
Ted Ralphs
ted at lehigh.edu
Mon Apr 4 23:08:57 EDT 2011
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
>
--
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