Robustness in Combinatorial Optimization and Scheduling Theory: An Extended Annotated Bibliography

  • Yury Nikulin
    • Categories Combinatorial Optimization, Robust Optimization, Scheduling

    This extended annotated bibliography focuses on what has been published during the last ten years in the area of combinatorial optimization and scheduling theory concerning robustness and other similar techniques dealing with worst case optimization under uncertainty and non-accuracy of problem data CitationChristian-Albrechts University in Kiel, Institute of Production and Logistics, Working paper ArticleDownload View … Read more

    Lagrange Multipliers with Optimal Sensitivity Properties

  • Dimitri Bertsekas
    • Categories Constrained Nonlinear Optimization Tags ,

    We consider optimization problems with inequality and abstract set constraints, and we derive sensitivity properties of Lagrange multipliers under very weak conditions. In particular, we do not assume uniqueness of a Lagrange multiplier or continuity of the perturbation function. We show that the Lagrange multiplier of minimum norm defines the optimal rate of improvement of … Read more

    Optimal Nodal Control of Networked Hyperbolic Systems: Evaluation of Derivatives

  • Martin Gugat
    • Categories Applications - Science and Engineering, Control Applications, Optimization of Systems modeled by PDEs Tags , , , , ,

    We consider a networked system defined on a graph where each edge corresponds to a quasilinear hyperbolic system with space dimension one. At the nodes, the system is governed by algebraic node conditions. The system is controlled at the nodes of the graph. Optimal control problems for systems of this type arise in the operation … Read more

    The Design and Implementation of a Generic Sparse Bundle Adjustment Software Package Based on the Levenberg-Marquardt Algorithm

  • Antonis Argyros
  • Manolis Lourakis
    • Categories Basic Sciences Applications, Nonlinear Systems and Least-Squares, Optimization Software and Modeling Systems Tags , , , , ,

    Bundle adjustment using the Levenberg-Marquardt minimization algorithm is almost invariably used as the last step of every feature-based structure and motion estimation computer vision algorithm to obtain optimal 3D structure and viewing parameter estimates. However, due to the large number of unknowns contributing to the minimized reprojection error, a general purpose implementation of the Levenberg-Marquardt … Read more

    Convergence of a hybrid projection-proximal point algorithm coupled with approximation methods in convex optimization

  • Felipe Álvarez
  • Miguel Carrasco
  • Karine Pichard
    • Categories Convex Optimization, Global Optimization

    In order to minimize a closed convex function that is approximated by a sequence of better behaved functions, we investigate the global convergence of a generic diagonal hybrid algorithm, which consists of an inexact relaxed proximal point step followed by a suitable orthogonal projection onto a hyperplane. The latter permits to consider a fixed relative … Read more

    Stabilized Branch-and-cut-and-price for the Generalized Assignment Problem

  • Alexandre Pigatti
  • Marcus Poggi de Aragão
  • Eduardo Uchoa
    • Categories Branch and Cut Algorithms, Meta Heuristics, Scheduling Tags , , ,

    The Generalized Assignment Problem (GAP) is a classic scheduling problem with many applications. We propose a branch-and-cut-and-price for that problem featuring a stabilization mechanism to accelerate column generation convergence. We also propose ellipsoidal cuts, a new way of transforming the exact algorithm into a powerful heuristic, in the same spirit of the cuts recently proposed … 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

    A genetic algorithm for the resource constrained multi-project scheduling problem

  • José Fernando Gonçalves
  • Jorge Magalhaes-Mendes
  • Mauricio G.C. Resende
    • Categories Meta Heuristics, Scheduling Tags , , ,

    This paper presents a genetic algorithm for the Resource Constrained Multi-Project Scheduling Problem (RCMPSP). The chromosome representation of the problem is based on random keys. The schedules are constructed using a heuristic that builds parameterized active schedules based on priorities, delay times, and release dates defined by the genetic algorithm. The approach is tested on … Read more

    Best approximation to common fixed points of a semigroup of nonexpansive operators

  • Arkady Aleyner
  • Yair Censor
    • Categories Constrained Nonlinear Optimization, Convex and Nonsmooth Optimization Tags , , , ,

    We study a sequential algorithm for finding the projection of a given point onto the common fixed points set of a semigroup of nonexpansive operators in Hilbert space. The convergence of such an algorithm was previously established only for finitely many nonexpansive operators. Algorithms of this kind have been applied to the best approximation and … Read more

    Proximal-ACCPM: a versatile oracle based optimization method

  • Frédéric Babonneau
  • Cesar Beltran
  • Jean-Philippe Vial
  • Alain Haurie
  • Claude Tadonki
    • Categories Applications - OR and Management Sciences, Convex and Nonsmooth Optimization, Optimization Software and Modeling Systems Tags , , , , , ,

    Oracle Based Optimization (OBO) conveniently designates an approach to handle a class of convex optimization problems in which the information pertaining to the function to be minimized and/or to the feasible set takes the form of a linear outer approximation revealed by an oracle. We show, through three representative examples, how difficult problems can be … Read more