Path Cover and Path Pack Inequalities for the Capacitated Fixed-Charge Network Flow Problem

  • Alper Atamturk
  • Simge Küçükyavuz
  • Birce Tezel
    • Categories (Mixed) Integer Linear Programming, Cutting Plane Approaches Tags , , ,

    Capacitated fixed-charge network flows are used to model a variety of problems in telecommunication, facility location, production planning and supply chain management. In this paper, we investigate capacitated path substructures and derive strong and easy-to-compute path cover and path pack inequalities. These inequalities are based on an explicit characterization of the submodular inequalities through a … Read more

    Global Solution Strategies for the Network-Constrained Unit Commitment Problem With AC Transmission Constraints

  • Anya Castillo
  • Carl D. Laird
  • Jean-Paul Watson
  • Jianfeng Liu
    • Categories Global Optimization, Integer Programming, Nonlinear Optimization Tags , ,

    We propose a novel global solution algorithm for the network-constrained unit commitment problem that incorporates a nonlinear alternating current model of the transmission network, which is a nonconvex mixed-integer nonlinear programming (MINLP) problem. Our algorithm is based on the multi-tree global optimization methodology, which iterates between a mixed-integer lower-bounding problem and a nonlinear upper-bounding problem. … Read more

    Extending the ergodic convergence rate of the proximal ADMM

  • Max L. N. Gonçalves
  • Jefferson Gonçalves Melo
  • Renato D.C. Monteiro
    • Categories Convex Optimization, Nonsmooth Optimization Tags , , , , , , , ,

    Pointwise and ergodic iteration-complexity results for the proximal alternating direction method of multipliers (ADMM) for any stepsize in $(0,(1+\sqrt{5})/2)$ have been recently established in the literature. In addition to giving alternative proofs of these results, this paper also extends the ergodic iteration-complexity result to include the case in which the stepsize is equal to $(1+\sqrt{5})/2$. … Read more

    Distributionally Robust Project Crashing with Partial or No Correlation Information

  • Selin Damla Ahipasaoglu
  • Karthik Natarajan
  • Dongjian Shi
    • Categories Robust Optimization, Semi-definite Programming

    Crashing is a method for optimally shortening the project makespan by reducing the time of one or more activities in a project network by allocating resources to it. Activity durations are however uncertain and techniques in stochastic optimization, robust optimization and distributionally robust optimization have been developed to tackle this problem. In this paper, we … Read more

    Cyclic Coordinate Update Algorithms for Fixed-Point Problems: Analysis and Applications

  • Yat Tin Chow
  • Wotao Yin
  • Tianyu Wu
    • Categories Convex and Nonsmooth Optimization Tags , , , , , , ,

    Many problems reduce to the fixed-point problem of solving $x=T(x)$. To this problem, we apply the coordinate-update algorithms, which update only one or a few components of $x$ at each step. When each update is cheap, these algorithms are faster than the full fixed-point iteration (which updates all the components). In this paper, we focus … Read more

    Generalized average shadow prices and bottlenecks

  • Alejandro Crema
    • Categories (Mixed) Integer Linear Programming, Applications - OR and Management Sciences Tags , , ,

    We present a generalization of the average shadow price in 0-1-Mixed Integer Linear Programming problems and its relation with bottlenecks including the analysis relative to the coefficients matrix of resource constraints. A mathematical programming approach to find the strategy for investment in resources is presented. CitationEscuela de Computación, Facultad de Ciencias, Universidad Central de VenezuelaArticleDownload … Read more

    Achievable Rates for a LAN-Limited Distributed Receiver in Gaussian Interference

  • Daniel W. Bliss
  • Hans D Mittelmann
  • Christian D. Chapman
  • Adam R. Margetts
    • Categories Applications - Science and Engineering Tags , ,

    A base node seeks to receive a broadcast with its own observation in addition to side-information provided via a local area network (LAN) from several ‘helper nodes,’potentially occluded by an external interferer. Ideally, helpers would convey their precise observations to the base but the LAN has limited capacity, so helpers must compress and forward. Bounds … Read more

    SPECTRA – a Maple library for solving linear matrix inequalities in exact arithmetic

  • Didier Henrion
  • Simone Naldi
  • Mohab Safey El Din
    • Categories Semi-definite Programming Tags , , , ,

    This document briefly describes our freely distributed Maple library {\sc spectra}, for Semidefinite Programming solved Exactly with Computational Tools of Real Algebra. It solves linear matrix inequalities in exact arithmetic and it is targeted to small-size, possibly degenerate problems for which symbolic infeasibility or feasibility certificates are required. ArticleDownload View PDF

    BFGS-like updates of constraint preconditioners for sequences of KKT linear systems

  • Luca Bergamaschi
  • Valentina De Simone
  • Daniela di Serafino
  • Angeles Martinez
    • Categories Nonlinear Optimization, Quadratic Programming Tags

    We focus on efficient preconditioning techniques for sequences of KKT linear systems arising from the interior point solution of large convex quadratic programming problems. Constraint Preconditioners (CPs), though very effective in accelerating Krylov methods in the solution of KKT systems, have a very high computational cost in some instances, because their factorization may be the … Read more