[SCIP] Column Generation with a convex objective

[Guillaume BS]

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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://listserv.zib.de/pipermail/scip/attachments/20240213/82b8ff12/attachment.html>