Optimization models play an increasingly important role in financial decisions. Many computational finance problems ranging from asset allocation to risk management, from option pricing to model...
Balanced 0, ±1-matrices, Part I: Decomposition (2007)
Michele Conforti, Gerard Cornuejols, Ajai Kapoor, Kristina Vuskovic
A 0, ±1 matrix is balanced if, in every square submatrix with two nonzero entries per row and column, the sum of the entries is a multiple of four. This paper extends the decomposition of balanced...
Balanced 0, + or - Matrices. Part 2. Recognition Algorithm (2006)
Conforti, Michele, Cornuejols, Gerard, Kapoor, Ajai, Vuskovi, Krisina
In this paper we give a polynomial time recognition algorithm for balanced 0, + or - matrices. This algorithm is based on a decomposition theorem proved in a companion paper.
Conforti, Michele, Cornuejols, Gerard, Francesco, Carla De
Perfect graphs and perfect 0,1 matrices are well studied in the literature. Here we introduce perfect 0 plus or minus 1 matrices. Our main result is a characterization of these matrices in terms of a...
Mixed 0-1 Programming by Lift-and-Project in a Branch-and-Cut Framework (2005)
Balas, Egon, Ceria, Sebastian, Cornuejols, Gerard
We investigate the computational issues that need to be addressed when incorporating general cutting planes for mixed 0-1 programs into a branch- and-cut framework. The cuts we use are of the...
Balanced 0, + or - Matrices. Part 1. Decomposition, (2005)
Conforti, Michele, Cornuejols, Gerard, Kapuur, Ajai, Vuskovic, Kristina
A 0, + or - matrix is balanced if, in every square submatrix with two nonzero entries per row and column, the sum of the entries is a multiple of four. This paper extends the decomposition of...
General Factors in Graphs. (2002)
Consider a graph G=(N,E) and, for each node i is a member of N, let B sub I be a subset of (0,1,...,d sub G(i)) where d sub G(i) denotes the degree of node i in G. The general factor problem asks...
Probabilistic Analysis of a Relaxation for the k-Median Problem. Revision. (2002)
Ahn,Sang, Cooper,Colin, Cornuejols,Gerard, Frieze,Alan
This paper provides a probabilistic analysis of the so-called 'strong' linear programming relaxation of the k-median problem. The analysis is performed under four classical models in location theory,...
Elementary closures for integer programs (2001)
In integer programming, the elementary closure associated with a family of cuts is the convex set de ned by theintersection of all the cuts in the family. In this paper, we compare the elementary...
Gerard Cornuejols, Bertrand Guenin, Francois Margot
Abstract. A clutter (V � E) packs if the smallest number of vertices needed to intersect all the edges (i.e. a minumum transversal) is equal to the maximum number of pairwise disjoint edges (i.e. a...
Decomposition of balanced matrices (1999)
Michele Conforti, Gerard Cornuejols
A0 � 1 matrix is balanced if it does not contain a square submatrix of odd order with two ones per row and per column. We show that a balanced 0,1 matrix is either totally unimodular or its...
Brezovec, Carl, Cornuejols, Gerard, Glover, Fred
This document addresses the problem of finding a minimum weight base B of a matroid when, in addition, each element of the matroid is colored with one of m colors and there are upper and lower bound...
Brezovec, Carl, Cornuejols, Gerard, Glover, Fred
The problem of finding a minimum weight base B of a matroid is addressed when, in addition, each element of the matroid is colored with one of m colors and there are upper and lower bound...
Mathematical Programming and Logical Inference. (1998)
Balas, Egon, Cornuejols, Gerard, Hooker, John
The object of this research is to develop new and effective methods for logical inference that are based on mathematical programming. We investigated fast packing and covering algorithms as well as...
Decomposition of Balanced Matrices. Part 4. Connected Squares. (1998)
Conforti, Michele, Cornuejols, Gerard, Rao, M. R.
There exist two complete bipartite graphs K1, K2 in G having disjoint node sets, with the property that the removal of the edges in K1, K2 disconnects G. There exists a subset S of the nodes of G...
Decomposition of Balanced Matrices. Part 1. Introduction. (1998)
Conforti, Michele, Cornuejols, Gerard, Rao, M. R.
This study concerns 0,1 matrices that do not contain a square submatrix of odd order with two ones per row and per column. Such matrices and called balanced. They were first introduced by Berge and...
Decomposition of Balanced Matrices. Part 2. Wheel-and-Parachute-Free Graphs. (1998)
Conforti, Michele, Cornuejols, Gerard, Rao, M. R.
See also Part 4, AD-A247 308. Sponsored in part by Grant NSF-DDM-9001705.
Decomposition of Balanced Matrices. Part 6. Even Wheels. (1998)
Conforti, Michele, Cornuejols, Gerard, Rao, M. R.
In this part, we prove that if a balanced bipartite graph G contains an even wheel as an induced subgraph, then it has an extended star cutset. The proof is divided into two parts, treated in...
Decomposition of Balanced Matrices. Part 7. A Polynomial Recognition Algorithm. (1998)
Conforti, Michele, Cornuejols, Gerard, Rao, M. R.
In this seven part paper, we prove the following theorem: At least one of the following alternatives occurs for a bipartite graph G: (1) The graph G has no cycle of length 4k+2; (2) The graph G has a...
Decomposition of Balanced Matrices. Part 5: Goggles. (1998)
Conforti, Michele, Cornuejols, Gerard, Rao, M. R.
In this seven part paper, we prove the following theorem: At least one of the following alternatives occurs for a bipartite graph G: - The graph G has no cycle of length 4k+2. - The graph G has a...
A Lift-and-Project Cutting Plane Algorithm for Mixed 0-1 Programs. (1998)
Balas, Egon, Ceria, Sebastian, Cornuejols, Gerard
We propose a cutting plane algorithm for programs based on a family of polyhedra which strengthen the usual LP relaxation. We show how to generate a facet of a polyhedron in this family which is most...
Supply Contracts Under Bounded Order Quantities. (1998)
Kumar, Anant, Akella, Ram, Cornuejols, Gerard
It is the practice in some industries, as well as within multiplant organizations, to specify bounds on the range of allowable order values. That Z's, the buyer contracts to place an order within a...
Polyhedral Methods for the Maximum Clique Problem, (1997)
Balas, Egon, Ceria, Sebastian, Cornuejols, Gerard, Pataki, Gabor
This paper presents an integer programming approach to the maximum clique problem. An initial linear programming relaxation is solved and, when there is an integrality gap, this relaxation is...