user-friendly modeling of multiple subproblems

[IssamT]

I tried to write down the suggestion of François.

Instead of this: https://github.com/atoptima/Coluna.jl/blob/master/examples/CuttingStock_SubprobMultiplicity/model_csp.jl

we could have this:

function model_scsp(d::DataCsp)
    params = Coluna.Params(use_restricted_master_heur = true)

    csp = Model(with_optimizer(Coluna.ColunaModelOptimizer, params = params),
              bridge_constraints = false)

    max_nb_patterns = sum(d.orders[o].width for o in 1:d.nborders) /
                       d.stocksheetswidth

    K = identical_block_indices(csp, max = max_nb_patterns)
    # K is the implicit description of 1:max_nb_patterns
    # value(K) is the explicit describtion of 1:nb_patterns after the model is solved

    @variable(csp, 0 <= x[k in K, o in 1:d.nborders] <= d.orders[o].demand, Int)

    @variable(csp, 0 <= y[k in K] <= 1, Bin)

    @variable(csp, 0 <= z[k in K] <= max_nb_patterns, Int)

    @constraint(csp, cov[o in 1:d.nborders],
            sum(x[k, o] * z[k] for k in K) >= d.orders[o].demand)

    @constraint(csp, knp[k in K],
            sum(x[k, o] * d.orders[o].width for o in 1:d.nborders)
            <= y[k] * d.stocksheetswidth )

    @objective(csp, Min, sum(z[k] for k in K))

    # setting Dantzig Wolfe composition: one subproblem per machine
    function csp_decomp_func(name, key)
      if name == :cov
          return 0
      else
          return key[1] # which is not an int but an IdenticalBlockIndex
      end
    end
    Coluna.set_dantzig_wolfe_decompostion(csp, csp_decomp_func)

    # setting pricing cardinality bounds (NOT NEEDED ANYMORE)
    # card_bounds_dict = Dict(1 => (0, max_nb_patterns))
    # Coluna.set_dantzig_wolfe_cardinality_bounds(csp, card_bounds_dict)

    return (csp, x,  y)
end

Then we can access the solution using:

for k in value(K)
    @show value(z[k])
    for o in 1:d.nborders
        @show value(x[o, k])
    end
end

Advantages :

• easier to understand for users.
• the original formulation could be solved by a solver without any modification/decomposition
• accessing the solution is very intuitive and does not require new tools other than those of JuMP.

Drawbacks :

• I̶t̶ ̶r̶e̶q̶u̶i̶r̶e̶s̶ ̶c̶o̶m̶m̶u̶n̶i̶c̶a̶t̶i̶o̶n̶ ̶o̶f̶ ̶i̶n̶d̶i̶c̶e̶s̶ ̶t̶o̶ ̶M̶O̶I̶ ̶w̶h̶i̶c̶h̶ ̶i̶s̶ ̶n̶o̶t̶ ̶t̶h̶e̶ ̶c̶a̶s̶e̶ ̶t̶o̶d̶a̶y̶.̶ ̶M̶O̶I̶ ̶o̶n̶l̶y̶ ̶k̶e̶e̶p̶s̶ ̶a̶ ̶s̶i̶n̶g̶l̶e̶ ̶i̶n̶t̶ ̶i̶d̶e̶n̶t̶i̶f̶i̶e̶r̶ ̶f̶o̶r̶ ̶e̶a̶c̶h̶ ̶v̶a̶r̶i̶a̶b̶l̶e̶ ̶a̶n̶d̶ ̶t̶h̶a̶t̶'̶s̶ ̶t̶h̶e̶ ̶o̶n̶l̶y̶ ̶t̶h̶i̶n̶g̶ ̶c̶o̶m̶m̶u̶n̶i̶c̶a̶t̶e̶d̶ ̶t̶o̶ ̶s̶o̶l̶v̶e̶r̶s̶.
• It requires generating variables on JuMP side after the model is solved or an extra number of variables before the model is solved.
• blocks (master, pricing sp, ...) are not annotated only with ints
• longer to write for expert users

[rrsadykov]

It is good for me. The only thing is the meaning of "key[1]" in csp_decomp_func. I do not understand what does this mean.

[IssamT]

key is the name for multi-index in jump. For example, the function can be called with name="x" and key = (k, o). In this case, key[1] is k

[FD-V]

following the model in my email the code would look like

function model_scsp(d::DataCsp)
    params = Coluna.Params(use_restricted_master_heur = true)

    csp = Model(with_optimizer(Coluna.ColunaModelOptimizer, params = params),
              bridge_constraints = false)

    max_nb_patterns = sum(d.orders[o].demand for o in 1:d.nborders) 

    O = index_set(csp, d.nborders) # K denotes the set of stock sheet type index
    K = index_set(csp, 1) # K denotes the set of stock sheet type index
    P = sub_index_set(csp,  K, max_nb_patterns) # P denotes the set of cutting  pattern index for a given stock sheet type, in this case indentical for each k in K

    Coluna.set_dantzig_wolfe_decomposition(csp, K) # defines a pricing subproblem per index k in K 
    for k in K 
       Coluna.set_dantzig_wolfe_subdecomposition(csp, k, P) # defines a pricing subsubproblem per index k in K 
    end

    @variable(csp, 0 <= x[k in K, p in P, o in O] <= d.orders[o].demand, Int)

    @variable(csp, 0 <= z[k in K, p in P] <= max_nb_patterns, Int)

    @constraint(csp, cov[o in 1:d.nborders],
            sum(x[k, p, o] * z[k] for k in K, p in P) >= d.orders[o].demand)

    @constraint(csp, knp[k in K, p in P],
            sum(x[k, p, o] * d.orders[o].width[k] for o in O)
            <=  d.stocksheetswidth[k] )

    @objective(csp, Min, sum(z[k, p] for k in K, p in P))

    # setting Dantzig Wolfe decomposition function: (NOT NEEDED ANYMORE)
    # setting pricing cardinality bounds (NOT NEEDED ANYMORE)

    return (csp, x,  z)
end

Then we can access the solution using:

for (k,p) in (K,P)
    @show value(z[k, p])
    for o in 0
        @show value(x[k, p, o])
    end
end

[rrsadykov]

François, this model is for cutting stock with several stock sheet types? This is too complicated for me.
The proposition of Issam was much more clearer for me (although we can probably remove variables y[k] from there).
I think we should stick to the standard way to define the decomposition: by indicating the constraints which go to master/subproblem.

[IssamT]

Here are the several models discussed in the meeting with different modeling "style". for now model 2 is almost available for all considered applications.

https://github.com/atoptima/Coluna.jl/wiki

[rrsadykov]

Issam, Is there any documentation for @axis? Is it the standard JuMP thing or a new one? Ruslan

…

On 4 Feb 2019, at 16:28, Issam Tahiri ***@***.***> wrote: Here are the several models discussed in the meeting. with different modeling "style" for now model 2 is almost available for all considered applications. https://github.com/atoptima/Coluna.jl/wiki — You are receiving this because you commented. Reply to this email directly, view it on GitHub, or mute the thread.

--------------------------------------------------------------- Ruslan Sadykov Research Fellow ( CR1 ) Project-team RealOpt INRIA Bordeaux - Sud-Ouest 351 cours de la Libération, 33405 Talence, France +33 5 40 00 60 52 http://www.math.u-bordeaux.fr/~sadykov/