[SCIP] set/vbc/dispsols
Gotzes, Uwe Dr.
Uwe.Gotzes at open-grid-europe.com
Wed Dec 21 12:38:24 CET 2016
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.0000
>>>> 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
-------------- next part --------------
A non-text attachment was scrubbed...
Name: testscip.zpl
Type: application/octet-stream
Size: 239 bytes
Desc: testscip.zpl
URL: <http://listserv.zib.de/pipermail/scip/attachments/20161221/d4a04463/attachment.obj>
-------------- 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/20161221/d4a04463/attachment-0001.obj>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: bbtree.pdf
Type: application/pdf
Size: 380995 bytes
Desc: bbtree.pdf
URL: <http://listserv.zib.de/pipermail/scip/attachments/20161221/d4a04463/attachment.pdf>
More information about the Scip
mailing list