Koster, Arie M. C. A., Zymolka, Adrian and Kutschka, Manuel (2009) Algorithms to separate {0,1/2}-Chvátal-Gomory cuts. In: 15th Annual European Symposium on Algorithms (ESA 2007), Eilat, Israel, October 08-10, 2007. Published in: Algorithmica, Vol.55 (No.2 Sp. Iss. SI). pp. 375-391.

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 (Math. Program. 74: 221-235, 1996) 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 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. Some simple heuristic separation routines complete the algorithmic framework.

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 (Paper)
Subjects:	Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software Q Science > QA Mathematics
Divisions:	Faculty of Science > Mathematics
Journal or Publication Title:	Algorithmica
Publisher:	Springer Verlag
ISSN:	0178-4617
Official Date:	October 2009
Volume:	Vol.55
Number:	No.2 Sp. Iss. SI
Number of Pages:	17
Page Range:	pp. 375-391
Identification Number:	10.1007/s00453-008-9218-7
Status:	Peer Reviewed
Publication Status:	Published
Access rights to Published version:	Restricted or Subscription Access
Description:	From the issue entitled "Special Issue: European Symposium on Algorithms 2007, Guest Editors: Larse Arge and Emo Welzl"
Funder:	DFG research group “Algorithms, Structure, Randomness”, Centre for Discrete Mathematics and its Applications (DIMAP)
Grant number:	GR 883/9-3, GR 883/9-4
Conference Paper Type:	Paper
Title of Event:	15th Annual European Symposium on Algorithms (ESA 2007)
Type of Event:	Conference
Location of Event:	Eilat, Israel
Date(s) of Event:	October 08-10, 2007
URI:	http://wrap.warwick.ac.uk/id/eprint/27879

Data sourced from Thomson Reuters' Web of Knowledge

Request changes or add full text files to a record

Actions (login required)

View Item