[Scip] Column generation
mahdi noorizadegan
m.noorizadegan at gmail.com
Tue Apr 1 16:47:58 CEST 2014
Hi 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> 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> 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/666168a8/attachment.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: addVar.rtf
Type: application/rtf
Size: 4390 bytes
Desc: not available
URL: <http://listserv.zib.de/pipermail/scip/attachments/20140401/666168a8/attachment.rtf>
More information about the Scip
mailing list