[SCIP] Column Generation with a convex objective

[Ambros Gleixner]

Hi Guillaume,

Let me add just some more details that I caught from your initial questions:

- SCIPgetBestSol() will give you the incumbent, i.e., the best known 
primal feasible solution globally, not the primal LP relaxation solution 
at the current node.

- SCIPisDualSolAvailable() is not relevant from within a plugin; it is 
meant when you use SCIP as a black-box solver, solving an LP, and want 
to get the dual solution.

- You mentioned that preprocessing is turned off; I assume you also 
marked your constraints as modifiable?

But indeed, as Marc mentioned, the main issue is that you expected a 
nonlinear RMP relaxation, while SCIP's pricing loop is designed for the 
LP relaxation of the RMP.

Note that there is an example for a relaxator that solves a convex NLP 
at https://scipopt.org/doc/html/RELAXATOR_MAIN.php and potentially this 
could be extended to fit your purpose.

Best,
Ambros



Am 13.02.2024 um 17:08 schrieb 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
> _______________________________________________
> Scip mailing list
> Scip at zib.de
> https://listserv.zib.de/mailman/listinfo/scip