On a generalization of the Chvátal–Gomory closure

Autor:	Oktay Günlük, Dabeen Lee, Sanjeeb Dash
Rok vydání:	2021
Předmět:	Combinatorics Set (abstract data type) Polyhedron Unit cube Generalization General Mathematics Closure (topology) Mathematics::Metric Geometry Polytope Integer programming Software Variable (mathematics) Mathematics
Zdroj:	Mathematical Programming. 192:149-175
ISSN:	1436-4646 0025-5610
Popis:	Many practical integer programming problems involve variables with one or two-sided bounds. Dunkel and Schulz (A refined Gomory–Chvatal closure for polytopes in the unit cube, http://www.optimization-online.org/DB_FILE/2012/03/3404.pdf , 2012) considered a strengthened version of Chvatal–Gomory (CG) inequalities that use 0–1 bounds on variables, and showed that the set of points in a rational polytope that satisfy all these strengthened inequalities is a polytope. Recently, we generalized this result by considering strengthened CG inequalities that use all variable bounds. In this paper, we generalize further by considering not just variable bounds, but general linear constraints on variables. We show that all points in a rational polyhedron that satisfy such strengthened CG inequalities form a rational polyhedron. We also extend this polyhedrality result to mixed-integer sets defined by linear constraints.
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_________::77641d2e448887e5f6dea4e6ddafb767 https://doi.org/10.1007/s10107-021-01697-0 Zobrazit plný text záznamu Full text from SpringerLink