[Scip] Column generation
mahdi noorizadegan
m.noorizadegan at gmail.com
Tue Apr 1 14:51:13 CEST 2014
Hi Gerald,
Please find the attachments.
Thanks,
Mahdi
On 1 April 2014 13:30, Gerald Gamrath <gamrath at zib.de> wrote:
> 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> 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 <%2B44%20%280%29%2024%207652%204491>
>> Fax: +44 (0) 24 7652 4539 <%2B44%20%280%29%2024%207652%204539>
>> 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/97dec737/attachment.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: stat 2.rtf
Type: application/rtf
Size: 23836 bytes
Desc: not available
URL: <http://listserv.zib.de/pipermail/scip/attachments/20140401/97dec737/attachment.rtf>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: stat1.rtf
Type: application/rtf
Size: 32255 bytes
Desc: not available
URL: <http://listserv.zib.de/pipermail/scip/attachments/20140401/97dec737/attachment-0001.rtf>
More information about the Scip
mailing list