[Symphony] Issue: get No solution in Symphony
Ted Ralphs
ted at lehigh.edu
Tue Apr 5 23:14:29 EDT 2011
Just to be clear, I was not saying that using CPLEX would resolve your
issues. The output of CPLEX is also reinforcing what I was telling
you---that your model is unstable. I will say, however, that there are
some tricks to handling these instabilities and CPLEX, as a commercial
product, will tend to handle them much better than SYMPHONY. Problem
conditioning is a function of the input matrix. A problem for which
many poorly conditioned basis matrices arise will be difficult for any
solver. The problem is not with the algorithm, it is with the fact
that the solution to the model itself is very sensitive to the
inevitable round-off errors that occur with floating point
computation. Intuitively, you can think of the condition number as
telling you how much any round-off errors that arise could get
magnified as a result of the computations that occur within the
algorithm. Hence, a condition number of 10^18 means that tiny
inaccuracies in intermediate calculations may be magnified massively
in the final output.
A rule of thumb to avoid instability is to try to keep the difference
between the largest and smallest numbers appearing in your coefficient
matrix as small as possible, i.e., keeping all the numbers around the
same "scale". This can be done automatically to a certain extent by
scaling the rows and columns. In general, scaling the matrix so that
all entries are between 0 and 1 helps. Most solvers do this for you.
However, by using units that tend to make the problem inputs have
similar scales to being with, you can improve stability. In other
words, do not put one input measurement in milimeters and another one
in kilometers.
Hope this helps.
Cheers,
Ted
On Tue, Apr 5, 2011 at 2:23 AM, Vladyslav Kolbasin <marcell at insart.com> wrote:
>
> 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
>>>
>
>
--
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