Consider the following restricted (symmetric or asymmetric) traveling-salesman problem (TSP): given an initial ordering of the n cities and an integer k> 0, find a minimum-cost feasible tour,...
Generating cuts from Multiple-Term Disjunctions (2007)
Michael Perregaard, Egon Balas
Abstract. The traditional approach towards generating lift-and-project cuts involves solving a cut generating linear program (CGLP) that grows prohibitively large if a multiple-term disjunction is...
Egon Balas, Milind Dawande, Francois Margot
We propose a new heuristic for pure 0--1 programs, which finds feasible integer points by enumerating extended facets of the octahedron, the outer polar of the unit hypercube. We give efficient...
Consider the following restricted (symmetric or asymmetric) traveling-salesman problem (TSP): given an initial ordering of the n cities and an integer k> 0, find a minimum-cost feasible tour,...
Weighted and Unweighted Maximum Clique Algorithms with Upper Bounds from Fractional Coloring (2006)
The linear programming relaxation of the minimum vertex coloring problem, called the fractional coloring problem, is NP-hard. We describe efficient approximation procedures for both the weighted and...
A.: Optimizing over the split closure (2006)
The polyhedron defined by all the split cuts obtainable directly (i.e. without iterated cut generation) from the LP-relaxation P of a mixed integer program (MIP) is termed the (elementary, or rank 1)...
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...
On unions and dominants of polytopes (2004)
Egon Balas, Er Bockmayr, Nicolai Pisaruk, Laurence Wolsey
A well-known result on unions of polyhedra in the same space gives an extended formulation whose projection is the convex hull of the union. Here in contrast we study the unions of polytopes in...
A Precise Correspondence Between Lift-and-Project Cuts, Simple Disjunctive Cuts (2003)
Egon Balas, Michael Perregaard
Abstract We establish a precise correspondence between lift-and-project cuts for mixed 0-1 programs, simple disjunctive cuts (intersection cuts) and mixed-integer Gomory cuts. The correspondence maps...
Facets of the Knapsack Polytope from Minimal Covers. (2002)
In this paper the authors give easily computable best upper and lower bounds on the coefficients of facets of the knapsack polytope associated with minimal covers. For some coefficients the upper...
Strengthening Cuts for Mixed Integer Programs. (2002)
Balas,Egon, Jeroslow,Robert G.
The authors give a method for strengthening cutting planes for pure and mixed integer programs. The method improves the coefficients of the integer-constrained variables, while leaving unchanged...
This paper discusses the set partitioning or equality-constrained set covering problem. It is a survey of theoretical results and solution methods for this problem. Part 1 gives some background...
Graph Substitution and Set Packing Polytopes. (2002)
Facets of the set packing polytope provide strong cutting planes for set packing and partitioning problems. Set packing polytopes are in a one to one correspondence with graphs. The facets of P(G),...
Critical Cutsets of Graphs and Canonical Facets of Set Packing Polytopes. (2002)
A cutset in a graph G with node set N is the set of edges joining the nodes in a subset of N to those not in the subset. A cutset is called critical if its removal produces a graph whose independence...
Set Partitioning: A Survey, (2002)
Balas,Egon, Padberg,Manfred W.
This paper discusses the set partitioning or equality-constrained set covering problem. It is a survey of theoretical results and solution methods for this problem. Part 1 gives some background...
Pivot and Complement - A Heuristic for 0-1 Programming. (2002)
Balas,Egon, Martin,Clarence H.
The pivot and complement procedure is a heuristic for finding approximate solutions to 0-1 programming problems. It uses the fact that a 0-1 program is equivalent to the associated linear program...
Solving Large Zero-One Knapsack Problems. (2002)
An algorithm for the 0-1 knapsack problem (KP) is described which relies mainly on three new ideas. The first one is to focus on the core of the problem, namely a knapsack problem equivalent to (KP),...
Benders's Method Revisited. (2002)
Balas,Egon, Bergthaller,Christian
The master problem in Benders's partitioning method is an integer program with a very large number of constraints, each of which is usually generated by solving the integer program with the...
A Restricted Lagrangean Approach to the Traveling Salesman Problem. (2002)
Balas,Egon, Christofides,Nicos
We describe an algorithm for the asymmetric traveling salesman problem (TSP) using a new, restricted Lagrangean relaxation based on the assignment problem (AP). The Lagrange multipliers are...
We report on the implementation and computational testing of several versions of a set covering algorithm, based on the family of cutting planes from conditional bounds. The algorithm uses a set of...
Valid Inequalities for 0-1 Programming Polytopes. (2002)
We introduce a family of valid inequalities for 0-1 programming polytopes that are typically not implied by individual problem constraints or by proper subsets of the full constraint set. The...
Linearizing Nonlinear 0-1 Programs. (2002)
Any real-valued nonlinear function in 0-1 variables can be rewritten as a multilinear function. We discuss classes of lower and upper bounding linear expressions for multilinear functions in 0-1...
A Note on the Weiszfeld-Kuhn Algorithm for the General Fermat Problem. (2002)
The General Fermat Problem, or Weber Problem, asks for a point that minimizes a weighted sum of the distances to m given points. The Weiszfeld-Kuhn algorithm is an iterative procedure that converges...
Branch and Bound Methods for the Traveling Salesman Problem. (2002)
This paper reviews the state of the art in enumerative solution methods for the traveling salesman problem (TSP). The introduction (Section 1) discusses the main ingredients of branch and bound...
This is an introductory survey of integer programming, its theory, methodology and applications, for the Encyclopedia of Statistical Sciences. (Author)
Traffic Assignment in Communication Satellites. (2002)
Balas,Egon, Landweer,Philip R.
A high capacity communication satellite interconnects scores of ground stations simultaneously. Under the Satellite-Switched/Time Division Multiple Access (SS/TDMA) system, each channel of the...
The Perfectly Matchable Subgraph Polytype of a Bipartite Graph. (2002)
Balas,Egon, Pulleyblank,William
The following type of problem arises in practice: in a node-weighted graph G, find a minimum weight node set that satisfies certain conditions and, in addition, induces a perfectly matchable subgraph...
On the Set Covering Polytope. I. All the Facets with Coefficients in (0,1,2). Revision. (2002)
While the set packing polytope, through its connection with vertex packing, has lent itself to fruitful investigations, little is known about the set covering polytope. We characterize the class of...
An O(/V/+/E/) Algorithm for finding an Edge-Maximal Subgraph with a TR-Formative Coloring. (2002)
If TR is the class of triangulated graphs, a TR-formative edge coloring is a green/red coloring of the edges of a graph, such that the green graph is triangulated (i.e. belongs to TR) and the red...
The Shifting Bottleneck Procedure for Job Shop Scheduling. (2002)
Adams, Joseph, Balas, Egon, Zawack, Daniel
This report describes an approximation method for solving the minimum makespan problem of job shop scheduling. It sequences the machines one by one, successively, taking each time the machine...
Facets of the Three-Index Assignment Polytope. Revision. (2002)
Balas,Egon, Saltzman,Matthew J.
Given three disjoint n-sets and the family of all weighted triplets that contain exactly one element of each set, the 3-index assignment (or 3-dimensional matching) problem asks for a minimum-weight...
More on Graphs with Polynomially Solvable Maximum-Weight Clique Problem. (2002)
This document gives a new bound on the number of maximal cliques in a graph along with a bound on the length of odd antiholes that the graph can contain. Based on these bounds a family of graphs with...
Sequential Convexification in Reverse Convex and Disjunctive Programming. (2002)
Balas, Egon, Tama, Joseph M., Tind, Jorgen
This paper is about a property of certain combinatorial structures, called sequential convexifiability, shown by Balas 1974, 1979 to hold for facial disjunctive programs. Sequential convexifiability...
OCTANE: a new heuristic for pure 0-1 programs (2001)
We propose a new heuristic for pure 0–1 programs, which finds feasible integer points by enumerating extended facets of the octahedron, the outer polar of the unit hypercube. We give efficient...
Lift-and-Project for Mixed 0-1 Programming: Recent Progress (2000)
Egon Balas, Michael Perregaard
Introduction Disjunctive programming Two basic ideas 2. Compact Representation of the Convex Hull Projection and polarity Adjacency on the higher dimensional polyhedron 3. Sequential Convexification...
On the Set Covering Problem. (1998)
Balas,Egon, Padberg,Manfred W.
The paper establishes some useful properties of the equality-constrained set covering problem P and the associated linear program P'. First, the Dantzig property of transportation matrices is shown...
On the Set Covering Problem. II. An Algorithm. (1998)
In an earlier paper the authors proved that any feasible integer solution to the linear program associated with the equality-constrained set covering problem can be obtained from any other feasible...
Adjacent Vertices of the Convex Hull of Feasible 0-1 Points. (1998)
In the paper the authors give a constructive characterization of adjacency relations between integer vertices of the feasible set of an all zero-one program. This characterization can be used, for...
Finding a Minimum Node Cover in an Arbitrary Graph. (1998)
The paper describes a node covering algorithm, i.e., a procedure for finding a smallest set of nodes covering all edges of an arbitrary graph. The algorithm is based on the concept of a dual...
Maximizing a Convex Quadratic Function Subject to Linear Constraints. (1998)
Balas,Egon, Burdet,Claude-Alain
In the paper the authors discuss a new method for solving linearly constrained, nonconvex quadratic programs in which the maximand is convex (or the minimand is concave). The approach is based on the...
All the Facets of Zero-One Programming Polytopes with Positive Coefficients. (1998)
The authors give a linear characterization of 0-1 programming polytopes with positive coefficients, by showing that every non-trival facet of such a polytope can be obtained from a minimal cover for...
The Asymmetric Assignment Problem and Some New Facets of the Traveling Salesman Polytope. (1998)
An assignment (spanning union of node-disjoint dicycles) in a directed graph is called asymmetric if it contains at most one arc of each pair (i,j), (j,i). This document describes a class of facets...
The Perfectly Matchable Subgraph Polytope of an Arbitrary Graph. (1998)
Balas, Egon, Pulleyblank, William R.
The Perfectly Matchable Subgraph Polytope of a graph G=(V,E), denoted by PMS (G) is the convex hull of the incidence vectors of those X is a subset of V which induce a subgraph having a perfect...
The Prize Collecting Traveling Salesman Problem. (1998)
The following is a valid model for an important class of scheduling and routing problems. A salesman who travels between pairs of cities at a cost depending only on the pair, gets a prize in every...
On the Set Covering Polytope. II. Lifting the Facets with Coefficients in (0,1,2). Revision. (1998)
An earlier paper characterized the class of facets of the set covering polytope defined by inequalities with coefficients equal to 0, 1 or 2. This paper connects that characterization to the theory...
On the Convex Hull of the Union of Certain Polyhedra. (1998)
This document considers a finite collection of polyhedra whose defining linear systems differ only in their right hand sides. Jeroslow and Blair specified conditions under which the convex hull of...
An Algorithm for the Three-Index Assignment Problem. (1998)
Balas, Egon, Saltzman, Matthew J.
A branch and bound algorithm is described for solving the axial three-index assignment problem. The main features of the algorithm include a Lagrangian relaxation incorporating a class of facet...
Linear-Time Separation Algorithms for the Three-Index Assignment Polytope. (1998)
Balas and Saltzman identified several classes of facet inducing inequalities for the three-index assignment polytope, and gave O(n to the 4th power) separation algorithms for two of them. We give O(n...
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...
A Parallel Shortest Augmenting Path Algorithm for the Assignment Problem. (1998)
Balas, Egon, Miller, Donald, Pekny, Joseph, Toth, Paolo
We describe a parallel version of the shortest augmenting path algorithm for the assignment problem. While generating the initial dual solution and partial assignment in parallel does not require...
Efficient algorithms are known for finding a maximum weight stable set, a minimum weight clique covering, and a maximum-weight clique of a vertex-weighted triangulated graph. However, there is no...
An Algorithm for the Three-Index Assignment Problem. (1998)
Balas, Egon, Saltzman, Matthew J.
We describe a branch and bound algorithm for solving the axial three-index assignment problem. The main features of the algorithm include a Lagrangian relaxation incorporating a class of facet...
The Fixed-Outdegree 1-Arborescence Polytope. (1998)
Balas, Egon, Fischetti, Matteo
A 1-arborescence is an arborescence rooted at node 1, plus one arc incident into node 1. The 1-arborescences polytope, the convex hull of incidence vectors of 1-arborescence, is a well known...
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...
Projection with a Minimal System of Inequalities. (1998)
Projection of a polyhedron involves the use of a cone whose extreme rays induce the inequalities defining the projection. These inequalities need not be facet defining. We introduce a transformation...
A Dynamic Subgradient-Based Branch and Bound Procedure for Set Covering. Revision, (1998)
Balas, Egon, Carrera, Maria C.
We discuss a branch and bound algorithm for set covering, whose centerpiece is an integrated upper bounding/lower bounding procedure called dynamic subgradient optimization (DYNSGRAD), that is...
Recent Advanced in Lift-and-Project (1998)
In recent years the lift-and-project approach has been used successfully within a branch-and-cut framework to solve large. difficult pure and mixed 0-1 programs that have resisted solution efforts by...
Lifted Cycle Inequalities for the Asymmetric Traveling Salesman Problem (1998)
Balas, Egon, Fischetti, Matteo
We investigate the family of facet defining inequalities for the asymmetric traveling salesman (ATS) polytope obtainable by lifting the cycle inequalities. We establish several properties of this...
Job Shop Scheduling with Deadlines (1998)
Egon Balas, Giuseppe Lancia, Paolo Serafini, Alkiviadis Vazacopoulos
In this paper we deal with a variant of the Job Shop Scheduling Problem. We consider the addition of release dates and deadlines to be met by all jobs. The objective is makespan minimization if there...
One Machine Scheduling With Delayed Precedence Constraints. (1997)
Balas, Egon, Lenstra, Jan K., Vazacopoulos, Alkis
We study the one machine scheduling problem with release and delivery times and the minimum makespan objective, in the presence of constraints that for certain pairs of jobs require a delay between...
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...
Choosing Algorithm Parameters Strategically (1997)
Erlendur Smári Þorsteinsson, Supervised Prof, Egon Balas
In this paper we examine the potential use of arti cial intelligence in choosing values for free parameters in the software implementation of algorithms. As a particular example we examine a...
Implementation of a linear time algorithm for certain generalized traveling salesman problems (1996)
Abstract. This paper discusses an implementation of a dynamic programming approach to the traveling salesman problem that runs in time linear in the number of cities. Optimality can be guaranteed...
On unions and dominants of polytopes
BALAS, Egon, BOCKMAYR, Alexander, PISARUK, Nicolai, WOLSEY, Laurence
A well-known result on unions of polyhedra in the same space gives an extended formulation whose projection is the convex hull of the union. Here in contrast we study the unions of polytopes in...
OCTANE: A New Heuristic for Pure 0--1 Programs
Egon Balas Sebasti'an, Egon Balas, Milind Dawande, Francois Margot
We propose a new heuristic for pure 0--1 programs, which finds feasible integer points by enumerating extended facets of the octahedron, the outer polar of the unit hypercube. We give efficient...
OCTANE: A New Heuristic for Pure 0-1 Programs
Egon Balas, Sebastián Ceria, Milind Dawande, Francois Margot, Gábor Pataki
We propose a new heuristic for pure 0--1 programs, which finds feasible integer points by enumerating extended facets of the octahedron, the outer polar of the unit hypercube. We give efficient...