Skip to content Skip to navigation
University of Warwick
  • Study
  • |
  • Research
  • |
  • Business
  • |
  • Alumni
  • |
  • News
  • |
  • About

University of Warwick
Publications service & WRAP

Highlight your research

  • WRAP
    • Home
    • Search WRAP
    • Browse by Warwick Author
    • Browse WRAP by Year
    • Browse WRAP by Subject
    • Browse WRAP by Department
    • Browse WRAP by Funder
    • Browse Theses by Department
  • Publications Service
    • Home
    • Search Publications Service
    • Browse by Warwick Author
    • Browse Publications service by Year
    • Browse Publications service by Subject
    • Browse Publications service by Department
    • Browse Publications service by Funder
  • Help & Advice
University of Warwick

The Library

  • Login
  • Admin

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

Request Changes to record.

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:
DateEvent
October 2009Published
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 View Item
twitter

Email us: wrap@warwick.ac.uk
Contact Details
About Us