Janny Leung

Reinforcing Old Fences Gives New Facets and More

Categories Combinatorial Optimization, Integer Programming, Polyhedra

The unpublished 1990 technical report reproduced here introduced the $t$-reinforced $k$-fence inequalities, the first facets of the acyclic subgraph polytope that are not rank inequalities: each simple $k$-fence induces $k-2$ of them, one for each $1\le t\le k-2$. The report proved this with the spectral method, using a coherent configuration and computer algebra. It went … Read more

A Polytope for a Product of Real Linear Functions in 0/1 Variables

Categories 0-1 Programming Tags ,

In the context of integer programming, we develop a polyhedral method for linearizing a product of a pair of real linear functions in 0/1 variables. As an example, by writing a pair of integer variables in binary expansion, we have a technique for linearizing their product. We give a complete linear description for the resulting … Read more