Robust Branch-Cut-and-Price for the Capacitated Minimum Spanning Tree Problem over a Large Extended Formulation

This paper presents a robust branch-cut-and-price algorithm for the Capacitated Minimum Spanning Tree Problem (CMST). The variables are associated to $q$-arbs, a structure that arises from a relaxation of the capacitated prize-collecting arborescence probem in order to make it solvable in pseudo-polynomial time. Traditional inequalities over the arc formulation, like Capacity Cuts, are also used. … Read more

Copositive programming motivated bounds on the stability and the chromatic number

The Lovasz theta number of a graph G can be viewed as a semidefinite programming relaxation of the stability number of G. It has recently been shown that a copositive strengthening of this semidefinite program in fact equals the stability number of G. We introduce a related strengthening of the Lovasz theta number toward the … Read more

Goal Driven Optimization

Achieving a targeted objective, goal or aspiration level are relevant aspects of decision making under uncertainties. We develop a goal driven stochastic optimization model that takes into account an aspiration level. Our model maximizes the shortfall aspiration level criterion}, which encompasses the probability of success in achieving the goal and an expected level of under-performance … Read more

Valid Inequalities and Restrictions for Stochastic Programming Problems with First Order Stochastic Dominance Constraints

Stochastic dominance relations are well-studied in statistics, decision theory and economics. Recently, there has been significant interest in introducing dominance relations into stochastic optimization problems as constraints. In the discrete case, stochastic optimization models involving second order stochastic dominance (SSD) constraints can be solved by linear programming (LP). However, problems involving first order stochastic dominance … Read more

Improved bounds for the symmetric rendezvous search problem on the line

A notorious open problem in the field of rendezvous search is to decide the rendezvous value of the symmetric rendezvous search problem on the line, when the initial distance apart between the two players is 2. We show that the symmetric rendezvous value is within the interval (4.1520, 4.2574), which considerably improves the previous best … Read more

An inexact primal-dual path following algorithm for convex quadratic SDP

We propose primal-dual path-following Mehrotra-type predictor-corrector methods for solving convex quadratic semidefinite programming (QSDP) problems of the form: $\min_{X} \{ \frac{1}{2} X\bullet {\cal Q}(X) + C\bullet X : {\cal A} (X) = b, X\succeq 0\}$, where ${\cal Q}$ is a self-adjoint positive semidefinite linear operator on ${\cal S}^n$, $b\in R^m$, and ${\cal A}$ is a … Read more

Exponential neighborhood search for a parallel machine scheduling problem

We consider the parallel machine scheduling problem where jobs have different earliness-tardiness penalties and a restrictive common due date. This problem is NP-hard in the strong sense. In this paper we define an exponential size neighborhood for this problem and prove that finding the local minimum in it is an NP-hard problem. The main contribution … Read more

Robust Semidefinite Programming Approaches for Sensor Network Localization with Anchors

We derive a robust primal-dual interior-point algorithm for a semidefinite programming, SDP, relaxation for sensor localization with anchors and with noisy distance information. The relaxation is based on finding a Euclidean Distance Matrix, EDM, that is nearest in the Frobenius norm for the known noisy distances and that satisfies given upper and lower bounds on … Read more

New Inequalities for Finite and Infinite Group Problems from Approximate Lifting

In this paper, we derive new families of piecewise linear facet-defining inequalities for the finite group problem and extreme inequalities for the infinite group problem using approximate lifting. The new valid inequalities for the finite group problem are two- and three-slope facet-defining inequalities as well as the first family of four-slope facet-defining inequalities. The new … Read more

Perturbed projections and subgradient projections for the multiple-sets split feasibility problem

We study the multiple-sets split feasibility problem that requires to find a point closest to a family of closed convex sets in one space such that its image under a linear transformation will be closest to another family of closed convex sets in the image space. By casting the problem into an equivalent problem in … Read more