[Scip] Column generation
Gerald Gamrath
gamrath at zib.de
Wed Apr 2 00:10:41 CEST 2014
Dear Mahdi,
if you do not know how to use a method or don't know its parameters,
check the documentation: http://scip.zib.de/doc/html/
You can also search methods by name there.
What I wanted you to do is check the *old* variable for whether it is in
the LP and has negative reduced costs. Also you could check its value in
the LP.
But I have two other things:
1) Do you add the variables to the original or the transformed
constraints? -> SCIPconsIsTransformed()
2) You have upper bounds on your variables. This can be a problem for
column generation, because a variable can have negative reduced cost if
it is nonbasic on its upper bound. Please change it to infinity or set
the upper bound to be lazy (if it is enforced by some constraint). See
the FAQ about how to do this.
Best,
Gerald
> >>is the delay flag of your pricer set to TRUE?
> Yes,
>
>
> >>When you create and add new variables, do you set the initial flag
> of the variables to TRUE?
> Which parameter corresponds to the initial flag?
>
> >>You add them with SCIPaddPricedVar()?
> Yes,
> >>Can you double-check, that the variables you create really have the
> same meaning.
> Yes,
>
> >> If so, please check the following for the "old" variable:
> >>- is it in the LP? -> SCIPvarIsInLP()
> I did not use SCIPvarIsInLP() ( I do not know how to use it) but in
> each iteration I checked, s
>
> >>- what are the reduced cost of the variable -> SCIPgetVarRedcost()
> >>- does this corresond to the reduced cost you are computing for the
> new variable?
> When I add SCIPgetVarRedCost(), after one iteration it returns error:
> ERROR: Error <1516178640> in function call
> But in this iteraion, the reduced cost are exactly the same as what I
> calculate.
> How can I find out what is wrong here?
> Note that without SCIPgetVarRedCost(), I do not get any error.
> I have attached the procedure in which I add new variables.
>
> Regards,
> Mahdi
>
>
> On 1 April 2014 14:35, Gerald Gamrath <gamrath at zib.de
> <mailto:gamrath at zib.de>> wrote:
>
> 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/20140402/f75b11d9/attachment.html>
More information about the Scip
mailing list