[Scip] Column generation

mahdi noorizadegan m.noorizadegan at gmail.com
Tue Apr 1 13:42:59 CEST 2014


Hi Gerald,

The constraints are modifiable.
I am nit sure if you have the whole log files.
I have attached again the log files.
I was wondering if you could let me know what you mean by printing the
statistics after stopping?
What do you want to see in the log files?

Regards,
Mahdi


On 1 April 2014 10:04, Gerald Gamrath <gamrath at zib.de> wrote:

>  Dear Nalan,
>
> Mahdi's mail didn't reach the mailing list, because he also sent it from a
> mail address not registered for the list.
>
> It seems like your problem is not caused by the branching, on two of the
> three log file, you already stop before the first branching is performed.
>
> If you could print the statistics after stopping and send the log files
> again, this would help us a lot to identify the problem.
>
> Did you change all constraints to modifiable to which you add variables
> during solving? Otherwise, propagation might fix some of your priced
> variables to 0 and it might happen that pricing regenerates them again and
> again. Except for that, my best guess would be that you somehow compute the
> reduced cost wrongly.
>
> Best,
> Gerald
>
>
>
> On 01.04.2014 09:20, Gulpinar, Nalan wrote:
>
>  Dear Ambros,
>
>
>  Thank you for your prompt reply. As you suggested, I am resending my
> previous email.
>
>
>  I am writing this email about the problem we have faced with SCIP.
>
> As Mahdi reported yesterday (please see his email below), we have checked
> the
>
> code several times, and even tried to run its alternative formulation but
> the problem
>
> remains the same. I have also attached the output of three instances of
> the model.
>
> I hope this helps you to identify the problem.
>
>
> We use column generation procedure where continuous variables are added
> into the
>
> master problem and branch and bound procedure is used to solve the master
> problem.
>
> But after some iterations it cannot be improved. For example, as you will
> see from
>
> log file.rtf, we have the following output.
>
>
>  I am looking forward to receiving your reply and suggestions.
>
>
>  Thank you for your help at advance.
>
>
>  Best regards
>
>
>  Nalan
>
>
>  _____________________________________________
>  Nalan Gulpinar, Ph.D.
> Associate Professor of Operational Research
> Warwick Business School
> The University of Warwick, Coventry, CV4 7AL, UK.
> Tel:     +44 (0) 24 7652 4491
> Fax:    +44 (0) 24 7652 4539
> Email:  Nalan.Gulpinar at wbs.ac.uk
> _____________________________________________
>
>
>  leastJ/leastT= 0,0, minRedCost: -43.3117
>
> total cost= 1173.06, 10.84, 882.22, 280, z_134
>
> 134, add new variables
>
>   0.1s|     1 |     0 |   203 |     - | 725k|   0 |  33 | 206 | 115 | 205
> | 115 |   0 |   0 |   0 |      --      | 7.654555e+03 |    Inf
>
>  time | node  | left  |LP iter|LP it/n| mem |mdpt |frac |vars |cons |cols
> |rows |cuts |confs|strbr|  dualbound   | primalbound  |  gap
>
>   0.1s|     1 |     0 |   205 |     - | 725k|   0 |  36 | 206 | 115 | 206
> | 115 |   0 |   0 |   0 |      --      | 7.654555e+03 |    Inf
>
>
>
>  leastJ/leastT= 2,0, minRedCost: -90.6829
>
> total cost= 532.45, 1.05, 363.4, 168, z_135
>
> 135, add new variables
>
>   0.1s|     1 |     0 |   205 |     - | 727k|   0 |  36 | 207 | 115 | 206
> | 115 |   0 |   0 |   0 |      --      | 7.654555e+03 |    Inf
>
>   0.1s|     1 |     0 |   205 |     - | 727k|   0 |  23 | 207 | 115 | 207
> | 115 |   0 |   0 |   0 |      --      | 7.654555e+03 |    Inf
>
>
>
>  leastJ/leastT= 2,0, minRedCost: -90.6829
>
> total cost= 532.45, 1.05, 363.4, 168, z_136
>
> 136, add new variables
>
>   0.1s|     1 |     0 |   205 |     - | 729k|   0 |  23 | 208 | 115 | 207
> | 115 |   0 |   0 |   0 |      --      | 7.654555e+03 |    Inf
>
>   0.1s|     1 |     0 |   209 |     - | 729k|   0 |  23 | 208 | 115 | 208
> | 115 |   0 |   0 |   0 |      --      | 7.654555e+03 |    Inf
>
>
>
>  leastJ/leastT= 1,0, minRedCost: -88.4043
>
> total cost= 350.84, 31.14, 151.7, 168, z_137
>
> 137, add new variables
>
>   0.1s|     1 |     0 |   209 |     - | 731k|   0 |  23 | 209 | 115 | 208
> | 115 |   0 |   0 |   0 |      --      | 7.654555e+03 |    Inf
>
>
>
>  leastJ/leastT= 1,0, minRedCost: -88.4043
>
> total cost= 350.84, 31.14, 151.7, 168, z_138
>
> 138, add new variables
>
>   0.1s|     1 |     0 |   209 |     - | 733k|   0 |  23 | 210 | 115 | 208
> | 115 |   0 |   0 |   0 |      --      | 7.654555e+03 |    Inf
>
>
>
>  leastJ/leastT= 1,0, minRedCost: -88.4043
>
> total cost= 350.84, 31.14, 151.7, 168, z_139
>
> 139, add new variables
>
> This goes on......
>
>
> ---------- Forwarded message ----------
> From: mahdi noorizadegan <m.noorizadegan at gmail.com>
> Date: 31 March 2014 18:37
> Subject: Column generation
> To: Scip at zib.de
>
>  Hi,
>
>  I have been trying to solve a problem by the column generation method.
>  The variables which are being added to the master problem were binary
>  so I had the problem with the branch and bound procedure.
>  I changed the formulation and added new dummy binary variables and
> changed
>  the type of the other variables to continuous.
>  So there should not be any problem with the branch and bound producer.
>  However, I still have problems. It keeps adding the same column after
> few iterations!
>  For example for a simple instance, the objective function value is
> 350.84,
>  the dual value is 439.24 therefore the reduced cost is
> -439.24+350.84=-88.40.
>  When this new variable is added to the problem, in the next iteration
> this variable is again
>  identified and added!
>
>  I have checked the pricing problem. It seems correct and I could not
> find any mistake.
>  I was wondering if you could help me and let me know what can be wrong!?
>
>  Thanks and best,
> Mahdi
>
>
>
>
> _______________________________________________
> Scip mailing list
> Scip at zib.de
> http://listserv.zib.de/mailman/listinfo/scip
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://listserv.zib.de/pipermail/scip/attachments/20140401/a24e3d83/attachment.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: log file.rtf
Type: application/rtf
Size: 18334 bytes
Desc: not available
URL: <http://listserv.zib.de/pipermail/scip/attachments/20140401/a24e3d83/attachment.rtf>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: log file 2.rtf
Type: application/rtf
Size: 10813 bytes
Desc: not available
URL: <http://listserv.zib.de/pipermail/scip/attachments/20140401/a24e3d83/attachment-0001.rtf>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: log file 3.rtf
Type: application/rtf
Size: 81059 bytes
Desc: not available
URL: <http://listserv.zib.de/pipermail/scip/attachments/20140401/a24e3d83/attachment-0002.rtf>


More information about the Scip mailing list