[Symphony] Issue: get No solution in Symphony

Vladyslav Kolbasin marcell at insart.com
Tue Mar 29 13:16:38 EDT 2011 

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

More information about the Symphony mailing list