[Dip] Differences between GAP examples

[Florian Fontan]

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/0595d897/attachment.html>