An algorithm for the separation of two-row cuts

Autor:	Laurent Poirrier, Quentin Louveaux
Rok vydání:	2012
Předmět:	Polynomial (hyperelastic model) Discrete mathematics General Mathematics Computation Numerical analysis Computer Science::Computational Geometry Type (model theory) Combinatorics Quadratic equation Integer Algorithm Integer programming Row Software Mathematics
Zdroj:	Mathematical Programming. 143:111-146
ISSN:	1436-4646 0025-5610
DOI:	10.1007/s10107-012-0597-9
Popis:	We consider the question of finding deep cuts from a model with two rows of the type $$P_I=\{(x,s)\in \mathbb{Z }^2\times \mathbb{R }^n_+ : x=f+Rs\}$$ . To do that, we show how to reduce the complexity of setting up the polar of $$\mathop {\mathrm{conv}}(P_I)$$ from a quadratic number of integer hull computations to a linear number of integer hull computations. Furthermore, we present an algorithm that avoids computing all integer hulls. A polynomial running time is not guaranteed but computational results show that the algorithm runs quickly in practice.
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_________::059f158aaf82fb8f1ab00025a9846e1b https://doi.org/10.1007/s10107-012-0597-9 Zobrazit plný text záznamu Full text from SpringerLink