[Dip] Differences between GAP examples

Ted Ralphs ted at lehigh.edu
Wed Jun 12 18:19:55 EDT 2019 

You definitely need to take the claims of computational papers with a big
grain of salt. Matt has much more practical experience than me, but I would
expect DIP's BP to beat its own BC handily on GAP. Comparing to commercial
solvers is really an apples to oranges comparison. In any case, you would
need to test with a more difficult and varied set of instances to draw any
conclusions. Anything can happen on a given instance.

On the other hand, what you're observing looks like either a true bug or a
result of numerical error. I will try to take a look at it. As Matt said,
Dip hasn't been under active development for some time, but it's always
good to have an excuse to dig into it.

Ted

On Wed, Jun 12, 2019 at 6:05 PM Matthew Galati <matthew.galati at gmail.com>
wrote:

> Yes. Understood.
>
> It is probably a bug in the GAP example code. I have not looked at it in
> over 10 years.
>
> As for branch-and-price (BP) vs branch-and-cut (BC) for GAP, in my
> experience GAP is handled quite well by BC -- and BP will rarely outperform
> it (in most cases) - at least using a "standard" (generic) BP
> implementation. I am sure it is possible to make BP competitive with BC for
> GAP with some tricks. But, I have not seen good evidence of this for a
> standard approach.
>
> I think BC solvers have just gotten really good at generating strong cuts
> for those polytopes (in GAP). So, BP will add no real value there.
>
> BP "wins" on two main cases (in my experience): (a) block angular where
> parallelism is exploited, (b) cases where the known cutting planes in BC
> solvers are ineffective - so BP gets the bound strength from a different
> direction (the inner expansion of the polytope, rather than an outer
> expansion).
>
> On Wed, Jun 12, 2019 at 5:20 PM Florian Fontan <dev at florian-fontan.fr>
> wrote:
>
>> 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>
>> 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
>>>>>
>>>> _______________________________________________
> Dip mailing list
> Dip at list.coin-or.org
> https://list.coin-or.org/mailman/listinfo/dip



-- 
Dr. Ted Ralphs
Professor, Industrial and Systems Engineering
Lehigh University
(610) 628-1280
ted 'at' lehigh 'dot' edu
coral.ie.lehigh.edu/~ted
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://list.coin-or.org/pipermail/dip/attachments/20190612/9eb04fd7/attachment-0001.html>

More information about the Dip mailing list