[Scip] Column generation

Gerald Gamrath gamrath at zib.de
Tue Apr 1 11:04:06 CEST 2014


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 triedto 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/5d191df5/attachment.html>


More information about the Scip mailing list