Koster, Arie M. C. A., Zymolka, Adrian and Kutschka, Manuel (2007) Algorithms to separate {0,1/2}-Chvatal-Gomory cuts. In: 15th Annual European Symposium on Algorithms (ESA 2007), Eilat, ISRAEL, OCT 08-10, 2007. Published in: ALGORITHMS - ESA 2007, PROCEEDINGS, 4698 pp. 693-704.

Full text not available from this repository.

Abstract

Chvatal-Gomory cuts are among the most well-known classes of cutting planes for general integer linear programs (ILPs). In case the constraint multipliers are either 0 or 1/2, such cuts are known as {0, 1/2}-cuts. It has been proven by Caprara and Fischetti [7] that separation of {0, 1/2}-cuts is NP-hard. In this paper, we study ways to separate {0,1/2}-cuts effectively in practice. We 2 propose a range of preprocessing rules to reduce the size of the separation problem. The core of the preprocessing builds a Gaussian elimination-like procedure. TO separate the most violated {0,1/2}-cut, we formulate the (reduced) problem as integer linear program and develop some simple heuristic separation routines. Computational experiments on benchmark instances show that the combination of preprocessing with exact and/or heuristic separation is a very vital idea to generate strong generic cutting planes for integer linear programs and to reduce the overall computation times of state-of-the-art ILP-solvers.

Item Type:	Conference Item (UNSPECIFIED)
Subjects:	Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software
Divisions:	Faculty of Science > Mathematics
Series Name:	LECTURE NOTES IN COMPUTER SCIENCE
Journal or Publication Title:	ALGORITHMS - ESA 2007, PROCEEDINGS
Publisher:	SPRINGER-VERLAG BERLIN
ISBN:	978-3-540-75519-7
ISSN:	0302-9743
Editor:	Arge, L and Hoffmann, M and Welzl, E
Date:	2007
Volume:	4698
Number of Pages:	12
Page Range:	pp. 693-704
Publication Status:	Published
Title of Event:	15th Annual European Symposium on Algorithms (ESA 2007)
Location of Event:	Eilat, ISRAEL
Date(s) of Event:	OCT 08-10, 2007
URI:	http://wrap.warwick.ac.uk/id/eprint/30774

Data sourced from Thomson Reuters' Web of Knowledge

Request changes to a record

Actions (login required)

View Item