(Mixed) Integer Linear Programming – Page 48

Integer Programming Approaches for Appointment Scheduling with Random No-shows and Service Durations

Published: 2015/08/31, Updated: 2016/09/30

We consider a single-server scheduling problem given a fixed sequence of appointment arrivals with random no-shows and service durations. The probability distribution of the uncertain parameters is assumed to be ambiguous and only the support and first moments are known. We formulate a class of distributionally robust (DR) optimization models that incorporate the worst-case expectation/conditional … Read more

The Uncapacitated Single Allocation p-Hub Median Problem with Stepwise Cost Function

Published: 2015/07/31, Updated: 2017/10/19

Christoph Buchheim

Borzou Rostami

(Mixed) Integer Linear Programming, Applications - OR and Management Sciences, Quadratic Programming Branch-and-Bound, hub location, lagrangian relaxation

In this paper, we address a new version of the Uncapacitated Single Allocation p-Hub Median Problem (USApHMP) in which transportation costs on each edge are given by piecewise constant cost functions. In the classical USApHMP, transportation costs are modelled as linear functions of the transport volume, where a fixed discount factor on hub-hub connections is … Read more

Constructing a Small Compact Binary Model for the Travelling Salesman Problem

Published: 2015/07/21, Updated: 2015/08/08

J. Fabian Meier

(Mixed) Integer Linear Programming, 0-1 Programming, Transportation landau function, mixed-integer programming, traveling salesman problem

A variety of formulations for the Travelling Salesman Problem as Mixed Integer Program have been proposed. They contain either non-binary variables or the number of constraints and variables is large. We want to give a new formulation that consists solely of binary variables; the number of variables and the number of constraints are of order … Read more

On Sublinear Inequalities for Mixed Integer Conic Programs

Published: 2015/07/10, Updated: 2016/03/10

Fatma Kılınç-Karzan

Daniel E. Steffy

(Mixed) Integer Linear Programming

This paper studies $K$-sublinear inequalities, a class of inequalities with strong relations to K-minimal inequalities for disjunctive conic sets. We establish a stronger result on the sufficiency of $K$-sublinear inequalities. That is, we show that when $K$ is the nonnegative orthant or the second-order cone, $K$-sublinear inequalities together with the original conic constraint are always … Read more

A Stabilised Scenario Decomposition Algorithm Applied to Stochastic Unit Commitment Problems

Published: 2015/07/06, Updated: 2017/02/04

Andreas Grothey

Kenneth McKinnon

Tim Schulze

(Mixed) Integer Linear Programming, Stochastic Programming dantzig-wolfe decomposition, heuristics, lagrangian relaxation, mixed-integer column generation, proximal bundle method, stochastic unit-commitment

In recent years the expansion of energy supplies from volatile renewable sources has triggered an increased interest in stochastic optimization models for hydro-thermal unit commitment. Several studies have modelled this as a two-stage or multi-stage stochastic mixed-integer optimization problem. Solving such problems directly is computationally intractable for large instances, and alternative approaches are required. In … Read more

Using the Johnson-Lindenstrauss lemma in linear and integer programming

Published: 2015/07/02

Leo Liberti

Pierre-Louis Poirion

Ky Vu

(Mixed) Integer Linear Programming, Linear Programming cone membership, dimension reduction, linear membership, random projections

The Johnson-Lindenstrauss lemma allows dimension reduction on real vectors with low distortion on their pairwise Euclidean distances. This result is often used in algorithms such as $k$-means or $k$ nearest neighbours since they only use Euclidean distances, and has sometimes been used in optimization algorithms involving the minimization of Euclidean distances. In this paper we … Read more

Mathematical programming algorithms for spatial cloaking

Published: 2015/06/24

(Mixed) Integer Linear Programming, Applications - Science and Engineering, Combinatorial Optimization branch-and-cut, branch-and-price, spatial cloaking, steiner trees

We consider a combinatorial optimization problem for spatial information cloaking. The problem requires to compute one or several disjoint arborescences on a graph from a predetermined root or subset of candidate roots, so that the number of vertices in the arborescences is minimized but a given threshold on the overall weight associated with the vertices … Read more

A cutting-plane approach for large-scale capacitated multi-period facility location using a specialized interior-point method

Published: 2015/06/10

Jordi Castro

Stefano Nasini

Francisco Saldanha-da-Gama

(Mixed) Integer Linear Programming, Cutting Plane Approaches, Linear Programming

We propose a cutting-plane approach (namely, Benders decomposition) for a class of capacitated multi-period facility location problems. The novelty of this approach lies on the use of a specialized interior-point method for solving the Benders subproblems. The primal block-angular structure of the resulting linear optimization problems is exploited by the interior-point method, allowing the (either … Read more

Embedding Formulations and Complexity for Unions of Polyhedra

Published: 2015/06/02, Updated: 2017/05/20

Juan Pablo Vielma

(Mixed) Integer Linear Programming

It is well known that selecting a good Mixed Integer Programming (MIP) formulation is crucial for an effective solution with state-of-the art solvers. While best practices and guidelines for constructing good formulations abound, there is rarely a systematic construction leading to the best possible formulation. We introduce embedding formulations and complexity as a new MIP … Read more