[Dip] Differences between GAP examples

[Matthew Galati]

Yes, the bound at the root should be at least as good as the LP bound and
yes, it is equal to the Lagrangian bound. If Ted has some time, maybe he
can investigate. It sounds like the code might not be doing what you think
it is doing.

As for "decomposition" working "well" on GAP... don't believe everything
you read on OptOnline. :)

On Wed, Jun 12, 2019 at 4:49 PM Florian Fontan <dev at florian-fontan.fr>
wrote:

> I tested the default version, i.e. the one using Pisinger's algorithm to
> solve the knapsack sub-problems.
>
> Decomposition techniques should work rather well for GAP. For example:
> http://www.optimization-online.org/DB_FILE/2004/11/990.pdf
>
> Furthermore, isn't the PC relaxation supposed to be at least as good as
> the linear relaxation? I though it was even supposed to be equal to the
> bound from the Lagrangian relaxation of the assignment constraints. I've
> implemented on my own the Lagrangian relaxation of the assignment
> constraints that I solved with Vol from COIN-OR, and it finds a lower bound
> of 1698 in 0.02s for instance a05100. And I'm sure that the problems are
> exactly the same.
>
> For the 1693 with doCut=1, it really seems to me that it may come from the
> non-implementation of the knapsack constraints in GAP_DecompApp.cpp
>
>      setModelRelax(NULL, modelName, i);
>
> I don't know if there's a reason why they are not added here whereas they
> are in GAP_DecompApp3.cpp
>
> Florian
> Le 12/06/2019 à 22:23, Matthew Galati a écrit :
>
> Sure that can happen. It just means that the PC relaxation is too weak and
> that is a bad way to solve the problem. Is that with the KP oracle or the
> AP oracle? I would expect the bound using the KP oracle to be strong.
>
> If you get 1693 with doDirect or doCut but 1698 with CBC, then either (a)
> there is a bug, or (b) you are not creating the same model.
>
> On Wed, Jun 12, 2019 at 4:14 PM Florian Fontan <dev at florian-fontan.fr>
> wrote:
>
>> Indeed! I didn't think to look there.
>>
>> I managed to compile the GAP example. I tested on instance a05100. This
>> instance is solved optimally by a naive implementation in CBC in 0.005s.
>> The optimal value is 1698 which is actually also the upper bound from the
>> linear relaxation. When I try the GAP implementation given as example in
>> Dip on this instance (./decomp_gap --param gap.parm)
>>
>>    - with doPriceCut = 1, doCut = 0, doDirect = 0: the lower bound found
>>    is 1556, no feasible solution is found and the algorithm doesn't terminate
>>    after at least several minutes
>>    - with doPriceCut = 0, doCut = 1, doDirect = 0 or doDirect = 1: the
>>    algorithm terminates very quickly, returning a best lower bound and a best
>>    upper bound of 1693. I think it may be the solution of the problem with the
>>    capacity constraints removed.
>>
>> Is this the expected behavior?
>>
>> Florian
>> Le 11/06/2019 à 22:34, Matthew Galati a écrit :
>>
>> The Makefile gives some hints... one case using the built-in MILP solver,
>> one case uses a KP solver.
>>
>> #PC: oracle for KP solve is Pisinger, BranchEnforceInMaster
>> OBJS += GAP_DecompApp. at OBJEXT@
>> CFLAGS = -DVERSION1
>> #TODO: BranchEnforceInSubProb using GAP_DecompApp2 or by option
>> # CPM/PC: built-in MILP solver, dense model build
>> # BranchEnforceInMaster or BranchEnforceInSubProb by option
>> #OBJS += GAP_DecompApp3. at OBJEXT@
>> #CFLAGS += -DVERSION3
>> # CPM/PC: built-in MILP solver, sparse model build
>> # BranchEnforceInMaster or BranchEnforceInSubProb by option
>> #OBJS += GAP_DecompApp4. at OBJEXT@
>> #CFLAGS += -DVERSION4
>>
>> On Tue, Jun 11, 2019 at 3:41 PM Florian Fontan <dev at florian-fontan.fr>
>> wrote:
>>
>>> Dear Dip community,
>>>
>>> I am trying to get familiar with Dip and understand how it works. Could
>>> someone tell me the differences between the multiple DecompApp
>>> implementation examples for the Generalized Assignment Problem?
>>> https://github.com/coin-or/Dip/tree/master/Dip/examples/GAP
>>>
>>> For example, in GAP_DecompApp.cpp, I noticed that the setModelRelax call
>>> passes NULL as first argument:
>>>
>>>      setModelRelax(NULL, modelName, i);
>>>
>>> whereas in GAP_DecompApp3.cpp, an other model is defined:
>>>
>>>      status = createModelPartKP(modelRelax, i);
>>>      modelName = "KP" + UtilIntToStr(i);
>>>      setModelRelax(modelRelax, modelName, i);
>>>
>>> What does that mean? I haven't found any documentation about it
>>>
>>> Florian
>>> _______________________________________________
>>> Dip mailing list
>>> Dip at list.coin-or.org
>>> https://list.coin-or.org/mailman/listinfo/dip
>>>
>>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://list.coin-or.org/pipermail/dip/attachments/20190612/c720efc4/attachment-0001.html>