[Dip] generateCuts Question

[Kipp Martin]

Hi Matt:

> Kipp - the example you sent finds the optimal solution after a few 

How does it know the solution is optimal, if integrality does not imply 
optimality? See me example below.
> passes of pricing and therefore never calls the cut generator. By 
> default, the PC solver, in the root node starts with pricing, and does 
> not stop until it prices out (or finds optimal, or within gap limits).
> 
> If it prices out and has not yet found optimal, then it will proceed to 
> cuts.

Let's say I want solve some sort of routing problem (which is what I 
need to do) and I want to generate using  generateCuts() the tour 
breaking constraints. Assume that at the root node,  that after pricing, 
I have an integer solution in my original variable space. So it seems 
like Dip will think it is "optimal" since there is an integer solution 
and not call generateCuts().  However, this integer solution could 
certainly violate a tour breaking constraint that I need to add.

If I set

  [DECOMP]
  LimitRoundPriceIters = 1
  LimitRoundCutIters   = 1

then this seem like it could be pretty inefficient.

What do you and Ted do for the routing problems you guys solve to 
guarantee generateCuts() will get called if there is an integer solution 
and you want to guarantee no subtours. Do you set the parameters above?

Thanks


> 
> This is parameter driven.
> 
> 
> You'll see in the log file (LogDebugLevel = 3),
> PRICE_AND_CUT  LimitRoundCutIters       2147483647
> PRICE_AND_CUT  LimitRoundPriceIters     2147483647
> 
> This is the number of Price/Cut iterations to take before switching off 
> (i.e., MAXINT).
> 
> To force it to cut before pricing out, change this parameter in the parm 
> file. For example, if you change to :
> 
> [DECOMP]
> LimitRoundPriceIters = 1
> LimitRoundCutIters   = 1
> 
> It will then go into your generateCuts after one pricing iteration.
> 
> 
> 
> 
> 
> 
> 
> On Tue, Oct 5, 2010 at 7:24 PM, Kipp Martin <kmartin at chicagobooth.edu 
> <mailto:kmartin at chicagobooth.edu>> wrote:
> 
>     Hi:
> 
>     The class DecompApp has a virtual function
> 
> 
>     virtual int generateCuts(const double  * x,
>          DecompCutList & newCuts);
> 
> 
>     I have implemented this function in a class that derives from DecompApp.
>      When solving an integer program that has an integer LP relaxation
>     value, generateCuts() does not get called. This seems like a potential
>     problem for routing problems where I might want  generateCuts() to
>     generate subtour elimination constraints. It is possible to have an
>     integer solution and a subtour so I want generateCuts called even with
>     an integer solution.
> 
>     Indeed, in the sample code, TSP_DecompApp.cpp I see the implementation
>     of generateCuts() calls in turn generateCutsSubtour(). But will
>     generateCuts() get called if there is an integer solution? It seems like
>     it should, yet I have an example where generateCuts() is not being
>     called when the LP is integer.
> 
>     Thanks
> 
> 


-- 
Kipp Martin
Professor of Operations Research
and Computing Technology
Booth School of Business
University of Chicago
5807 South Woodlawn Avenue
Chicago, IL 60637
773-702-7456
kmartin at chicagobooth.edu
http://www.chicagobooth.edu/faculty/bio.aspx?person_id=12825325568
http://projects.coin-or.org/OS