Sequential-merge facets for two-dimensional group problems

Santanu S. Dey, Jean Philippe P. Richard

Research output: Chapter in Book/Report/Conference proceedingConference contribution

9 Scopus citations

Abstract

In this paper, we show how to generate strong cuts for unstructured mixed integer programs through the study of high-dimensional group problems. We present a new operation that generates facet-defining inequalities for two-dimensional group problems by combining two facet-defining inequalities of one-dimensional group problems. Because the procedure allows the use of a large variety of one-dimensional constituent inequalities, it yields large families of new cutting planes for MIPs that we call sequentialmerge inequalities. We show that sequential-merge inequalities can be used to generate inequalities whose continuous variable coefficients are stronger than those of one-dimensional cuts and can be used to derive the three-gradient facet-defining inequality introduced by Dey and Richard [4].

Original languageEnglish (US)
Title of host publicationInteger Programming and Combinatorial Optimization - 12th International IPCO Conference, Proceedings
PublisherSpringer Verlag
Pages30-42
Number of pages13
ISBN (Print)9783540727910
DOIs
StatePublished - 2007
Externally publishedYes
Event12th International Conference on Integer Programming and Combinatorial Optimization, IPCO XII - Ithaca, NY, United States
Duration: Jun 25 2007Jun 27 2007

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume4513 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other12th International Conference on Integer Programming and Combinatorial Optimization, IPCO XII
CountryUnited States
CityIthaca, NY
Period6/25/076/27/07

Fingerprint Dive into the research topics of 'Sequential-merge facets for two-dimensional group problems'. Together they form a unique fingerprint.

Cite this