Two dimensional lattice-free cuts and asymmetric disjunctions for mixed-integer polyhedra

In this paper, we study the relationship between {\em 2D lattice-free cuts}, the family of cuts obtained by taking two-row relaxations of a mixed-integer program (MIP) and applying intersection cuts based on maximal lattice-free sets in $\R^2$, and various types of disjunctions. Recently, Li and Richard (2007) studied disjunctive cuts obtained from $t$-branch split disjunctions … Read more

Solving A Low-Rank Factorization Model for Matrix Completion by A Nonlinear Successive Over-Relaxation Algorithm

The matrix completion problem is to recover a low-rank matrix from a subset of its entries. The main solution strategy for this problem has been based on nuclear-norm minimization which requires computing singular value decompositions — a task that is increasingly costly as matrix sizes and ranks increase. To improve the capacity of solving large-scale … Read more

Kusuoka Representation of Higher Order Dual Risk Measures

We derive representations of higher order dual measures of risk in $\mathcal{L}^p$ spaces as suprema of integrals of Average Values at Risk with respect to probability measures on $(0,1]$ (Kusuoka representations). The suprema are taken over convex sets of probability measures. The sets are described by constraints on the dual norms of certain transformations of … Read more

A Hybrid Shifting Bottleneck-Tabu Search Heuristic for the Job Shop Total Weighted Tardiness Problem

In this paper, we study the job shop scheduling problem with the objective of minimizing the total weighted tardiness. We propose a hybrid shifting bottleneck – tabu search (SB-TS) algorithm by replacing the reoptimization step in the shifting bottleneck (SB) algorithm by a tabu search (TS). In terms of the shifting bottleneck heuristic, the proposed … Read more

Robust Airline Schedule Planning: Minimizing Propagated Delay in an Integrated Routing and Crewing Framework

To retain a degree of tractability, the airline scheduling problem has traditionally been sequentially decomposed into various stages (eg. schedule generation, fleet assignment, aircraft routing, and crew pairing), with the decisions from one stage imposed upon the decision making process in subsequent stages. Whilst this approach greatly simpli es the solution process, it unfortunately fails to … Read more

Isomorphism testing for circulant graphs Cn(a,b)

In this paper we focus on connected directed/undirected circulant graphs Cn(a,b). We investigate some topological characteristics, and define a simple combinatorial model, which is new for the topic. Building on such a model, we derive a necessary and sufficient condition to test whether two circulant graphs Cn(a, b) and Cn(a’,b’) are isomorphic or not. The … Read more

The unified framework of some proximal-based decomposition methods for monotone variational inequalities with separable structure

Some existing decomposition methods for solving a class of variational inequalities (VI) with separable structures are closely related to the classical proximal point algorithm, as their decomposed sub-VIs are regularized by proximal terms. Differing in whether the generated sub-VIs are suitable for parallel computation, these proximal-based methods can be categorized into the parallel decomposition methods … Read more

Stability Analysis of Two Stage Stochastic Mathematical Programs with Complementarity Constraints via NLP-Regularization

This paper presents numerical approximation schemes for a two stage stochastic programming problem where the second stage problem has a general nonlinear complementarity constraint: first, the complementarity constraint is approximated by a parameterized system of inequalities with a well-known regularization approach (SIOPT, Vol.11, 918-936) in deterministic mathematical programs with equilibrium constraints; the distribution of the … Read more

Lipschitz solutions of optimal control problems with state constraints of arbitrary order

In this paper we generalize to an arbitrary order, under minimal hypotheses, some sufficient conditions for Lipschitz continuity of the solution of a state constrained optimal control problems. The proof combines the approach by Hager in 1979 for dealing with first-order state constraints, and the high-order alternative formulation of the optimality conditions. Citation Published as … Read more

New Lower Bounds for the Vehicle Routing Problem with Simultaneous Pickup and Delivery

This work deals with the Vehicle Routing Problem with Simultaneous Pickup and Delivery (VRPSPD). We propose undirected and directed two-commodity flow formulations, which are based on the one developed by Baldacci, Hadjiconstantinou and Mingozzi for the Capacitated Vehicle Routing Problem. These new formulations are theoretically compared with the one-commodity flow formulation proposed by Dell’Amico, Righini … Read more