CglFlowCover

Contributor: Jeff Linderoth, Martin Savelsbergh, Yan Xu

Maintainer: Yan Xu (@yanxu55)

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.

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 continuous and y's are binary. The opposite convention is used in release 0.5.1 and version 0.51 and earlier.

• 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 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_1 z_1 + a_2 z_2 - a_3 z_3 <= rhs Letting y_i = a_i z_i the canonical "single node system" form is obtained:

  y_1 + y_2 - y_3 <= rhs,
  y_1 <= up_1 x_1,
  y_2 <= up_2 x_2,
  y_3 <= up_3 x_3,
  

  (Note: up, y, and x are variable names used in CglFlowCover:generateOneFlowCut() method).

• 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.

References:

• 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.