Approximating the Pareto frontier for bi-objective preventive maintenance and workshop scheduling. A Lagrangean lower bounding methodology for evaluating contracting forms

  • Gabrijela Obradović
  • Ann-Brith Strömberg
  • Felix Held
    • Categories (Mixed) Integer Linear Programming, Scheduling Tags , , ,

    Effective planning of preventive maintenance plays an important role in maximizing the operational readiness of any industrial system. We consider an operating system and a maintenance workshop governed by two stakeholders who collaborate based on a mutual contract: components of the operating system that need maintenance are sent to the maintenance workshop, where necessary maintenance … Read more

    Computational Guarantees for Restarted PDHG for LP based on “Limiting Error Ratios” and LP Sharpness

  • Zikai Xiong
  • Robert M. Freund
    • Categories Convex Optimization, Linear Programming, Linear, Cone and Semidefinite Programming Tags , , , , , , ,

    In recent years, there has been growing interest in solving linear optimization problems – or more simply “LP” – using first-order methods in order to avoid the costly matrix factorizations of traditional methods for huge-scale LP instances. The restarted primal-dual hybrid gradient method (PDHG) – together with some heuristic techniques – has emerged as a … Read more

    On the Relation Between LP Sharpness and Limiting Error Ratio and Complexity Implications for Restarted PDHG

  • Zikai Xiong
  • Robert M. Freund
    • Categories Convex Optimization, Linear Programming, Linear, Cone and Semidefinite Programming Tags , , , , , , ,

    There has been a recent surge in development of first-order methods (FOMs) for solving huge-scale linear programming (LP) problems. The attractiveness of FOMs for LP stems in part from the fact that they avoid costly matrix factorization computation. However, the efficiency of FOMs is significantly influenced – both in theory and in practice – by … Read more

    Convergence Rate of Projected Subgradient Method with Time-varying Step-sizes

  • Zhihan
  • Yanhao Zhang
  • Yong Xia
    • Categories Convex and Nonsmooth Optimization, Convex Optimization, Nonsmooth Optimization Tags , , ,

    We establish the optimal ergodic convergence rate for the classical projected subgradient method with time-varying step-sizes. This convergence rate remains the same even if we slightly increase the weight of the most recent points, thereby relaxing the ergodic sense. ArticleDownload View PDF

    Convergence of the Chambolle–Pock Algorithm in the Absence of Monotonicity

  • Brecht Evens
    • Categories Generalized Convexity/Monoticity, Nonsmooth Optimization Tags , , , , ,

    The Chambolle-Pock algorithm (CPA), also known as the primal-dual hybrid gradient method (PDHG), has surged in popularity in the last decade due to its success in solving convex/monotone structured problems. This work provides convergence results for problems with varying degrees of (non)monotonicity, quantified through a so-called oblique weak Minty condition on the associated primal-dual operator. … Read more

    Adaptive Partitioning for Chance-Constrained Problems with Finite Support

  • Marius Roland
  • Alexandre Forel
  • Thibaut Vidal
    • Categories Integer Programming, Stochastic Programming

    This paper studies chance-constrained stochastic optimization problems with finite support. It presents an iterative method that solves reduced-size chance-constrained models obtained by partitioning the scenario set. Each reduced problem is constructed to yield a bound on the optimal value of the original problem. We show how to adapt the partitioning of the scenario set so … Read more

    It’s All in the Mix: Wasserstein Classification and Regression with Mixed Features

  • Mohammad Reza Belbasi
  • Aras Selvi
  • Wolfram Wiesemann
    • Categories Optimization in Data Science, Robust Optimization Tags , , ,

    Problem definition: A key challenge in supervised learning is data scarcity, which can cause prediction models to overfit to the training data and perform poorly out of sample. A contemporary approach to combat overfitting is offered by distributionally robust problem formulations that consider all data-generating distributions close to the empirical distribution derived from historical samples, … Read more

    An Exceptionally Difficult Binary Quadratic Optimization Problem with Symmetry: a Challenge for The Largest Unsolved QAP Instance Tai256c

  • Koichi Fujii
  • Sunyoung Kim
  • Masakazu Kojima
  • Hans D Mittelmann
  • Yuji Shinano
    • Categories 0-1 Programming, Quadratic Programming, Semi-definite Programming Tags , , , , ,

    Tai256c is the largest unsolved quadratic assignment problem (QAP) instance in QAPLIB. It is known that QAP tai256c can be converted into a 256 dimensional binary quadratic optimization problem (BQOP) with a single cardinality constraint which requires the sum of the binary variables to be 92. As the BQOP is much simpler than the original … Read more

    Inter-DS: A cost saving algorithm for expensive constrained multi-fidelity blackbox optimization

  • Xavier Lebeuf
  • Sébastien Le Digabel
  • Charles Audet
  • Miguel Diago
  • Stéphane Alarie
    • Categories Constrained Nonlinear Optimization, Energy, Optimization of Simulated Systems Tags , , , , ,

    This work introduces a novel blackbox optimization algorithm for computationally expensive constrained multi-fidelity problems. When applying a direct search method to such problems, the scarcity of feasible points may lead to numerous costly evaluations spent on infeasible points. Our proposed fidelity and interruption controlled optimization algorithm addresses this issue by leveraging multi-fidelity information, allowing for … Read more

    Doubly stochastic primal dual splitting algorithm with variance reduction for saddle point problems

  • Dimitri Papadimitriou
    • Categories Constrained Nonlinear Optimization, Convex Optimization, Nonlinear Optimization, Unconstrained Optimization Tags , , , , ,

    The structured saddle-point problem involving the infimal convolution in real Hilbert spaces finds applicability in many applied mathematics disciplines. For this purpose, we develop a stochastic primal-dual splitting algorithm with loopless variance-reduction for solving this generic problem. We first prove the weak almost sure convergence of the iterates. We then demonstrate that our algorithm achieves … Read more