Best way to use Cgl within JuMP?

Specific Domains Optimization (Mathematical)
1

Hi,

I need to use the Cgl cut generation library GitHub - coin-or/Cgl: Cut Generator Library from within JuMP.

In particular I want to generate KnapsackCover cuts.

I managed to install Cgl, however I’m struggling because it is written in C++ and I would like to pass it a model solved with Clp, on which it is based.

So far my idea was to do the following:

using JuMP
using Clp

m = Model(Clp.Optimizer)

#define MIP model here ...
#...

ccall((:Clp_initialSolve, Clp.libClp), Cint, (Ptr{Clp_Simplex},), unsafe_backend(m)) # solve continuous relaxation.
ccall(...) # C wrapper function which passes unsafe_backend(m) to a C++ function which would generate Knapsack Covers using Cgl.

The first question I have is if this approach is right or if there is a simpler way ?

Second, the issue I have is I can’t find a way to access the backend object from C, as the original Clp code is in C++ and I don’t know which wrapper is used in Clp.jl

2

There is no easy way to use Cgl from JuMP.

The wrapper in Clp.jl exposes these methods:

which are provided by coin-or/clp here:

Importantly, this is not a C++ interface, but an extern "C" interface.

Why are you trying to use Cgl? What is the goal? It might be easier just to write the cuts using JuMP and never touch the low-level Clp model.

3

Thanks for your answer.

I implemented a branch-and-price algorithm using JuMP for a specialized multicommodity flow problem. However the resolution is quite slow for now and would benefit a lot from additional cuts (mainly knapsack cover cuts but I would love to be able to experiment with other cuts afterwards).

If you have any suggestion for example implementations that are known to perform well (and ideally that are quite readable) that would be greatly appreciated.

If anyone is looking too, so far, aside from Cgl I found this implementation: Discrete-Optimization/Knapsack Cover Inequalities at main · prameshk/Discrete-Optimization · GitHub (but I doubt a tutorial would be state-of-the-art)
and the code from this paper which looks quite promising An implementation of exact knapsack separation | SpringerLink Code available here: https://web.archive.org/web/20170113070323/http://iv.icc.ru/Papers.html

1 Like