[Scip] Column generation
Gulpinar, Nalan
Nalan.Gulpinar at wbs.ac.uk
Wed Apr 2 00:55:55 CEST 2014
Let's hope that this will solve the problem...
________________________________
From: Gerald Gamrath <gamrath at zib.de>
Sent: 01 April 2014 23:10
To: mahdi noorizadegan
Cc: Gulpinar, Nalan; Scip at zib.de
Subject: Re: [Scip] Column generation
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 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<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/8eee46fe/attachment.html>
More information about the Scip
mailing list