lagrangian relaxation

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

  • Antonio Frangioni
  • Enrico Gorgone
    • Categories Convex and Nonsmooth Optimization, Linear Programming, Network Optimization Tags , , , ,

    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

  • Yu An
  • Bo Zeng
  • Yu Zhang
    • Categories Applications - OR and Management Sciences, Facility Planning and Design, Network Optimization Tags , ,

    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

  • Oleg Burdakov
  • Ivan Kapyrin
  • Yuri Vassilevski
    • Categories Convex Optimization Tags , , , , ,

    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

    Inexact Dynamic Bundle Methods

  • Krzysztof C. Kiwiel
    • Categories Convex Optimization, Nonsmooth Optimization Tags , , ,

    We give a proximal bundle method for minimizing a convex function $f$ over $\mathbb{R}_+^n$. It requires evaluating $f$ and its subgradients with a possibly unknown accuracy $\epsilon\ge0$, and maintains a set of free variables $I$ to simplify its prox subproblems. The method asymptotically finds points that are $\epsilon$-optimal. In Lagrangian relaxation of convex programs, it … Read more

    A new lower bound for one-machine earliness-tardiness scheduling

  • Francis Sourd
    • Categories Scheduling Tags , , , ,

    In one-machine scheduling, MIP time-indexed formulations are often used to provide very good lower bounds through Lagrangian relaxations. In order to get an improved lower bound, we add valid cuts to a time-indexed formulation and show we still have a Lagrangian relaxation that can be solved as a shortest path in a graph. Two branch-and-bound … Read more

    A Computational Analysis of Lower Bounds for Big Bucket Production Planning Problems

  • Kerem Akartunali
  • Andrew J. Miller
    • Categories Production and Logistics Tags , , ,

    In this paper, we analyze a variety of approaches to obtain lower bounds for multi-level production planning problems with big bucket capacities, i.e., problems in which multiple items compete for the same resources. We give an extensive survey of both known and new methods, and also establish relationships between some of these methods that, to … Read more

    Solving the uncapacitated facility location problem with semi-Lagrangian relaxation

  • Antonio Alonso-Ayuso
  • Cesar Beltran-Royo
  • Jean-Philippe Vial
    • Categories (Mixed) Integer Linear Programming, 0-1 Programming, Convex Optimization Tags , ,

    The semi-Lagrangian Relaxation (SLR) method has been introduced in Beltran et al. (2006) to solve the p-median problem. In this paper we apply the method to the Uncapacitated Facility Location (UFL) problem. We perform computational experiments on two main collections of UFL problems with unknown optimal values. On one collection, we manage to solve to … Read more

    A Lagrangian Heuristic for Satellite Range Scheduling with Resource Constraints

  • Fabrizio Marinelli
  • Salvatore Nocella
  • Fabrizio Rossi
  • Stefano Smriglio
    • Categories 0-1 Programming, Applications - OR and Management Sciences Tags , , , , ,

    The task of scheduling communications between satellites and ground control stations is getting more and more critical since an increasing number of satellites must be controlled by a small set of stations. In such a congested scenario, the current practice, in which experts build hand-made schedules, often leaves a large number of communication requests unserved. … Read more

    Decomposition in Integer Programming

  • M.V. Galati
  • Ted K. Ralphs
    • Categories (Mixed) Integer Linear Programming, Cutting Plane Approaches Tags , , , , ,

    Both cutting plane methods and traditional decomposition methods are procedures that compute a bound on the optimal value of an integer linear program (ILP) by constructing an approximation to the convex hull of feasible solutions. This approximation is obtained by intersecting the polyhedron associated with the continuous relaxation, which has an explicit representation, with an … Read more

    Sums of Squares and Semidefinite Programming Relaxations for Polynomial Optimization Problems with Structured Sparsity

  • Sunyoung Kim
  • Masakazu Kojima
  • Masakazu Muramatsu
  • Hayato Waki
    • Categories Constrained Nonlinear Optimization, Global Optimization, Linear, Cone and Semidefinite Programming Tags , , , , , ,

    Unconstrained and inequality constrained sparse polynomial optimization problems (POPs) are considered. A correlative sparsity pattern graph is defined to find a certain sparse structure in the objective and constraint polynomials of a POP. Based on this graph, sets of supports for sums of squares (SOS) polynomials that lead to efficient SOS and semidefinite programming (SDP) … Read more