[Dip] Differences between GAP examples
Florian Fontan
dev at florian-fontan.fr
Wed Jun 12 17:20:01 EDT 2019
Thanks! Yes, it is very likely that I just misunderstand what the code
is doing
I linked this article since it is the best branch-and-price published.
But the previous state-of-the-art exact algorithm was already a
branch-and-price
https://pubsonline.informs.org/doi/abs/10.1287/opre.45.6.831 and the
current one strongly relies on the Lagrangian relaxation
https://link.springer.com/article/10.1007/s10589-011-9432-0
Florian
Le 12/06/2019 à 23:07, Matthew Galati a écrit :
> 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
> <mailto: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 <mailto: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 <mailto: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 <mailto: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/2e4a3735/attachment.html>
More information about the Dip
mailing list