[Scip] Column generation
Gerald Gamrath
gamrath at zib.de
Tue Apr 1 15:35:36 CEST 2014
Hi Mahdi,
is the delay flag of your pricer set to TRUE? When you create and add
new variables, do you set the initial flag of the variables to TRUE? You
add them with SCIPaddPricedVar()? Can you double-check, that the
variables you create really have the same meaning. If so, please check
the following for the "old" variable:
- is it in the LP? -> SCIPvarIsInLP()
- what are the reduced cost of the variable -> SCIPgetVarRedcost()
- does this corresond to the reduced cost you are computing for the new
variable?
Best,
Gerald
On 01.04.2014 14:51, mahdi noorizadegan wrote:
> Hi Gerald,
>
> Please find the attachments.
>
> Thanks,
> Mahdi
>
>
> On 1 April 2014 13:30, Gerald Gamrath <gamrath at zib.de
> <mailto: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
>> <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/ff178494/attachment.html>
More information about the Scip
mailing list