Lower Bounding Procedures for the Single Allocation Hub Location Problem

This paper proposes a new lower bounding procedure for the Uncapacitated Single Allocation p-Hub Median Problem based on Lagrangean relaxation. For solving the resulting Lagrangean subproblem, the given problem structure is exploited: it can be decomposed into smaller subproblems that can be solved efficiently by combinatorial algorithms. Our computational experiments for some benchmark instances demonstrate … Read more

Lower Bounds for the Quadratic Minimum Spanning Tree Problem Based on Reduced Cost Computation

The Minimum Spanning Tree Problem (MSTP) is one of the most known combinatorial optimization problems. It concerns the determination of a minimum edge-cost subgraph spanning all the vertices of a given connected graph. The Quadratic Minimum Spanning Tree Problem (QMSTP) is a variant of the MST whose cost considers also the interaction between every pair … Read more

Nonsmooth Optimization Using Uncontrolled Inexact Information

We consider convex nonsmooth optimization problems whose objective function is known through a (fine) oracle together with some additional (cheap but poor) information – formalized as a second coarse oracle with uncontrolled inexactness. It is the case when the objective function is itself the output of an optimization solver, using a branch-and-bound procedure, or decomposing … Read more

Simplified Copositive and Lagrangian Relaxations for Linearly Constrained Quadratic Optimization Problems in Continuous and Binary Variables

For a quadratic optimization problem (QOP) with linear equality constraints in continuous nonnegative variables and binary variables, we propose three relaxations in simplified forms with a parameter $\lambda$: Lagrangian, completely positive, and copositive relaxations. These relaxations are obtained by reducing the QOP to an equivalent QOP with a single quadratic equality constraint in nonnegative variables, … Read more

A Parallel Bundle Method for Asynchronous Subspace Optimization in Lagrangian Relaxation

An algorithmic approach is proposed for exploiting parallelization possibilities in large scale optimization models of the following generic type. Objects change their state over time subject to a limited availability of common resources. These are modeled by linear coupling constraints and result in few objects competing for the same resource at each point in time. … Read more

The Lagrangian Relaxation for the Combinatorial Integral Approximation Problem

We are interested in methods to solve mixed-integer nonlinear optimal control problems (MIOCPs) constrained by ordinary di erential equations and combinatorial constraints on some of the control functions. To solve these problems we use a rst discretize, then opti- mize approach to get a specially structured mixed-integer nonlinear program (MINLP). We decompose this MINLP into an … Read more

Dynamic Graph Generation for Large Scale Operational Train Timetabling

The aim of operational train timetabling is to find a conflict free timetable for a set of passenger and freight trains with predefined stopping time windows along given routes in an infrastructure network so that station capacities and train dependent running and headway times are observed. Typical models for this problem are based on time-discretized … Read more

Generalized Bundle Methods for Sum-Functions with Easy” Components: Applications to Multicommodity Network Design

We propose a modification to the (generalized) bundle scheme for minimization of a convex nondifferentiable sum-function in the case where some of the components are “easy”, that is, they are Lagrangian functions of explicitly known convex programs with “few” variables and constraints. This happens in many practical cases, particularly within applications to combinatorial optimization. In … Read more

The Reliable Hub-and-spoke Design Problem: Models and Algorithms

This paper presents a study on reliable single and multiple allocation hub-and-spoke network design problems where disruptions at hubs and the resulting hub unavailability can be mitigated by backup hubs and alternative routes. It builds nonlinear mixed integer programming models and presents linearized formulas. To solve those difficult problems, Lagrangian relaxation and Branch-and-Bound methods are … Read more

Monotonicity recovering and accuracy preserving optimization methods for postprocessing finite element solutions

We suggest here a least-change correction to available finite element (FE) solution. This postprocessing procedure is aimed at recovering the monotonicity and some other important properties that may not be exhibited by the FE solution. It is based on solving a monotonic regression problem with some extra constraints. One of them is a linear equality-type … Read more