Evaluating Mixed-Integer Programming Models over Multiple Right-hand Sides

A critical measure of model quality for a mixed-integer program (MIP) is the difference, or gap, between its optimal objective value and that of its linear programming relaxation. Although in many contexts, only an approximation of the right-hand side(s) is available, there is no consensus on appropriate measures for MIP model quality over multiple right-hand … Read more

Relaxations and Duality for Multiobjective Integer Programming

Multiobjective integer programs (MOIPs) simultaneously optimize multiple objective functions over a set of linear constraints and integer variables. In this paper, we present continuous, convex hull and Lagrangian relaxations for MOIPs and examine the relationship among them. The convex hull relaxation is tight at supported solutions, i.e., those that can be derived via a weighted-sum … Read more

The Gap Function: Evaluating Integer Programming Models over Multiple Right-hand Sides

For an integer programming model with fixed data, the linear programming relaxation gap is considered one of the most important measures of model quality. There is no consensus, however, on appropriate measures of model quality that account for data variation. In particular, when the right-hand side is not known exactly, one must assess a model … Read more

Two-Stage Quadratic Integer Programs with Stochastic Right-Hand Sides

We consider two-stage quadratic integer programs with stochastic right-hand sides, and present an equivalent reformulation using value functions. We fi rst derive some basic properties of value functions of quadratic integer programs. We then propose a two-phase solution approach. The first phase constructs the value functions of quadratic integer programs in both stages. The second phase … Read more