[SCIP] SCIP pricer is generating the same column

[Theo Francois]

 Dear Marc,
Thanks for your answer.
The problem seems not to be from reduced costs for two reasons: first, I computed manually a column generation algorithm where these reduced costs were used without issue, second I manually implemented the first column in the initial set and the reduced cost was better, meaning this column is effectively improving the master problem.
The variable bounds are correct and the initial LP also looks correct. I also printed some constraints at the end of the pricer call and it looks like the variables are correctly added to the master problem but I lack a tool to output the LP during the process of column generation (for example at the end of the pricer call), is there a way to do this ? The only function I found was Model.writeProblem() but the output shows only the initial master problem (I tested the function with the binary stock example and the final LP appears only when the whole process of column generation is finished).
Best,
Théo
    Le mercredi 24 août 2022 à 14:43:38 UTC+2, Marc Pfetsch <pfetsch at mathematik.tu-darmstadt.de> a écrit :  
 
 
Hi Théo,

without knowing the details of your implementation, the most likely 
reason is that your reduced costs are not correctly computed. This might 
be a bug in your code. One further reason might be variable bounds (and 
the corresponding dual variables) that you have forgotten in the 
computation.

I would recommend to output the current LP and check whether there are 
constraints that you did not expect. Moreover, you should then recompute 
the reduced costs after you generated the new column and check whether 
it is actually improving.

Best

Marc


On 19/08/2022 11.42, Theo Francois wrote:
> Dear SCIP Team,
> 
> I am using the python interface of SCIP pyscipopt to implement a column 
> generation algorithm for the Resource Constrained Modulo Scheduling 
> problem, and I have some issues regarding the process.
> 
> Since the first iteration for my instances, the columns generated are 
> all the same. It may come from the reduced costs but those were already 
> implemented in a column generation algorithm I coded myself and it just 
> works fine. It looks like when I printed the details of constraints that 
> the new columns are added correctly by the pricer to the master problem 
> but for some reasons the dual variables remain unchanged from one 
> iteration to the other, which lead to the generation of the same column.
> 
> I implemented my model following the cutting stock example 
> test_pricer.py and I wasn't able to determine what was causing the dual 
> problem to find the very same dual solutions despite the introduction of 
> a truly improving column.
> 
> Is there any possibility to help me ?
> 
> If you want further informations on the model itself, I presented it 
> briefly in a joint pdf. You will also find an instance and the code 
> associated if there is a necessity to perform tests (I implemented at 
> the end of the pricer an interruption condition to avoid the infinite 
> loop caused by the generation of the same column).
> 
> Best regards,
> 
> Théo FRANCOIS,
> Research intern at LAAS-CNRS
> 
> _______________________________________________
> Scip mailing list
> Scip at zib.de
> https://listserv.zib.de/mailman/listinfo/scip
_______________________________________________
Scip mailing list
Scip at zib.de
https://listserv.zib.de/mailman/listinfo/scip
  
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://listserv.zib.de/pipermail/scip/attachments/20220824/1635d087/attachment.html>