Abstract
In polyhedral combinatorics, the polytope related to a combinatorial optimization problem is examined in order to obtain families of valid inequalities. To incorporate such families of inequalities within a 'Branch & Cut' algorithm requires one further step: that of deriving an algorithm which determines whether an inequality of a specific family is violated by a given vector (the separation problem). The idea put forward in this work is to consider a compact representation of the given vector, and measure the complexity of a separation algorithm in terms of this compact representation. We illustrate the idea on the separation of known inequalities for the three index assignment polytope. It turns out that we find new separation algorithms with better complexities than the current ones (that were called best possible).
| Original language | English |
|---|---|
| Title of host publication | Combinatorial Optimization |
| Subtitle of host publication | Second International Symposium, ISCO 2012, Revised Selected Papers |
| Editors | A.R. Mahjoub, V. Markakis, I. Milis, V.T. Paschos |
| Place of Publication | Berlin |
| Publisher | Springer |
| Chapter | 18 |
| Pages | 189-200 |
| Number of pages | 12 |
| ISBN (Electronic) | 978-3-642-32147-4 |
| ISBN (Print) | 978-3-642-32146-7 |
| DOIs | |
| Publication status | Published - 2012 |
| Externally published | Yes |
| Event | 2nd International Symposium on Combinatorial Optimization (ISCO 2012) - Athens, Greece Duration: 19 Apr 2012 → 21 Apr 2012 Conference number: 2 http://www.lamsade.dauphine.fr/~isco/ISCO2012/ |
Publication series
| Name | Lecture Notes in Computer Science |
|---|---|
| Volume | 7422 |
| ISSN (Print) | 0302-9743 |
| ISSN (Electronic) | 1611-3349 |
Conference
| Conference | 2nd International Symposium on Combinatorial Optimization (ISCO 2012) |
|---|---|
| Abbreviated title | ISCO 2012 |
| Country/Territory | Greece |
| City | Athens |
| Period | 19/04/12 → 21/04/12 |
| Internet address |