wiki:CglFlowCover

CglFlowCover

Contributor: Jeff Linderoth, Martin Savelsbergh, Yan Xu
Maintainer: Yan Xu, Yan.Xu@…

Introduction

The Cgl Flow Cover Cut generator generates lifted simple generalized flow cover inequalities. Since flow cover inequalities are generally not facet-defining, they are lifted to obtain stronger inequalities. Although flow cover inequalities requires a special problem structure to be generated, they are quite useful for solving general mixed integer linear programs.

Understanding the Implementation

At the risk of this quickly becomming out of sync with the implementation, I'm jotting down some things I learned about the CglFlowCover implementation. Additions/corrections welcome!

  • A working copy of the paper cited below was used by Yan in implementing the code.
  • In the paper, x's are continous and y's are binary. The opposite convention is used in release 0.5.1 and version 0.51 and earlier. (Which convention should I use for this documentation? Argh?!)
  • In Cgl release 0.5.1 and stable version: 0.51, the lifting is #ifdef'd out. This part of the code was disabled because invalid cuts were being generated. The bug was not reported in the tracking system. This needs to be fixed.
  • The paper explains flow cover cuts in terms of a cannonical form, i.e.,
$\sum_{j\in N^+}x_j - \sum_{j\in N^-}x_j \le d, x_j \le m_jy_j, j\in N$

the implementation identifies and stores VUB information from the problem data once in a pre-processing step. The implementation looks at a (some what select) row of the matrix that may have continuous or integer variables and tries to generate a flow cover cut. How does the implementation map the generic row into the cannonical form? Good question. The code uses the approach described on page 286 of Nemhauser and Woolsey's book, "Integer and Combinatorial Optimization." Essentially, they introduce "fake" binaries are introduced and "fake" VUBs. (Note: This is a different approach than in the CglKnapsackCover, which transforms the generic row into its canonical form by replacing the continous variables by their appropriate bounds. Which way is better? It depends on the problem data. It'd be interesting to implement a test for the better approach based on the coefficients, bounds, and rhs and use the stronger of the two approaches.) Example:

$a_1z_1 + a_2z_2 - a_3z_3 \le rhs$

the canonical "single node system" form is obtained

$y_1 + y_2 - y_3 \le rhs$, 
$y_1 \le up_1x_1$, 
$y_2 \le up_2x_2$, 
$y_3\le up_3x_3$, 

(note: "up," "y," and "x" are variable names used in CglFlowCover:generateOneFlowCut() method) and by letting

$y_i = a_iz_i$.
  • In CglFlowCover release 0.5.1 and stable version: 0.51 has one (approximate) method for finding a cover. (It'd be interesting to see different methods and try using exact methods for small-sized problem. Code to do this already exists for CglKnapsackCover, but using a slighly different problem representation.)
  • Finding a cover: The code finds a cover by solving a relaxaton of the real separation problem (which is non-linear mip). For more details on what the real separation problem is and how the relaxed problem comes about, see page 498 of Nemhauser and Wolsey's book.

Papers, Presentations, and References

  • R. Lougee-Heimer, J. Forrest, G. Grun, A. Marting, M. Trick, and Y. Xu, "COIN-OR Open-Source Coding Contest", INFORMS, Atlanta, 2003.
  • Z. Gu, G.L. Nemhauser, M.W.P. Savelsbergh, Lifted flow cover inequalities for mixed 0-1 integer programs, Math. Programming A 85 (1999) 439-467.

Documentation and Bug Reports

See the section "Project Links" on the Cgl main Trac page.

Last modified 11 years ago Last modified on Nov 29, 2007 3:55:31 PM