The Library
Algorithms to separate {0,1/2}-Chvátal-Gomory cuts
Tools
Tools
Tools
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. ISSN 0178-4617. doi:10.1007/s00453-008-9218-7
Research output not available from this repository, contact author.
Official URL: http://dx.doi.org/10.1007/s00453-008-9218-7
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 | ||||
| Dates: |
|
||||
| Volume: | Vol.55 | ||||
| Number: | No.2 Sp. Iss. SI | ||||
| Number of Pages: | 17 | ||||
| Page Range: | pp. 375-391 | ||||
| DOI: | 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 |
Data sourced from Thomson Reuters' Web of Knowledge
Request changes or add full text files to a record
Repository staff actions (login required)
 |
View Item |
