[Scip] Column generation

Gulpinar, Nalan Nalan.Gulpinar at wbs.ac.uk
Tue Apr 1 09:20:45 CEST 2014


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<mailto:m.noorizadegan at gmail.com>>
Date: 31 March 2014 18:37
Subject: Column generation
To: Scip at zib.de<mailto: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


-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://listserv.zib.de/pipermail/scip/attachments/20140401/9317fd7d/attachment.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: log file.rtf
Type: application/rtf
Size: 18334 bytes
Desc: log file.rtf
URL: <http://listserv.zib.de/pipermail/scip/attachments/20140401/9317fd7d/attachment.rtf>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: log file 2.rtf
Type: application/rtf
Size: 10813 bytes
Desc: log file 2.rtf
URL: <http://listserv.zib.de/pipermail/scip/attachments/20140401/9317fd7d/attachment-0001.rtf>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: log file 3.rtf
Type: application/rtf
Size: 81059 bytes
Desc: log file 3.rtf
URL: <http://listserv.zib.de/pipermail/scip/attachments/20140401/9317fd7d/attachment-0002.rtf>


More information about the Scip mailing list