[SCIP] Column Generation with a convex objective

[Marc Pfetsch]

Hi Guillaume,

I am not aware of an implementation of column generation for convex NLPs 
- probably because of the problems that you describe.

Let me comment a bit:

- SCIP only solves LP relaxations and no NLPs. Thus, you will not be 
able to directly access dual values.

   It might be able to track the dual variables of the LP rows to the 
original constraints and check which one is active. But even then, this 
is only an approximation of the dual and probably not useful for column 
generation if you want to obtain a valid bound.

- I do not know why the dual variables of the linear constraints are not 
correct (or with expected values). I think that they should be 
accessible, but they might not be sensible, because the RMP is only 
approximated in intermediate steps.

- The convergence of the solution of the RMP is indeed another problem. 
Unfortunately, I am not aware of an easy method to determine whether 
SCIP thinks that it has solved the RMP to acceptable accuracy (it might 
have stopped early because of certain limits like stalling).

- In your example I would assume that f only contains variables that are 
not priced. Otherwise you need to be careful about correctness of the 
algorithm.


Note that, in principle, it would be possible to solve NLP as a 
relaxation, see the "Relaxator" example in SCIP. But one would need to 
extend the code in order to access the relevant data for column 
generation and probably also adapt SCIP to this case.

Best

Marc


On 13/02/2024 08:58, Guillaume BS wrote:
> Hi everyone,
> 
> I am currently trying to run a column-generation algorithm on a problem 
> with a convex objective function and linear constraints.
> 
>   * I implemented the Restricted Master Program (RMP) in SCIP, using a
>     constraint to reproduce the convex objective function ; so my
>     problem is :
> 
>       o Min z
>       o f(x) < z
>       o A x < b
>       Variables z and x=(x_1…x_n) are real-valued ; the column 
> generation algorithm creates new x_k variables.
> 
>   *
>     I used SCIP 8.1.0 with IPopt as nonlinear solver, and wrote the
>     problem and pricer in C/C++ ; I set the
>     “constraints/nonlinear/assumeconvex” to True and remove pre-processings,
>   *
>     The pricer callback functions is based on the dual variables of the
>     linear constraints adds new columns in the RMP (the pricing problem
>     is derived from the KKT conditions on my master problem) ; I also
>     use at the current solution via the SCIPgetBestSol(...) function in
>     the pricer.
> 
> 
> When I run the program I face several issues:
> 
>   *
>     When I try the SCIPisDualSolAvailable(...) function I get a warning
>     message telling clearly that the dual variables are not available:
>     “WARNING: Dual information only available for pure LPs (only linear
>     constraints)”
>   *
>     Yet I can access the dual variables of my linear constraints, but
>     their value are clearly not what I would expect (similar to what is
>     described here:
>     https://listserv.zib.de/pipermail/scip/2023-August/004736.html )
>   *
>     Even ignoring the dual variables and focusing on the primal
>     solution, I see pricer is called well before the RMP converged, and
>     the primal solution is far from optimal. So when I run my program
>     the pricer is called way too often, leading to very poor performances.
> 
> 
> 
> So I am wondering if it is possible to run a column-generation algorithm 
> on a NLP in SCIP?
> 
> If it isn’t possible to access reliably the duals of the linear 
> constraints, is it possible to ensure the pricing problem is only called 
> when the RMP has converged to a (reasonably) optimal solution ?
> 
> Many thanks,
> Guillaume
> 
> _______________________________________________
> Scip mailing list
> Scip at zib.de
> https://listserv.zib.de/mailman/listinfo/scip