[SCIP] set/vbc/dispsols
Gotzes, Uwe Dr.
Uwe.Gotzes at open-grid-europe.com
Thu Jan 5 12:13:33 CET 2017
Hi Jakob,
I still don't get the point why objective value 8 with 0 fractional variables does not yield an upper bound. Maybe we can have a coffee together and discuss the topic when I am at ZIB next time. I used scip 3.2.0, but I can reproduce the results with the latest scip release after slightly modifying the formerly provided settings file (some timing parameters had to be adjusted from 2 to 4 to make the settings feasible for the new release). Please make sure that you use the right settings file (see attachment) if you want to reproduce the behavior. I tried to configure scip such that it applies only simple LP based branch and bound to the problem.
Best,
Uwe
-----Ursprüngliche Nachricht-----
Von: Jakob Witzig [mailto:witzig at zib.de]
Gesendet: Mittwoch, 4. Januar 2017 10:10
An: Gotzes, Uwe Dr.
Cc: scip at zib.de
Betreff: Re: [SCIP] set/vbc/dispsols
Hi Uwe,
as you can see in the pdf produced by your script the order in which the nodes are processed is 1-3-2 and node #3 is infeasible.
By the way: Which SCIP version do you use? With the latest release (3.2.1, githash: c7c6c02) and SoPlex (2.2.1, githash: 267a44a) I cannot reproduce 3 or more branch-and-bound nodes, the problem is solved within the root node.
Cheers
Jakob
Am 21.12.2016 um 12:38 schrieb Gotzes, Uwe Dr.:
> Hi Jakob,
>
> I'm still not perfectly satisfied with your answer. The node is neither infeasible nor inferior so I conclude from your answer it has no constructed LP. But what does that mean and where does the bound come from in that case?
>
> Attached you find the problem and also the settings I used. I wrote a little tool to visualize the branch and bound tree using the vbc-file that scip generates. You find its output also in the attachment. When the tool is ripe enough, I will put it on my website and send a link to the mailing list.
>
> Best,
> Uwe
>
> -----Ursprüngliche Nachricht-----
> Von: Jakob Witzig [mailto:witzig at zib.de]
> Gesendet: Montag, 19. Dezember 2016 09:33
> An: Gotzes, Uwe Dr.
> Cc: scip at zib.de
> Betreff: Re: [SCIP] set/vbc/dispsols
>
> Sorry, my explanation was not complete. A "-" is also printed when the current node has no constructed LP or the LP was not solved to optimality, e.g., infeasible or its objective exceeds the current cutoff bound.
>
> Cheers,
> Jakob
>
> Am 16.12.2016 um 15:07 schrieb Gotzes, Uwe Dr.:
>> Ok, I see, thanks!
>>
>> Could you also say something about
>>> Regarding your answer to my "frac"-question: If there are 0 fractional variables in the LP-solution of node 2, why isn't there a primal bound resulting from it?
>>> time | node | left |LP iter|LP it/n| mem |mdpt |frac |vars |cons |cols |rows |cuts |confs|strbr| dualbound | primalbound | gap
>>> 0.0s| 2 | 1 | 3 | 0.0 | 169k| 1 | - | 2 | 3 | 2 | 2 | 3 | 0 | 0 |8.000000e+000 | -- | Inf
>>
>>
>> -----Ursprüngliche Nachricht-----
>> Von: Jakob Witzig [mailto:witzig at zib.de]
>> Gesendet: Freitag, 16. Dezember 2016 14:58
>> An: Gotzes, Uwe Dr.
>> Cc: scip at zib.de
>> Betreff: Re: [SCIP] set/vbc/dispsols
>>
>> Hi Uwe!
>>
>> No, because the SCIP output only says that the solution with objective value 4 was found at the 5th node that was evaluated, this need not to be the node number with 5.
>>
>> Cheers,
>> Jakob
>>
>> Am 16.12.2016 um 13:28 schrieb Gotzes, Uwe Dr.:
>>> Hi Jakob,
>>>
>>> my problem is that the solution with objective value -4 corresponds to node 5 and the solution with objective value -7 corresponds to node 6. In the vbc-file it is somehow the other way round: "U -4" is printed "close" to the new (P)ainting of node 6 while "U -7" occurs close to the new painting of node 5 in the file.
>>>
>>>>> 00:00:00.00 P 6 14
>>>>> 00:00:00.00 U -4.000000
>>> ...
>>>>> 00:00:00.00 P 5 14
>>> ...
>>>>> 00:00:00.00 U -7.000000
>>>
>>> Isn't that strange?
>>>
>>> Regarding your answer to my "frac"-question: If there are 0 fractional variables in the LP-solution of node 2, why isn't there a primal bound resulting from it?
>>> time | node | left |LP iter|LP it/n| mem |mdpt |frac |vars |cons |cols |rows |cuts |confs|strbr| dualbound | primalbound | gap
>>> 0.0s| 2 | 1 | 3 | 0.0 | 169k| 1 | - | 2 | 3 | 2 | 2 | 3 | 0 | 0 |8.000000e+000 | -- | Inf
>>>
>>> Best,
>>> Uwe
>>>
>>>
>>> -----Ursprüngliche Nachricht-----
>>> Von: Jakob Witzig [mailto:witzig at zib.de]
>>> Gesendet: Freitag, 16. Dezember 2016 13:01
>>> An: Gotzes, Uwe Dr.
>>> Cc: scip at zib.de
>>> Betreff: Re: [SCIP] set/vbc/dispsols
>>>
>>> One additional remark or workaround. You can look at the lines of type:
>>>
>>> 00:00:00.00 U -7.000000
>>>
>>> This is new upper bound, i.e., the objective values of the new incumbent. In your case you need to multiply with -1 because your problem seems to be a maximization problem and SCIP's transformed problem is always a minimization problem.
>>>
>>> Cheers
>>> Jakob
>>>
>>> Am 16.12.2016 um 12:56 schrieb Jakob Witzig:
>>>> Hi Uwe,
>>>>
>>>> I had a look into the code and it seems that the vbc-format does
>>>> not support information about the new incumbent solution. If you
>>>> use bak instead of vbc, SCIP will print a line like:
>>>>
>>>> integer {nodenumber} {parentnumber} {boundtype} {newobj}
>>>>
>>>> The "frac" column shows the number of fractional variables in the
>>>> LP solution. If all integer variables have an integral solution
>>>> value in the LP solution a "-" is printed.
>>>>
>>>> Cheers,
>>>> Jakob
>>>>
>>>> Am 16.12.2016 um 12:02 schrieb Gotzes, Uwe Dr.:
>>>>> Hi,
>>>>>
>>>>> I have a very simple problem and tried to tell scip to apply plain
>>>>> lp-based branch and bound to it.
>>>>>
>>>>> I have set vbc/dispsols = TRUE to visualize the nodes where
>>>>> solutions are found.
>>>>>
>>>>> This option results in the two lines 00:00:00.00 P 6 14 and
>>>>> 00:00:00.00 P 5 14 in the vbc-file. (P int int Number of the node,
>>>>> number of the nodes colour.)
>>>>>
>>>>> I have two questions:
>>>>> 1. Is it possible to figure out the value of the solution found in
>>>>> the respective node from the vbc-file?
>>>>> 2. What is the meaning of the minus sign in the "frac"-column of node 2?
>>>>>
>>>>>
>>>>> Scip output is:
>>>>>
>>>>> time | node | left |LP iter|LP it/n| mem |mdpt |frac |vars
>>>>> |cons
>>>>> |cols |rows |cuts |confs|strbr| dualbound | primalbound | gap
>>>>> 0.0s| 1 | 0 | 0 | - | 166k| 0 | - | 2 | 3
>>>>> | 2 | 0 | 0 | 0 | 0 | -- | -- | Inf
>>>>> (node 1) LP relaxation is unbounded (LP 0)
>>>>> 0.0s| 1 | 0 | 2 | - | 167k| 0 | - | 2 | 3
>>>>> | 2 | 2 | 2 | 0 | 0 | -- | -- | Inf
>>>>> (node 1) LP relaxation is unbounded (LP 1)
>>>>> 0.0s| 1 | 0 | 3 | - | 168k| 0 | 1 | 2 | 3
>>>>> | 2 | 2 | 3 | 0 | 0 |8.428571e+000 | -- | Inf
>>>>> 0.0s| 1 | 2 | 3 | - | 168k| 0 | 1 | 2 | 3
>>>>> | 2 | 2 | 3 | 0 | 0 |8.428571e+000 | -- | Inf
>>>>> 0.0s| 2 | 1 | 3 | 0.0 | 169k| 1 | - | 2 | 3
>>>>> | 2 | 2 | 3 | 0 | 0 |8.000000e+000 | -- | Inf
>>>>> 0.0s| 3 | 2 | 5 | 1.0 | 169k| 1 | 1 | 2 | 3
>>>>> | 2 | 2 | 3 | 0 | 0 |7.500000e+000 | -- | Inf
>>>>> 0.0s| 4 | 3 | 6 | 1.0 | 170k| 2 | 1 | 2 | 3
>>>>> | 2 | 2 | 3 | 0 | 0 |7.000000e+000 | -- | Inf
>>>>> * 0.0s| 5 | 2 | 7 | 1.0 | 170k| 3 | - | 2 | 3
>>>>> | 2 | 2 | 3 | 0 | 0 |7.000000e+000 |4.000000e+000 | 75.00%
>>>>> * 0.0s| 6 | 0 | 8 | 1.0 | 170k| 3 | - | 2 | 3
>>>>> | 2 | 2 | 3 | 0 | 0 |7.000000e+000 |7.000000e+000 | 0.00%
>>>>>
>>>>> The content of the generated vbc-file:
>>>>>
>>>>> #TYPE: COMPLETE TREE
>>>>> #TIME: SET
>>>>> #BOUNDS: SET
>>>>> #INFORMATION: STANDARD
>>>>> #NODE_NUMBER: NONE
>>>>> 00:00:00.00 N 0 1 3
>>>>> 00:00:00.00 I 1
>>>>> \inode:\t1\idepth:\t0\nvar:\t-\nbound:\t-100000000000000000000.000
>>>>> 0
>>>>> 0
>>>>> 0
>>>>> 00:00:00.00 P 1 11
>>>>> 00:00:00.00 N 1 2 3
>>>>> 00:00:00.00 I 2 \inode:\t2\idepth:\t1\nvar:\t-\nbound:\t-8.428571
>>>>> 00:00:00.00 I 2 \inode:\t2\idepth:\t1\nvar:\tt_x1 [-0,1e+020] <=
>>>>> 2.000000\nbound:\t-8.000000
>>>>> 00:00:00.00 N 1 3 3
>>>>> 00:00:00.00 I 3 \inode:\t3\idepth:\t1\nvar:\t-\nbound:\t-8.428571
>>>>> 00:00:00.00 I 3 \inode:\t3\idepth:\t1\nvar:\tt_x1 [-0,1e+020] >=
>>>>> 3.000000\nbound:\t-8.428571
>>>>> 00:00:00.00 I 1
>>>>> \inode:\t1\idepth:\t0\nvar:\t-\nbound:\t-8.428571\nnr:\t1
>>>>> 00:00:00.00 P 1 2
>>>>> 00:00:00.00 I 3 \inode:\t3\idepth:\t1\nvar:\tt_x1 [3,1e+020] >=
>>>>> 3.000000\nbound:\t100000000000000000000.000000\nnr:\t2
>>>>> 00:00:00.00 P 3 2
>>>>> 00:00:00.00 I 3 \inode:\t3\idepth:\t1\nvar:\tt_x1 [3,1e+020] >=
>>>>> 3.000000\nbound:\t100000000000000000000.000000\nnr:\t2
>>>>> 00:00:00.00 P 3 4
>>>>> 00:00:00.00 N 2 4 3
>>>>> 00:00:00.00 I 4 \inode:\t4\idepth:\t2\nvar:\t-\nbound:\t-7.500000
>>>>> 00:00:00.00 I 4 \inode:\t4\idepth:\t2\nvar:\tt_x2 [-0,3] <=
>>>>> 0.000000\nbound:\t-7.500000
>>>>> 00:00:00.00 N 2 5 3
>>>>> 00:00:00.00 I 5 \inode:\t5\idepth:\t2\nvar:\t-\nbound:\t-7.500000
>>>>> 00:00:00.00 I 5 \inode:\t5\idepth:\t2\nvar:\tt_x2 [-0,3] >=
>>>>> 1.000000\nbound:\t-7.000000
>>>>> 00:00:00.00 I 2 \inode:\t2\idepth:\t1\nvar:\tt_x1 [-0,2] <=
>>>>> 2.000000\nbound:\t-7.500000\nnr:\t3
>>>>> 00:00:00.00 P 2 2
>>>>> 00:00:00.00 N 4 6 3
>>>>> 00:00:00.00 I 6 \inode:\t6\idepth:\t3\nvar:\t-\nbound:\t-6.000000
>>>>> 00:00:00.00 I 6 \inode:\t6\idepth:\t3\nvar:\tt_x1 [-0,2] <=
>>>>> 1.000000\nbound:\t-4.000000
>>>>> 00:00:00.00 N 4 7 3
>>>>> 00:00:00.00 I 7 \inode:\t7\idepth:\t3\nvar:\t-\nbound:\t-6.000000
>>>>> 00:00:00.00 I 7 \inode:\t7\idepth:\t3\nvar:\tt_x1 [-0,2] >=
>>>>> 2.000000\nbound:\t-6.000000
>>>>> 00:00:00.00 I 4 \inode:\t4\idepth:\t2\nvar:\tt_x2 [-0,0] <=
>>>>> 0.000000\nbound:\t-6.000000\nnr:\t4
>>>>> 00:00:00.00 P 4 2
>>>>> 00:00:00.00 I 6 \inode:\t6\idepth:\t3\nvar:\tt_x1 [-0,1] <=
>>>>> 1.000000\nbound:\t-4.000000\nnr:\t5
>>>>> 00:00:00.00 P 6 2
>>>>> 00:00:00.00 P 6 14
>>>>> 00:00:00.00 U -4.000000
>>>>> 00:00:00.00 I 5 \inode:\t5\idepth:\t2\nvar:\tt_x2 [1,3] >=
>>>>> 1.000000\nbound:\t-7.000000\nnr:\t6
>>>>> 00:00:00.00 P 5 2
>>>>> 00:00:00.00 P 5 14
>>>>> 00:00:00.00 I 7 \inode:\t7\idepth:\t3\nvar:\tt_x1 [-0,2] >=
>>>>> 2.000000\nbound:\t-6.000000\nnr:\t6
>>>>> 00:00:00.00 P 7 4
>>>>> 00:00:00.00 U -7.000000
>>>>>
>>>>> Thanks,
>>>>> Uwe
>>>>>
>>>>> _______________________________________________
>>>>> Scip mailing list
>>>>> Scip at zib.de
>>>>> http://listserv.zib.de/mailman/listinfo/scip
>>>>>
>>>>
>>>>
>>>
>>>
>>> --
>>> Jakob Witzig
>>>
>>> Zuse Institute Berlin (ZIB)
>>>
>>> Division Mathematical Optimization and Scientific Information
>>> Research Group Mathematical Optimization Methods
>>>
>>> Takustrasse 7
>>> 14195 Berlin
>>>
>>> Tel. : +49 (0)30 84185-416
>>> Fax : +49 (0)30 84185-269
>>> email: witzig at zib.de
>>>
>>
>>
>> --
>> Jakob Witzig
>>
>> Zuse Institute Berlin (ZIB)
>>
>> Division Mathematical Optimization and Scientific Information
>> Research Group Mathematical Optimization Methods
>>
>> Takustrasse 7
>> 14195 Berlin
>>
>> Tel. : +49 (0)30 84185-416
>> Fax : +49 (0)30 84185-269
>> email: witzig at zib.de
>>
>
>
> --
> Jakob Witzig
>
> Zuse Institute Berlin (ZIB)
>
> Division Mathematical Optimization and Scientific Information Research
> Group Mathematical Optimization Methods
>
> Takustrasse 7
> 14195 Berlin
>
> Tel. : +49 (0)30 84185-416
> Fax : +49 (0)30 84185-269
> email: witzig at zib.de
>
--
Jakob Witzig
Zuse Institute Berlin (ZIB)
Division Mathematical Optimization and Scientific Information Research Group Mathematical Optimization Methods
Takustrasse 7
14195 Berlin
Tel. : +49 (0)30 84185-416
Fax : +49 (0)30 84185-269
email: witzig at zib.de
-------------- next part --------------
A non-text attachment was scrubbed...
Name: scip.set
Type: application/octet-stream
Size: 315380 bytes
Desc: scip.set
URL: <http://listserv.zib.de/pipermail/scip/attachments/20170105/c586ba14/attachment.obj>
More information about the Scip
mailing list