[Symphony] Issue: get No solution in Symphony

Tue Mar 29 16:33:17 EDT 2011

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
>>>>>
>>>
>
>