[Scip] Column generation

[Gerald Gamrath]

Hi Mahdi,

Nalan sent these log files already. You can print statistics by "disp
stat" in the interactive shell or calling SCIPprintStatistics().

Best,
Gerald


On 01.04.2014 13:42, mahdi noorizadegan wrote:
> 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
> <mailto: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 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
>>     <tel:%2B44%20%280%29%2024%207652%204491>
>>     Fax:    +44 (0) 24 7652 4539 <tel:%2B44%20%280%29%2024%207652%204539>
>>     Email:  Nalan.Gulpinar at wbs.ac.uk <mailto: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
>>
>>
>
>
>     _______________________________________________
>     Scip mailing list
>     Scip at zib.de <mailto: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/3dc1fe06/attachment.html>