Hijazi, Hassan, Bonami, Pierre, Cornuéjols, Gérard, Ouorou, Adam
We call ”on/off” constraint an algebraic constraint that is activated if and only if a corresponding boolean variable is turned ”on” or equal to 1. Our main subject of interest is to derive...
Hijazi, Hassan, Bonami, Pierre, Cornuéjols, Gérard, Ouorou, Adam
We call ”on/off” constraint an algebraic constraint that is activated if and only if a corresponding boolean variable is turned ”on” or equal to 1. Our main subject of interest is to derive...
Bicolorings and Equitable Bicolorings of Matrices (2008)
Michele Conforti, Gérard Cornuéjols, Giacomo Zambelli
Two classical theorems of Ghouila-Houri and Berge characterize total unimodularity and balancedness in terms of equitable bicolorings and bicolorings, respectively. In this paper, we prove a...
Gérard Cornuéjols, Bertrand Guenin, Levent Tunçel
ABSTRACT. A pair of square 0, 1 matrices A, B such that AB T = E + kI (where E is the n × n matrix of all 1s and k is a positive integer) are called Lehman matrices. These matrices figure...
On Padberg’s conjecture about almost totally unimodular matrices (2007)
Gérard Cornuéjols, Luis F. Zuluaga
We consider Padberg’s conjecture about almost totally unimodular matrices proposed in 1988 in Operations Research Letters. We show that it is not correct as stated and give a modified version of...
Gérard Cornuéjols, Bertrand Guenin
ABSTRACT. For every nonnegative integer arc weight function Û, the minimum weight of a dicut is at least as large as the maximum number of dijoins such that no arc � is contained in more than Û...
Projected Chvátal-Gomory cuts for Mixed Integer Linear Programs (2006)
Pierre Bonami, Gérard Cornuéjols, Sanjeeb Dash, Matteo Fischetti, Andrea Lodi
Recent experiments by Fischetti and Lodi show that the first Chvátal closure of a pure Integer Linear Program (ILP) often gives a surprisingly tight approximation of the integer hull. They optimize...
Valid inequalities for mixed integer linear programs (2006)
Abstract. This tutorial presents a theory of valid inequalities for mixed integer linear sets. It introduces the necessary tools from polyhedral theory and gives a geometric understanding of several...
Early estimates of the size of branch-and-bound trees (2006)
Gérard Cornuéjols, Miroslav Karamanov, Yanjun Li
This paper intends to show that the time needed to solve mixed integer programming problems by branch and bound can be roughly predicted early in the solution process. We construct a procedure that...
A Feasibility Pump for Mixed Integer Nonlinear Programs (2006)
Pierre Bonami, Gérard Cornuéjols, Andrea Lodi, François Margot
Abstract We present an algorithm for finding a feasible solution to a convex mixed integer nonlinear program. This algorithm, called Feasibility Pump, alternates between solving nonlinear programs...
Early estimates of the size of branch-and-bound trees (2006)
Gérard Cornuéjols, Miroslav Karamanov, Yanjun Li
informs ® doi 10.1287/ijoc.1040.0107
Pierre Bonami, Lorenz T. Biegler, Andrew R. Conn, Gérard Cornuéjols, Ignacio E. Grossmann, Carl D. Laird, ...
algorithmic framework for convex mixed integer
Reduce-and-split cuts: Improving the performance of mixed-integer gomory cuts (2005)
Kent Andersen, Gérard Cornuéjols
Yanjun Li 3 Mixed integer Gomory cuts have become an integral part of state-of-the-art software for solving mixed integer linear programming problems. Therefore, improvements in the performance of...
A Convex-Analysis Perspective on Disjunctive Cuts (2004)
Cornuéjols, Gérard, Lemaréchal, Claude
We treat the general problem of cutting planes with tools from convex analysis. We emphasize the case of disjunctive polyhedra and the generation of facets. We conclude with some considerations on...
A Convex-Analysis Perspective on Disjunctive Cuts (2004)
Cornuéjols, Gérard, Lemaréchal, Claude
We treat the general problem of cutting planes with tools from convex analysis. We emphasize the case of disjunctive polyhedra and the generation of facets. We conclude with some considerations on...
A Convex-Analysis Perspective on Disjunctive Cuts (2004)
Cornuéjols, Gérard, Lemaréchal, Claude
We treat the general problem of cutting planes with tools from convex analysis. We emphasize the case of disjunctive polyhedra and the generation of facets. We conclude with some considerations on...
Synopses Graphs and Combinatorial Optimization (2004)
It is planned that lecture notes will be available to those who register for this course. Advance registration fees are $80 for AMS/MAA members, $110 for nonmembers, and $35 for...
Odd Hole Recognition in Graphs of Bounded Clique Size (2004)
Michele Conforti, Gérard Cornuéjols, Xinming Liu, Giacomo Zambelli
In a graph G, an odd hole is an induced odd cycle of length at least five. A clique of G is a set of pairwise adjacent vertices. In this paper we consider the class Ck of graphs whose cliques have a...
Recognizing Berge Graphs (2004)
Maria Chudnovsky, Gérard Cornuéjols, Xinming Liu, Paul Seymour , Et Al.
A graph is Berge if no induced subgraph of G is an odd cycle of length at least five or the complement of one. In this paper we give an algorithm to test if a graph G is Berge, with running time O(|V...
The strong perfect graph conjecture (2003)
A graph is {\em perfect} if, in all its induced subgraphs, the size of a largest clique is equal to the chromatic number. Examples of perfect graphs include bipartite graphs, line graphs of bipartite...
Maria Chudnovsky, Gérard Cornuéjols, Xinming Liu, Paul Seymour, Kristina Vuskovic
A graph is Berge if no induced subgraph of G is an odd cycle of length at least 5 or the complement of one. Let C be a shortest odd hole in G. A vertex v is major for C if its neighbours in C do not...
Perfect Graphs, Partitionable Graphs and Cutsets (2000)
Michele Conforti, Gérard Cornuéjols, Grigor Gasparyan, Kristina Vuskovic
We prove a theorem about cutsets in partitionable graphs that generalizes earlier results on amalgams, 2-amalgams and homogeneous pairs. 1 Introduction A graph G is perfect if, for all induced...
The integer programming models known as set packing and set covering have a wide range of applications, such as pattern recognition, plant location and airline crew scheduling. Sometimes, due to the...
Ideal binary clutters, connectivity, and a conjecture of Seymour (2000)
Gérard Cornuéjols, Bertrand Guenin
ABSTRACT. A binary clutter is the family of odd circuits of a binary matroid, that is, the family of circuits that intersect with odd cardinality a fixed given subset of elements. Let � denote the...
Even and odd holes in cap-free graphs (1999)
Michele Conforti, Gérard Cornuéjols, Ajai Kapoor
Abstract: It is an old problem in graph theory to test whether a graph contains a chordless cycle of length greater than three (hole) with a specific parity (even, odd). Studying the structure of...
A class of hard small 0-1 programs (1998)
Abstract. In this paper, we consider a class of 0–1 programs which, although innocent looking, is a challenge for existing solution methods. Solving even small instances from this class is...
Gérard Cornuéjols, G Erard, François Margot, Cornu Ejols, Bertrand Guenin, ...
. A clutter (V; E) packs if the smallest number of vertices needed to intersect all the edges (i.e. a transversal) is equal to the maximum number of pairwise disjoint edges (i.e. a matching). This...