Fair stochastic vehicle routing with partial deliveries

A common assumption in the models for the vehicle routing problem with stochastic demands is that all demands must be satisfied. This is achieved by including recourse actions in two-stage stochastic programming formulations or by ensuring with a high probability that all demand fits within the vehicle capacity (chance-constrained formulations). In this work, we relax … Read more

Column Elimination for Capacitated Vehicle Routing Problems

We introduce a column elimination procedure for the capacitated vehicle routing problem. Our procedure maintains a decision diagram to represent a relaxation of the set of feasible routes, over which we define a constrained network flow. The optimal solution corresponds to a collection of paths in the decision diagram and yields a dual bound. The … Read more

On solving the MAX-SAT using sum of squares

We consider semidefinite programming (SDP) approaches for solving the maximum satisfiabilityproblem (MAX-SAT) and the weighted partial MAX-SAT. It is widely known that SDP is well-suitedto approximate the (MAX-)2-SAT. Our work shows the potential of SDP also for other satisfiabilityproblems, by being competitive with some of the best solvers in the yearly MAX-SAT competition.Our solver combines … Read more

The min-Knapsack Problem with Compactness Constraints and Applications in Statistics

In the min-Knapsack problem, one is given a set of items, each having a certain cost and weight. The objective is to select a subset with minimum cost, such that the sum of the weights is not smaller than a given constant. In this paper we introduce an extension of the min-Knapsack problem with additional … Read more

The Hamiltonian p-median Problem: Polyhedral Results and Branch-and-Cut Algorithm

\(\) In this paper we study the Hamiltonian \(p\)-median problem, in which a weighted graph on \(n\) vertices is to be partitioned into \(p\) simple cycles of minimum total weight. We introduce two new families of valid inequalities for a formulation of the problem in the space of natural edge variables. Each one of the … Read more

A comparison of different approaches for the vehicle routing problem with stochastic demands

The vehicle routing problem with stochastic demands (VRPSD) is a well studied variant of the classic (deterministic) capacitated vehicle routing problem (CVRP) where the customer demands are given by random variables. Two prominent approaches for solving the VRPSD model it either as a chance-constraint program (CC-VRPSD) or as a two-stage stochastic program (2S-VRPSD). In this … Read more

The Largest Unsolved QAP Instance Tai256c Can Be Converted into A 256-dimensional Simple BQOP with A Single Cardinality Constraint

Tai256c is the largest unsolved quadratic assignment problem (QAP) instance in QAPLIB; a 1.48\% gap remains between the best known feasible objective value and lower bound of the unknown optimal value. This paper shows that the instance can be converted into a 256 dimensional binary quadratic optimization problem (BQOP) with a single cardinality constraint which … Read more

Cutting-plane algorithm for sparse estimation of the Cox proportional-hazards model

Survival analysis is a family of statistical methods for analyzing event occurrence times. In this paper, we address the mixed-integer optimization approach to sparse estimation of the Cox proportional-hazards model for survival analysis. Specifically, we propose a high-performance cutting-plane algorithm based on reformulation of bilevel optimization for sparse estimation. This algorithm solves the upper-level problem … Read more

On optimally solving sub-tree scheduling for wireless sensor networks with partial coverage

Energy efficiency and balancing are very important issues from the perspective of increasing the lifetime of a wireless sensor network (WSN). In this study, we concentrate on energy balancing. Given a WSN, we consider the problem to minimize its total power consumption over consecutive time slots with respect to communication activities. Disjoint subsets of nodes … Read more