Ted K. Ralphs Empirical studies are fundamental in assessing the effectiveness of implementations of branch-and-bound algorithms. The complexity of such implementations makes empirical study difficult for a wide variety of reasons. Various attempts have been made to develop and codify a set of standard techniques for the assessment of optimization algorithms and their software implementations; however, most previous … Read more
We report on the selection process leading to the sixth version of the Mixed Integer Programming Library. Selected from an initial pool of 5,721 instances, the new MIPLIB 2017 collection consists of 1,065 instances. A subset of 240 instances was specially selected for benchmarking solver performance. For the first time, these sets were compiled using … Read more
We investigate how the numerical properties of the LP relaxations evolve throughout the solution procedure in a solver employing the branch-and-cut algorithm. The long-term goal of this work is to determine whether the effect on the numerical conditioning of the LP relaxations resulting from the branching and cutting operations can be effectively predicted and whether … Read more
In this article, we provide an overview of the current state of the art with respect to solution of mixed integer linear optimization problems (MILPS) in parallel. Sequential algorithms for solving MILPs have improved substantially in the last two decades and commercial MILP solvers are now considered effective off-the-shelf tools for optimization. Although concerted development … Read more
In this paper, we describe an algorithmic framework for solving mixed integer bilevel linear optimization problems (MIBLPs) by a generalized branch-and-cut approach. The framework presented merges features from existing algorithms (for both traditional mixed integer linear optimization and MIBLPs) with new techniques to produce a flexible and robust framework capable of solving a wide range … Read more
We study the convex hull of the intersection of a disjunctive set defined by parallel hyperplanes and the feasible set of a mixed integer second order cone optimization problem. We extend our prior work on disjunctive conic cuts, which has thus far been restricted to the case in which the intersection of the hyperplanes and … Read more
We describe a generalization of Benders’ method for solving two-stage stochastic linear optimization problems in which there are both continuous and integer variables in the first and second stages. Benders’ method relies on finding effective lower approximations for the value function of the second-stage problem. In this setting, the value function is a discontinuous, non-convex, … Read more
This paper addresses the value function of a general mixed integer linear optimization problem (MILP). The value function describes the change in optimal objective value as the right-hand side is varied and understanding its structure is central to solving a variety of important classes of optimization problems. We propose a discrete representation of the MILP … Read more
We investigate families of quadrics that have fixed intersections with two given hyper-planes. The cases when the two hyperplanes are parallel and when they are nonparallel are discussed. We show that these families can be described with only one parameter. In particular we show how the quadrics are transformed as the parameter changes. This research … Read more
We study the convex hull of the intersection of a convex set E and a linear disjunction. This intersection is at the core of solution techniques for Mixed Integer Conic Optimization. We prove that if there exists a cone K (resp., a cylinder C) that has the same intersection with the boundary of the disjunction … Read more