Gérard Cornuéjols

Search for another author

Author Description

Ask a Question About This Mathematician

An algorithmic framework for convex mixed integer nonlinear programs

2007-12-01

Pierre Bonami , Lorenz T. Biegler , Andrew R. Conn +7 more

View PDF Chat

Integer Programming

2014-01-01

Michele Conforti , Gérard Cornuéjols , Giacomo Zambelli

Nonlinear programming: theory and algorithms

2006-12-21

Gérard Cornuéjols , Reha Tütüncü

A summary is not available for this content so a preview has been provided. Please use the Get access link above for information on how to access this content. A summary is not available for this content so a preview has been provided. Please use the Get access link above for information on how to access this content.

Recognizing Berge Graphs

2005-03-01

Maria Chudnovsky , Gérard Cornuéjols , Xinming Liu +2 more

Valid inequalities for mixed integer linear programs

2007-01-23

Gérard Cornuéjols

View PDF Chat

Extended formulations in combinatorial optimization

2010-03-01

Michele Conforti , Gérard Cornuéjols , Giacomo Zambelli

View PDF Chat

A Feasibility Pump for mixed integer nonlinear programs

2008-03-17

Pierre Bonami , Gérard Cornuéjols , Andrea Lodi +1 more

View PDF Chat

General factors of graphs

1988-10-01

Gérard Cornuéjols

Extended formulations in combinatorial optimization

2013-01-09

Michele Conforti , Gérard Cornuéjols , Giacomo Zambelli

View PDF Chat

Minimal Valid Inequalities for Integer Constraints

2009-07-23

Valentin Borozan , Gérard Cornuéjols

In this paper, we consider a semi-infinite relaxation of mixed-integer linear programs. We show that minimal valid inequalities for this relaxation correspond to maximal lattice-free convex sets, and that they … In this paper, we consider a semi-infinite relaxation of mixed-integer linear programs. We show that minimal valid inequalities for this relaxation correspond to maximal lattice-free convex sets, and that they arise from nonnegative, piecewise linear, positively homogeneous, convex functions.

A matching problem with side conditions

1980-01-01

Gérard Cornuéjols , William R. Pulleyblank

Maximal Lattice-Free Convex Sets in Linear Subspaces

2010-08-01

Amitabh Basu , Michele Conforti , Gérard Cornuéjols +1 more

We consider a model that arises in integer programming and show that all irredundant inequalities are obtained from maximal lattice-free convex sets in an affine subspace. We also show that … We consider a model that arises in integer programming and show that all irredundant inequalities are obtained from maximal lattice-free convex sets in an affine subspace. We also show that these sets are polyhedra. The latter result extends a theorem of Lovász characterizing maximal lattice-free convex sets in ℝ n .

View PDF Chat

Ideal 0, 1 Matrices

1994-01-01

Gérard Cornuéjols , Beth Novick

An extension of matching theory

1986-06-01

Gérard Cornuéjols , David Hartvigsen

On the facets of mixed integer programs with two integer variables and two constraints

2008-05-06

Gérard Cornuéjols , François Margot

View PDF Chat

A Geometric Perspective on Lifting

2011-06-01

Michele Conforti , Gérard Cornuéjols , Giacomo Zambelli

Recently it has been shown that minimal inequalities for a continuous relaxation of mixed-integer linear programs are associated with maximal lattice-free convex sets. In this paper, we show how to … Recently it has been shown that minimal inequalities for a continuous relaxation of mixed-integer linear programs are associated with maximal lattice-free convex sets. In this paper, we show how to lift these inequalities for integral nonbasic variables by considering maximal lattice-free convex sets in a higher dimensional space. We apply this approach to several examples. In particular, we identify cases in which the lifting is unique.

View PDF Chat

Minimal Inequalities for an Infinite Relaxation of Integer Programs

2010-01-01

Amitabh Basu , Michele Conforti , Gérard Cornuéjols +1 more

We show that maximal $S$-free convex sets are polyhedra when $S$ is the set of integral points in some rational polyhedron of $\mathbb{R}^n$. This result extends a theorem of Lov\'asz … We show that maximal $S$-free convex sets are polyhedra when $S$ is the set of integral points in some rational polyhedron of $\mathbb{R}^n$. This result extends a theorem of Lov\'asz characterizing maximal lattice-free convex sets. Our theorem has implications in integer programming. In particular, we show that maximal $S$-free convex sets are in one-to-one correspondence with minimal inequalities.

View PDF Chat

Cut-Generating Functions and <i>S</i>-Free Sets

2014-08-20

Michele Conforti , Gérard Cornuéjols , Aris Daniilidis +2 more

We consider the separation problem for sets X that are pre-images of a given set S by a linear mapping. Classical examples occur in integer programming, as well as in … We consider the separation problem for sets X that are pre-images of a given set S by a linear mapping. Classical examples occur in integer programming, as well as in other optimization problems such as complementarity. One would like to generate valid inequalities that cut off some point not lying in X, without reference to the linear mapping. To this aim, we introduce a concept: cut-generating functions (CGF) and we develop a formal theory for them, largely based on convex analysis. They are intimately related to S-free sets and we study this relation, disclosing several definitions for minimal CGF's and maximal S-free sets. Our work unifies and puts into perspective a number of existing works on S-free sets; in particular, we show how CGF's recover the celebrated Gomory cuts.

View PDF Chat

Mixed-integer nonlinear programs featuring “on/off” constraints

2011-08-05

Hassan Hijazi , Pierre Bonami , Gérard Cornuéjols +1 more

View PDF Chat

Tight bounds for christofides' traveling salesman heuristic

1978-12-01

Gérard Cornuéjols , George L. Nemhauser

On the relative strength of split, triangle and quadrilateral cuts

2009-04-22

Amitabh Basu , Pierre Bonami , Gérard Cornuéjols +1 more

View PDF Chat

Critical graphs, matchings and tours or a hierarchy of relaxations for the travelling salesman problem

1983-03-01

Gérard Cornuéjols , William R. Pulleyblank

Square-free perfect graphs

2003-12-09

Michele Conforti , Gérard Cornuéjols , Kristina Vušković

View PDF Chat

Decomposition of integer programs and of generating sets

1997-01-01

Gérard Cornuéjols , Rafał Urbaniak , Robert Weismantel +1 more

Universally signable graphs

1997-03-01

Michele Conforti , Gérard Cornuéjols , Ajai Kapoor +1 more

Experiments with Two-Row Cuts from Degenerate Tableaux

2011-02-03

Amitabh Basu , Pierre Bonami , Gérard Cornuéjols +1 more

There has been a recent interest in cutting planes generated from two or more rows of the optimal simplex tableau. One can construct examples of integer programs for which a … There has been a recent interest in cutting planes generated from two or more rows of the optimal simplex tableau. One can construct examples of integer programs for which a single cutting plane generated from two rows dominates the entire split closure. Motivated by these theoretical results, we study the effect of adding a family of cutting planes generated from two rows on a set of instances from the MIPLIB library. The conclusion of whether these cuts are competitive with GMI cuts is very sensitive to the experimental setup. In particular, we consider the issue of reliability versus aggressiveness of the cut generators, an issue that is usually not addressed in the literature.

View PDF Chat

Perfect triangle-free 2-matchings

1980-01-01

Gérard Cornuéjols , William R. Pulleyblank

A counterexample to a conjecture of Gomory and Johnson

2010-09-10

Amitabh Basu , Michele Conforti , Gérard Cornuéjols +1 more

View PDF Chat

Polyhedral methods for the maximum clique problem

1996-10-01

Egon Balas , Sebastián Ceria , Gérard Cornuéjols +1 more

Combining and strengthening Gomory cuts

1995-01-01

Sebastián Ceria , Gérard Cornuéjols , Milind Dawande

Decomposition of odd-hole-free graphs by double star cutsets and 2-joins

2004-05-30

Michele Conforti , Gérard Cornuéjols , Kristina Vušković

Odd Hole Recognition in Graphs of Bounded Clique Size

2006-01-01

Michele Conforti , Gérard Cornuéjols , Xinming Liu +2 more

In a graph G, an odd hole is an induced odd cycle of length at least 5. A clique of G is a set of pairwise adjacent vertices. In this … In a graph G, an odd hole is an induced odd cycle of length at least 5. A clique of G is a set of pairwise adjacent vertices. In this paper we consider the class ${\cal C}_k$ of graphs whose cliques have a size bounded by a constant k. Given a graph G in ${\cal C}_k$, we show how to recognize in polynomial time whether G contains an odd hole.

View PDF Chat

Unique Minimal Liftings for Simplicial Polytopes

2012-03-22

Amitabh Basu , Gérard Cornuéjols , Matthias Köppe

For a minimal inequality derived from a maximal lattice-free simplicial polytope in $\R^n$, we investigate the region where minimal liftings are uniquely defined, and we characterize when this region covers … For a minimal inequality derived from a maximal lattice-free simplicial polytope in $\R^n$, we investigate the region where minimal liftings are uniquely defined, and we characterize when this region covers $\R^n$. We then use this characterization to show that a minimal inequality derived from a maximal lattice-free simplex in $\R^n$ with exactly one lattice point in the relative interior of each facet has a unique minimal lifting if and only if all the vertices of the simplex are lattice points.

View PDF Chat

Perfect matchings in balanced hypergraphs

1996-09-01

Michele Conforti , Gérard Cornuéjols , Ajai Kapoor +1 more

Convex Sets and Minimal Sublinear Functions

2010-04-01

Amitabh Basu , Gérard Cornuéjols , Giacomo Zambelli

We show that, given a closed convex set $K$ containing the origin in its interior, the support function of the set $\{y\in K^* \mid \mbox{ there exists } x\in K\mbox{ … We show that, given a closed convex set $K$ containing the origin in its interior, the support function of the set $\{y\in K^* \mid \mbox{ there exists } x\in K\mbox{ such that } \langle x,y \rangle =1\}$ is the pointwise smallest among all sublinear functions $\sigma$ such that $K=\{x \mid \sigma(x)\leq 1\}$.

Incorporating Black-Litterman views in portfolio construction when stock returns are a mixture of normals

2018-11-22

Burak Kocuk , Gérard Cornuéjols

View PDF Chat

Graphs without odd holes, parachutes or proper wheels: a generalization of Meyniel graphs and of line graphs of bipartite graphs

2003-02-17

Michele Conforti , Gérard Cornuéjols

Unique lifting of integer variables in minimal inequalities

2012-06-01

Amitabh Basu , Manoel Campêlo , Michele Conforti +2 more

View PDF Chat

A 3-Slope Theorem for the infinite relaxation in the plane

2012-06-10

Gérard Cornuéjols , Marco Molinaro

Intersection Cuts with Infinite Split Rank

2012-01-10

Amitabh Basu , Gérard Cornuéjols , François Margot

We consider mixed integer linear programs where free integer variables are expressed in terms of nonnegative continuous variables. When this model only has two integer variables, Dey and Louveaux characterized … We consider mixed integer linear programs where free integer variables are expressed in terms of nonnegative continuous variables. When this model only has two integer variables, Dey and Louveaux characterized the intersection cuts that have infinite split rank. We show that, for any number of integer variables, the split rank of an intersection cut generated from a bounded convex set $P$ is finite if and only if the integer points on the boundary of $P$ satisfy a certain "2-hyperplane property". The Dey-Louveaux characterization is a consequence of this more general result.

View PDF Chat

Disjunctive cuts for cross-sections of the second-order cone

2015-06-13

Sercan Yıldız , Gérard Cornuéjols

View PDF Chat

Triangle-free graphs that are signable without even holes

2000-07-01

Michele Conforti , Gérard Cornuéjols , Ajai Kapoor +1 more

We characterize triangle-free graphs for which there exists a subset of edges that intersects every chordless cycle in an odd number of edges (TF odd-signable graphs). These graphs arise as … We characterize triangle-free graphs for which there exists a subset of edges that intersects every chordless cycle in an odd number of edges (TF odd-signable graphs). These graphs arise as building blocks of a decomposition theorem (for cap-free odd-signable graphs) obtained by the same authors. We give a polytime algorithm to test membership in this class. This algorithm is itself based on a decomposition theorem. © 2000 John Wiley & Sons, Inc. J Graph Theory 34: 204–220, 2000

Mixed Integer NonLinear Programs featuring “On/Off” constraints: convex analysis and applications

2010-07-20

Hassan Hijazi , Pierre Bonami , Gérard Cornuéjols +1 more

View PDF Chat

Cutting planes from two-term disjunctions

2013-05-29

Pierre Bonami , Michele Conforti , Gérard Cornuéjols +2 more

View PDF Chat

Ideal Binary Clutters, Connectivity, and a Conjecture of Seymour

2002-01-01

Gérard Cornuéjols , Bertrand Guenin

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. … 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 A denote the 0,1 matrix whose rows are the characteristic vectors of the odd circuits. A binary clutter is ideal if the polyhedron $\{ x \geq {\bf 0}: \; Ax \geq {\bf 1} \}$ is integral. Examples of ideal binary clutters are st-paths, st-cuts, T-joins or T-cuts in graphs, and odd circuits in weakly bipartite graphs. In 1977, Seymour [J. Combin. Theory Ser. B, 22 (1977), pp. 289--295] conjectured that a binary clutter is ideal if and only if it does not contain ${\cal{L}}_{F_7}$, ${\cal{O}}_{K_5}$, or $b({\cal{O}}_{K_5})$ as a minor. In this paper, we show that a binary clutter is ideal if it does not contain five specified minors, namely the three above minors plus two others. This generalizes Guenin's characterization of weakly bipartite graphs [J. Combin. Theory Ser., 83 (2001), pp. 112--168], as well as the theorem of Edmonds and Johnson [ Math. Programming, 5 (1973), pp. 88--124] on T-joins and T-cuts.

Cut-Generating Functions for Integer Variables

2016-09-23

Sercan Yıldız , Gérard Cornuéjols

For an integer linear program, Gomory’s corner relaxation is obtained by ignoring the nonnegativity of the basic variables in a tableau formulation. In this paper, we do not relax these … For an integer linear program, Gomory’s corner relaxation is obtained by ignoring the nonnegativity of the basic variables in a tableau formulation. In this paper, we do not relax these nonnegativity constraints. We generalize a classical result of Gomory and Johnson characterizing minimal cut-generating functions in terms of subadditivity, symmetry, and periodicity. Our result is based on the notion of generalized symmetry condition. We also prove a 2-slope theorem for extreme cut-generating functions in our setting, in the spirit of the 2-slope theorem of Gomory and Johnson.

Complete Multi-partite Cutsets in Minimal Imperfect Graphs

1993-11-01

Gérard Cornuéjols , Bruce Reed

Optimality certificates for convex minimization and Helly numbers

2017-10-23

Amitabh Basu , Michele Conforti , Gérard Cornuéjols +2 more

View PDF Chat

Perfect Graphs, Partitionable Graphs and Cutsets

2002-01-01

Michele Conforti , Gérard Cornuéjols , Grigor Gasparyan +1 more

Balanced 0, ±1 Matrices II. Recognition Algorithm

2001-03-01

Michele Conforti , Gérard Cornuéjols , Ajai Kapoor +1 more

Packing Dijoins in Weighted Chordal Digraphs

2025-01-18

Gérard Cornuéjols , Siyue Liu , R. Ravi

In a digraph, a dicut is a cut where all the arcs cross in one direction. A dijoin is a subset of arcs that intersects every dicut. Edmonds and Giles … In a digraph, a dicut is a cut where all the arcs cross in one direction. A dijoin is a subset of arcs that intersects every dicut. Edmonds and Giles conjectured that in a weighted digraph, the minimum weight of a dicut is equal to the maximum size of a packing of dijoins. This has been disproved. However, the unweighted version conjectured by Woodall remains open. We prove that the Edmonds-Giles conjecture is true if the underlying undirected graph is chordal. We also give a strongly polynomial time algorithm to construct such a packing.

View PDF Chat

Strongly connected orientations and integer lattices

2024-10-17

Ahmad Abdi , Gérard Cornuéjols , Siyue Liu +1 more

Let $D=(V,A)$ be a digraph whose underlying graph is $2$-edge-connected. Let $P$ be the polytope whose vertices are the incidence vectors of arc sets whose reversal makes $D$ strongly connected. … Let $D=(V,A)$ be a digraph whose underlying graph is $2$-edge-connected. Let $P$ be the polytope whose vertices are the incidence vectors of arc sets whose reversal makes $D$ strongly connected. $P$ can be described by $0,1$ bounds, and 'cut inequalities' which enforce that every nonempty proper vertex subset has at least one incoming arc after a re-orientation. Let $F$ be any face obtained by setting some cut inequalities to equality. We prove under a mild necessary condition that the integer points in $F$ contain an 'integral basis' $B$, i.e., $B$ is linearly independent, and any integral vector in the linear hull of $F$ is an integral linear combination of $B$. This result is surprising as the integer points in $F$ do not necessarily form a Hilbert basis. Our result is obtained by developing a theory similar to Matching Theory for degree-constrained dijoins in bipartite digraphs. Our result has several consequences, including to a famous conjecture by Woodall from the 1970s which states that the minimum size of a 'dicut' of $D$, say $\tau$, is equal to the maximum number of disjoint 'dijoins'. Our result proves a relaxation of this conjecture, by finding for any prime number $p\geq 2$, a $p$-adic packing of dijoins of value $\tau$ and of support size at most $2|A|$.

View PDF Chat

Approximately Packing Dijoins via Nowhere-Zero Flows

2024-01-01

Gérard Cornuéjols , Siyue Liu , R. Ravi

View PDF Chat

On Packing Dijoins in Digraphs and Weighted Digraphs

2023-10-19

Ahmad Abdi , Gérard Cornuéjols , Michael Zlatin

.Let $D=(V,A)$ be a digraph. A dicut is a cut $\delta^+(U)\subseteq A$ for some nonempty proper vertex subset $U$ such that $\delta^-(U)=\emptyset$, a dijoin is an arc subset that intersects … .Let $D=(V,A)$ be a digraph. A dicut is a cut $\delta^+(U)\subseteq A$ for some nonempty proper vertex subset $U$ such that $\delta^-(U)=\emptyset$, a dijoin is an arc subset that intersects every dicut at least once, and more generally a $k$-dijoin is an arc subset that intersects every dicut at least $k$ times. Our first result is that $A$ can be partitioned into a dijoin and a $(\tau -1)$-dijoin where $\tau$ denotes the smallest size of a dicut. Woodall conjectured the stronger statement that $A$ can be partitioned into $\tau$ dijoins. Let $w\in \mathbb{Z}^A_{\geq 0}$, and suppose every dicut has weight at least $\tau$, for some integer $\tau \geq 2$. Let $\rho (\tau,D,w):=\frac{1}{\tau }\sum_{v\in V} m_v$, where each $m_v$ is the integer in $\{0,1,\ldots,\tau -1\}$ equal to $w(\delta^+(v))-w(\delta^-(v))$ mod $\tau$. We prove the following results:i.If $\rho (\tau,D,w)\in \{0,1\}$, then there is an equitable $w$-weighted packing of dijoins of size $\tau$.ii.If $\rho (\tau,D,w)=2$, then there is a $w$-weighted packing of dijoins of size $\tau$.iii.If $\rho (\tau,D,w)=3$, $\tau=3$, and $w=\mathbf{1}$, then $A$ can be partitioned into three dijoins.Each result is best possible: (i) does not hold for $\rho (\tau,D,w)=2$ even if $w=\mathbf{1}$, (ii) does not hold for $\rho (\tau,D,w)=3$, and (iii) does not hold for general $w$.Keywordsmin-max theoremdijoinsstrongly base orderable matroidpacking common basessubmodular functioninteger decomposition propertyMSC codes05C2090C27

View PDF Chat

Total dual dyadicness and dyadic generating sets

2023-05-22

Ahmad Abdi , Gérard Cornuéjols , Bertrand Guenin +1 more

View PDF Chat

Dyadic linear programming and extensions

2023-01-01

Ahmad Abdi , Gérard Cornuéjols , Bertrand Guenin +1 more

A rational number is dyadic if it has a finite binary representation $p/2^k$, where $p$ is an integer and $k$ is a nonnegative integer. Dyadic rationals are important for numerical … A rational number is dyadic if it has a finite binary representation $p/2^k$, where $p$ is an integer and $k$ is a nonnegative integer. Dyadic rationals are important for numerical computations because they have an exact representation in floating-point arithmetic on a computer. A vector is dyadic if all its entries are dyadic rationals. We study the problem of finding a dyadic optimal solution to a linear program, if one exists. We show how to solve dyadic linear programs in polynomial time. We give bounds on the size of the support of a solution as well as on the size of the denominators. We identify properties that make the solution of dyadic linear programs possible: closure under addition and negation, and density, and we extend the algorithmic framework beyond the dyadic case.

View PDF Chat

Arc connectivity and submodular flows in digraphs

2023-01-01

Ahmad Abdi , Gérard Cornuéjols , Giacomo Zambelli

Let $D=(V,A)$ be a digraph. For an integer $k\geq 1$, a $k$-arc-connected flip is an arc subset of $D$ such that after reversing the arcs in it the digraph becomes … Let $D=(V,A)$ be a digraph. For an integer $k\geq 1$, a $k$-arc-connected flip is an arc subset of $D$ such that after reversing the arcs in it the digraph becomes (strongly) $k$-arc-connected. The first main result of this paper introduces a sufficient condition for the existence of a $k$-arc-connected flip that is also a submodular flow for a crossing submodular function. More specifically, given some integer $\tau\geq 1$, suppose $d_A^+(U)+(\frac{\tau}{k}-1)d_A^-(U)\geq \tau$ for all $U\subsetneq V, U\neq \emptyset$, where $d_A^+(U)$ and $d_A^-(U)$ denote the number of arcs in $A$ leaving and entering $U$, respectively. Let $\mathcal{C}$ be a crossing family over ground set $V$, and let $f:\mathcal{C}\to \mathbb{Z}$ be a crossing submodular function such that $f(U)\geq \frac{k}{\tau}(d_A^+(U)-d_A^-(U))$ for all $U\in \mathcal{C}$. Then $D$ has a $k$-arc-connected flip $J$ such that $f(U)\geq d_J^+(U)-d_J^-(U)$ for all $U\in \mathcal{C}$. The result has several applications to Graph Orientations and Combinatorial Optimization. In particular, it strengthens Nash-Williams' so-called weak orientation theorem, and proves a weaker variant of Woodall's conjecture on digraphs whose underlying undirected graph is $\tau$-edge-connected. The second main result of this paper is even more general. It introduces a sufficient condition for the existence of capacitated integral solutions to the intersection of two submodular flow systems. This sufficient condition implies the classic result of Edmonds and Giles on the box-total dual integrality of a submodular flow system. It also has the consequence that in a weakly connected digraph, the intersection of two submodular flow systems is totally dual integral.

Branch-and-Bound versus Lift-and-Project Relaxations in Combinatorial Optimization

2023-01-01

Gérard Cornuéjols , Yatharth Dubey

In this paper, we consider a theoretical framework for comparing branch-and-bound with classical lift-and-project hierarchies. We simplify our analysis of streamlining the definition of branch-and-bound. We introduce "skewed $k$-trees" which … In this paper, we consider a theoretical framework for comparing branch-and-bound with classical lift-and-project hierarchies. We simplify our analysis of streamlining the definition of branch-and-bound. We introduce "skewed $k$-trees" which give a hierarchy of relaxations that is incomparable to that of Sherali-Adams, and we show that it is much better for some instances. We also give an example where lift-and-project does very well and branch-and-bound does not. Finally, we study the set of branch-and-bound trees of height at most $k$ and effectively "squeeze" their effectiveness between two well-known lift-and-project procedures.

View PDF Chat

Approximately Packing Dijoins via Nowhere-Zero Flows

2023-01-01

Gérard Cornuéjols , Siyue Liu , R. Ravi

In a digraph, a dicut is a cut where all the arcs cross in one direction. A dijoin is a subset of arcs that intersects each dicut. Woodall conjectured in … In a digraph, a dicut is a cut where all the arcs cross in one direction. A dijoin is a subset of arcs that intersects each dicut. Woodall conjectured in 1976 that in every digraph, the minimum size of a dicut is equal to the maximum number of disjoint dijoins. However, prior to our work, it was not even known whether at least $3$ disjoint dijoins exist in a digraph whose minimum dicut size is arbitrarily large. By building connections with nowhere-zero (circular) $k$-flows, we prove that every digraph with minimum dicut size $\tau$ contains $\frac{\tau}{k}$ disjoint dijoins if the underlying undirected graph admits a nowhere-zero (circular) $k$-flow. The existence of nowhere-zero $6$-flows in $2$-edge-connected graphs (Seymour 1981) directly leads to the existence of $\frac{\tau}{6}$ disjoint dijoins in any digraph with minimum dicut size $\tau$, which can be found in polynomial time as well. The existence of nowhere-zero circular $(2+\frac{1}{p})$-flows in $6p$-edge-connected graphs (Lov\'asz et al 2013) directly leads to the existence of $\frac{\tau p}{2p+1}$ disjoint dijoins in any digraph with minimum dicut size $\tau$ whose underlying undirected graph is $6p$-edge-connected.

Testing idealness in the filter oracle model

2022-11-01

Ahmad Abdi , Gérard Cornuéjols , Bertrand Guenin +1 more

A filter oracle for a clutter consists of a finite set V and an oracle which, given any set X⊆V, decides in unit time whether X contains a member of … A filter oracle for a clutter consists of a finite set V and an oracle which, given any set X⊆V, decides in unit time whether X contains a member of the clutter. Let A2n be an algorithm that, given any clutter C over 2n elements via a filter oracle, decides whether C is ideal. We prove that in the worst case, A2n makes at least 2n−1 calls to the filter oracle. Our proof uses the theory of cuboids.

View PDF Chat

On Dyadic Fractional Packings of $T$-Joins

2022-09-01

Ahmad Abdi , Gérard Cornuéjols , Zuzanna Palion

Let $G=(V,E)$ be a graph, and $T\subseteq V$ a nonempty subset of even cardinality. The famous theorem of Edmonds and Johnson on the $T$-join polyhedron implies that the minimum cardinality … Let $G=(V,E)$ be a graph, and $T\subseteq V$ a nonempty subset of even cardinality. The famous theorem of Edmonds and Johnson on the $T$-join polyhedron implies that the minimum cardinality of a $T$-cut is equal to the maximum value of a fractional packing of $T$-joins. In this paper, we prove that the fractions assigned may be picked as dyadic rationals, i.e., of the form $\frac{a}{2^k}$ for some integers $a,k\geq 0$.

View PDF Chat

Total Dual Dyadicness and Dyadic Generating Sets

2022-01-01

Ahmad Abdi , Gérard Cornuéjols , Bertrand Guenin +1 more

View PDF Chat

On packing dijoins in digraphs and weighted digraphs

2022-01-01

Ahmad Abdi , Gérard Cornuéjols , Michael Zlatin

Let $D=(V,A)$ be a digraph. A dicut is a cut $\delta^+(U)\subseteq A$ for some nonempty proper vertex subset $U$ such that $\delta^-(U)=\emptyset$, a dijoin is an arc subset that intersects … Let $D=(V,A)$ be a digraph. A dicut is a cut $\delta^+(U)\subseteq A$ for some nonempty proper vertex subset $U$ such that $\delta^-(U)=\emptyset$, a dijoin is an arc subset that intersects every dicut at least once, and more generally a $k$-dijoin is an arc subset that intersects every dicut at least $k$ times. Our first result is that $A$ can be partitioned into a dijoin and a $(\tau-1)$-dijoin where $\tau$ denotes the smallest size of a dicut. Woodall conjectured the stronger statement that $A$ can be partitioned into $\tau$ dijoins. Let $w\in \mathbb{Z}^A_{\geq 0}$ and suppose every dicut has weight at least $\tau$, for some integer $\tau\geq 2$. Let $\rho(\tau,D,w):=\frac{1}{\tau}\sum_{v\in V} m_v$, where each $m_v$ is the integer in $\{0,1,\ldots,\tau-1\}$ equal to $w(\delta^+(v))-w(\delta^-(v))$ mod $\tau$. We prove the following results: (i) If $\rho(\tau,D,w)\in \{0,1\}$, then there is an equitable $w$-weighted packing of dijoins of size $\tau$. (ii) If $\rho(\tau,D,w)= 2$, then there is a $w$-weighted packing of dijoins of size $\tau$. (iii) If $\rho(\tau,D,w)=3$, $\tau=3$, and $w={\bf 1}$, then $A$ can be partitioned into three dijoins. Each result is best possible: (i) does not hold for $\rho(\tau,D,w)=2$ even if $w=\1$, (ii) does not hold for $\rho(\tau,D,w)=3$, and (iii) do not hold for general $w$.

View PDF Chat

Testing idealness in the filter oracle model

2022-01-01

Ahmad Abdi , Gérard Cornuéjols , Bertrand Guenin +1 more

A filter oracle for a clutter consists of a finite set $V$ along with an oracle which, given any set $X\subseteq V$, decides in unit time whether or not $X$ … A filter oracle for a clutter consists of a finite set $V$ along with an oracle which, given any set $X\subseteq V$, decides in unit time whether or not $X$ contains a member of the clutter. Let $\mathfrak{A}_{2n}$ be an algorithm that, given any clutter $\mathcal{C}$ over $2n$ elements via a filter oracle, decides whether or not $\mathcal{C}$ is ideal. We prove that in the worst case, $\mathfrak{A}_{2n}$ must make at least $2^n$ calls to the filter oracle. Our proof uses the theory of cuboids.

View PDF Chat

Clean tangled clutters, simplices, and projective geometries

2021-12-28

Ahmad Abdi , Gérard Cornuéjols , Matt Superdock

View PDF Chat

Total dual dyadicness and dyadic generating sets

2021-01-01

Ahmad Abdi , Gérard Cornuéjols , Bertrand Guenin +1 more

A vector is \emph{dyadic} if each of its entries is a dyadic rational number, i.e. of the form $\frac{a}{2^k}$ for some integers $a,k$ with $k\geq 0$. A linear system $Ax\leq … A vector is \emph{dyadic} if each of its entries is a dyadic rational number, i.e. of the form $\frac{a}{2^k}$ for some integers $a,k$ with $k\geq 0$. A linear system $Ax\leq b$ with integral data is \emph{totally dual dyadic} if whenever $\min\{b^\top y:A^\top y=w,y\geq {\bf 0}\}$ for $w$ integral, has an optimal solution, it has a dyadic optimal solution. In this paper, we study total dual dyadicness, and give a co-NP characterization of it in terms of \emph{dyadic generating sets for cones and subspaces}, the former being the dyadic analogue of \emph{Hilbert bases}, and the latter a polynomial-time recognizable relaxation of the former. Along the way, we see some surprising turn of events when compared to total dual integrality, primarily led by the \emph{density} of the dyadic rationals. Our study ultimately leads to a better understanding of total dual integrality and polyhedral integrality. We see examples from dyadic matrices, $T$-joins, cycles, and perfect matchings of a graph.

View PDF Chat

Idealness of k-wise intersecting families

2020-11-11

Ahmad Abdi , Gérard Cornuéjols , Tony Huynh +1 more

A clutter is k-wise intersecting if every k members have a common element, yet no element belongs to all members. We conjecture that, for some integer k≥4 , every k-wise … A clutter is k-wise intersecting if every k members have a common element, yet no element belongs to all members. We conjecture that, for some integer k≥4 , every k-wise intersecting clutter is non-ideal. As evidence for our conjecture, we prove it for k=4 for the class of binary clutters. Two key ingredients for our proof are Jaeger's 8-flow theorem for graphs, and Seymour's characterization of the binary matroids with the sums of circuits property. As further evidence for our conjecture, we also note that it follows from an unpublished conjecture of Seymour from 1975. We also discuss connections to the chromatic number of a clutter, projective geometries over the two-element field, uniform cycle covers in graphs, and quarter-integral packings of value two in ideal clutters.

View PDF Chat

Resistant Sets in the Unit Hypercube

2020-10-14

Ahmad Abdi , Gérard Cornuéjols , Dabeen Lee

Ideal matrices and clutters are prevalent in combinatorial optimization, ranging from balanced matrices, clutters of T-joins, to clutters of rooted arborescences. Most of the known examples of ideal clutters are … Ideal matrices and clutters are prevalent in combinatorial optimization, ranging from balanced matrices, clutters of T-joins, to clutters of rooted arborescences. Most of the known examples of ideal clutters are combinatorial in nature. In this paper, rendered by the recently developed theory of cuboids, we provide a different class of ideal clutters, one that is geometric in nature. The advantage of this new class of ideal clutters is that it allows for infinitely many ideal minimally nonpacking clutters. We characterize the densest ideal minimally nonpacking clutters of the class. Using the tools developed, we then verify the replication conjecture for the class.

View PDF Chat

Idealness of k-wise Intersecting Families

2020-01-01

Ahmad Abdi , Gérard Cornuéjols , Tony Huynh +1 more

View PDF Chat

Projective geometries, simplices and clutters

2019-08-28

Ahmad Abdi , Gérard Cornuéjols , Dabeen Lee +1 more

A clutter is {\it clean} if it has no delta or the blocker of an extended odd hole minor. There are combinatorial and geometric classes of clean clutters, namely ideal … A clutter is {\it clean} if it has no delta or the blocker of an extended odd hole minor. There are combinatorial and geometric classes of clean clutters, namely ideal clutters, clutters without an intersecting minor, and binary clutters. Tight connections between clean clutters and the first two classes have recently been established. In this paper, we establish a deep connection between clean clutters and binary clutters. Let $\mathcal{C}$ be a clean clutter with covering number 2 where every element is in a minimum cover. It was recently proved that $\mathcal{C}$ has a fractional packing of value two. Collecting the supports of all such fractional packings, we obtain the {\it core} of $\mathcal{C}$. We see that the core is a duplication of the cuboid of a set of 0-1 points, called the {\it setcore} of $\mathcal{C}$. We see that the convex hull of the setcore is a full-dimensional polytope containing the center of the hypercube in its interior. We define two parameters on $\mathcal{C}$, one is the optimum of a combinatorial minimization problem called the {\it girth}, while the other is the optimum of a geometric maximization problem called the {\it depth}. We prove a duality theorem between the two parameters, exposing a fascinating interplay between the combinatorics and the geometry of such clutters. Further stressing the interplay, we see that the convex hull of the setcore is a simplex if and only if the setcore is the cocycle space of a projective geometry over GF(2). We see that if the convex hull of the setcore is a simplex of dimension more than 3, then $\mathcal{C}$ has the Fano plane as a minor. We also see an infinite class of ideal minimally non-packing clutters with covering number two whose setcore corresponds to a simplex of dimension 3. Our results lend weight to two unpublished conjectures of Seymour (1975) about dyadic fractional packings in ideal clutters.

Idealness and 2-resistant sets

2019-07-03

Ahmad Abdi , Gérard Cornuéjols

View PDF Chat

Idealness of $k$-wise intersecting families

2019-01-01

Ahmad Abdi , Gérard Cornuéjols , Tony Huynh +1 more

A clutter is \emph{$k$-wise intersecting} if every $k$ members have a common element, yet no element belongs to all members. We conjecture that, for some integer $k\geq 4$, every $k$-wise … A clutter is \emph{$k$-wise intersecting} if every $k$ members have a common element, yet no element belongs to all members. We conjecture that, for some integer $k\geq 4$, every $k$-wise intersecting clutter is non-ideal. As evidence for our conjecture, we prove it for $k=4$ for the class of binary clutters. Two key ingredients for our proof are Jaeger's $8$-flow theorem for graphs, and Seymour's characterization of the binary matroids with the sums of circuits property. As further evidence for our conjecture, we also note that it follows from an unpublished conjecture of Seymour from 1975. We also discuss connections to the chromatic number of a clutter, projective geometries over the two-element field, uniform cycle covers in graphs, and quarter-integral packings of value two in ideal clutters.

View PDF Chat

Clean tangled clutters, simplices, and projective geometries

2019-01-01

Ahmad Abdi , Gérard Cornuéjols , Matt Superdock

A clutter is \emph{clean} if it has no delta or the blocker of an extended odd hole minor, and it is \emph{tangled} if its covering number is two and every … A clutter is \emph{clean} if it has no delta or the blocker of an extended odd hole minor, and it is \emph{tangled} if its covering number is two and every element appears in a minimum cover. Clean tangled clutters have been instrumental in progress towards several open problems on ideal clutters, including the $\tau=2$ Conjecture. Let $\mathcal{C}$ be a clean tangled clutter. It was recently proved that $\mathcal{C}$ has a fractional packing of value two. Collecting the supports of all such fractional packings, we obtain what is called the {\it core} of $\mathcal{C}$. The core is a duplication of the cuboid of a set of $0-1$ points, called the {\it setcore} of $\mathcal{C}$. In this paper, we prove three results about the setcore. First, the convex hull of the setcore is a full-dimensional polytope containing the center point of the hypercube in its interior. Secondly, this polytope is a simplex if, and only if, the setcore is the cocycle space of a projective geometry over the two-element field. Finally, if this polytope is a simplex of dimension more than three, then $\mathcal{C}$ has the clutter of the lines of the Fano plane as a minor. Our results expose a fascinating interplay between the combinatorics and the geometry of clean tangled clutters.

Incorporating Black-Litterman views in portfolio construction when stock returns are a mixture of normals

2018-11-22

Burak Kocuk , Gérard Cornuéjols

View PDF Chat

On the Rational Polytopes with Chvátal Rank 1

2018-08-21

Gérard Cornuéjols , Dabeen Lee , Yanjun Li

Multi-Period Models: Simple Examples

2018-07-27

Gérard Cornuéjols , Javier Peña , Reha Tütüncü

Linear Programming: Theory and Algorithms

2018-07-27

Gérard Cornuéjols , Javier Peña , Reha Tütüncü

Quadratic Programming: Theory and Algorithms

2018-07-27

Gérard Cornuéjols , Javier Peña , Reha Tütüncü

Sensitivity of Mean–Variance Models to Input Estimation

2018-07-27

Gérard Cornuéjols , Javier Peña , Reha Tütüncü

When the Gomory–Chvátal closure coincides with the integer hull

2018-02-08

Gérard Cornuéjols , Yanjun Li

View PDF Chat

On some polytopes contained in the 0, 1 hypercube that have a small Chvátal rank

2018-01-19

Gérard Cornuéjols , Dabeen Lee

Optimality certificates for convex minimization and Helly numbers

2017-10-23

Amitabh Basu , Michele Conforti , Gérard Cornuéjols +2 more

View PDF Chat

From estimation to optimization via shrinkage

2017-10-23

Danial Davarnia , Gérard Cornuéjols

View PDF Chat

Modeling Stock Returns as Mixtures of Normals and Incorporating Black-Litterman Views in Portfolio Optimization

2017-06-10

Burak Kocuk , Gérard Cornuéjols

Convex Sets and Minimal Sublinear Functions

2017-01-01

Amitabh Basu , Gérard Cornuéjols , Giacomo Zambelli

We show that, given a closed convex set $K$ containing the origin in its interior, the support function of the set $\{y\in K^*: \exists x\in K\mbox{ such that } \langle … We show that, given a closed convex set $K$ containing the origin in its interior, the support function of the set $\{y\in K^*: \exists x\in K\mbox{ such that } \langle x,y \rangle =1\}$ is the pointwise smallest among all sublinear functions $\sigma$ such that $K=\{x: \sigma(x)\leq 1\}$.

Cut-Generating Functions for Integer Variables

2016-09-23

Sercan Yıldız , Gérard Cornuéjols

Optimality certificates for convex minimization and Helly numbers

2016-01-01

Amitabh Basu , Michele Conforti , Gérard Cornuéjols +2 more

We consider the problem of minimizing a convex function over a subset of R^n that is not necessarily convex (minimization of a convex function over the integer points in a … We consider the problem of minimizing a convex function over a subset of R^n that is not necessarily convex (minimization of a convex function over the integer points in a polytope is a special case). We define a family of duals for this problem and show that, under some natural conditions, strong duality holds for a dual problem in this family that is more restrictive than previously considered duals.

View PDF Chat

Disjunctive cuts for cross-sections of the second-order cone

2015-06-13

Sercan Yıldız , Gérard Cornuéjols

View PDF Chat

Cut-Generating Functions and <i>S</i>-Free Sets

2014-08-20

Michele Conforti , Gérard Cornuéjols , Aris Daniilidis +2 more

View PDF Chat

On the relative strength of families of intersection cuts arising from pairs of tableau constraints in mixed integer programs

2014-04-10

Yogesh P. Awate , Gérard Cornuéjols , Bertrand Guenin +1 more

View PDF Chat

Extended formulations in combinatorial optimization

2013-01-09

Michele Conforti , Gérard Cornuéjols , Giacomo Zambelli

View PDF Chat

Cut-Generating Functions

2013-01-01

Michele Conforti , Gérard Cornuéjols , Aris Daniilidis +2 more

View PDF Chat

Lifting Gomory cuts with bounded variables

2012-12-23

Gérard Cornuéjols , Tamás Kis , Marco Molinaro

View PDF Chat

A 3-Slope Theorem for the infinite relaxation in the plane

2012-06-10

Gérard Cornuéjols , Marco Molinaro

Unique lifting of integer variables in minimal inequalities

2012-06-01

Amitabh Basu , Manoel Campêlo , Michele Conforti +2 more

View PDF Chat

Coauthor	Papers Together
Michele Conforti	34
Giacomo Zambelli	16
Ahmad Abdi	13
Kristina Vušković	13
Amitabh Basu	12
Bertrand Guenin	10
Reha Tütüncü	9
Pierre Bonami	9
Levent Tunçel	8
Ajai Kapoor	7
François Margot	7
Dabeen Lee	7
Ahmad Abdi	6
Javier Peña	4
R. Ravi	3
Robert Weismantel	3
Adam Ouorou	3
Matt Superdock	3
Siyue Liu	3
Hassan Hijazi	3
Tony Huynh	3
William R. Pulleyblank	3
Xinming Liu	3
Marco Molinaro	3
Manoel Campêlo	2
Jérôme Malick	2
Burak Kocuk	2
Klaus Truemper	2
Stefan Weltge	2
Michael Zlatin	2
Aris Daniilidis	2
Sercan Yıldız	2
Andrea Lodi	2
Yanjun Li	2
Sebastián Ceria	2
Claude Lemaréchal	2
Valentin Borozan	1
George L. Nemhauser	1
Carla De Francesco	1
Rafał Urbaniak	1
Milind Dawande	1
Laurence A. Wolsey	1
Beth Novick	1
Egon Balas	1
Andreas Wächter	1
Gábor Pataki	1
Paul Seymour	1
Jon Lee	1
Carl D. Laird	1
Danial Davarnia	1