Polyhedral results for a class of cardinality constrained submodular minimization problems
Motivated by concave cost combinatorial optimization problems, we study the following mixed integer nonlinear set: P = {(w,x) : w >= f(a’x), e’x
Cutting Plane Approaches
An Exact Extended Formulation for the Unrelated Parallel Machine Total Weighted Completion Time Problem
The plethora of research on NP-hard parallel machine scheduling problems is focused on heuristics due to the theoretically and practically challenging nature of these problems. Only a handful of exact approaches are available in the literature, and most of these suffer from scalability issues. Moreover, the majority of the papers on the subject are restricted … Read more
On the exact separation of rank inequalities for the maximum stable set problem
When addressing the maximum stable set problem on a graph G = (V,E), rank inequalities prescribe that, for any subgraph G[U] induced by U ⊆ V , at most as many vertices as the stability number of G[U] can be part of a stable set of G. These inequalities are very general, as many of … Read more
n-step cycle inequalities: facets for continuous n-mixing set and strong cuts for multi-module capacitated lot-sizing problem
In this paper, we introduce a generalization of the continuous mixing set (which we refer to as the continuous n-mixing set). This set is closely related to the feasible set of the multi-module capacitated lot-sizing (MML) problem with(out) backlogging. We develop new classes of valid inequalities for this set, referred to as n’-step cycle inequalities, … Read more
The split-demand one-commodity pickup-and-delivery travelling salesman problem
This paper introduces a new vehicle routing problem transferring one commodity between customers with a capacitated vehicle that can visit a customer more than once,although a maximum number of visits must be respected. It generalizes the capacitated vehicle routing problem with split demands and some other variants recently addressed in the literature. We model the … Read more
Equivariant Perturbation in Gomory and Johnson’s Infinite Group Problem. III. Foundations for the k-Dimensional Case with Applications to k=2
We develop foundational tools for classifying the extreme valid functions for the k-dimensional infinite group problem. In particular, (1) we present the general regular solution to Cauchy’s additive functional equation on bounded convex domains. This provides a k-dimensional generalization of the so-called interval lemma, allowing us to deduce affine properties of the function from certain … Read more
Strengthened Benders Cuts for Stochastic Integer Programs with Continuous Recourse
With stochastic integer programming as the motivating application, we investigate techniques to use integrality constraints to obtain improved cuts within a Benders decomposition algorithm. We compare the effect of using cuts in two ways: (i) cut-and-project, where integrality constraints are used to derive cuts in the extended variable space, and Benders cuts are then used … Read more
Decomposition Algorithm for Optimizing Multi-server Appointment Scheduling with Chance Constraints
We schedule appointments with random service durations on multiple servers with operating time limits. We minimize the costs of operating servers and serving appointments, subject to a joint chance constraint limiting the risk of server overtime. Using finite samples of the uncertainty, we formulate the problem as a mixed-integer linear program, and propose a two-stage … Read more
A Hierarchy of Subgraph Projection-Based Semidefinite Relaxations for some NP-Hard Graph Optimization Problems
Many important NP-hard combinatorial problems can be efficiently approximated using semidefinite programming relaxations. We propose a new hierarchy of semidefinite relaxations for classes of such problems that based on graphs and for which the projection of the problem onto a subgraph shares the same structure as the original problem. This includes the well-studied max-cut and … Read more
On the generation of cutting planes which maximize the bound improvement
We propose the bound-optimal cutting plane method. It is a new paradigm for cutting plane generation in Mixed Integer Programming allowing for the simultaneous generation of k cuts which, when added to the current Linear Programming elaxation, yield the largest bound improvement. By Linear Programming duality arguments and standard linearization techniques we show that, for … Read more