computational complexity

Insights into the computational complexity of the single-source capacitated facility location problem with customer preferences

  • Christina Büsing
  • Timo Gersing
  • Sophia Wrede
    • Categories Combinatorial Optimization Tags , , ,

    Single-source capacitated facility location problems are well studied in the operations research literature, yet classic problems often lack practicability by disregarding the customers’ perspective: An authority that assigns customers to open facilities deprives customers from choosing facilities according to their individual preferences. In reality, this can render solutions infeasible, as customers may deviate to their … Read more

    Unboundedness in Bilevel Optimization

  • Bárbara Rodrigues
  • Margarida Carvalho
  • Miguel F. Anjos
  • nsugishita
    • Categories Bilevel Optimization, Nonlinear Optimization Tags , , ,

    Bilevel optimization has garnered growing interest over the past decade. However, little attention has been paid to detecting and dealing with unboundedness in these problems, with most research assuming a bounded high-point relaxation. In this paper, we address unboundedness in bilevel and multilevel optimization by studying its computational complexity. We show that deciding whether an … Read more

    Complexity of the Directed Robust b-matching Problem and its Variants on Different Graph Classes

  • Jenny Segschneider
  • Arie M.C.A. Koster
    • Categories Network Optimization, Robust Optimization Tags , , ,

    The b-matching problem is a well-known generalization of the classical matching problem with various applications in operations research and computer science. Given an undirected graph, each vertex v has a capacity b(v), indicating the maximum number of times it can be matched, while edges can also be used multiple times. The problem is solvable in … 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

    Hardness of pricing routes for two-stage stochastic vehicle routing problems with scenarios

  • Matheus Jun Ota
  • Ricardo Fukasawa
    • Categories Combinatorial Optimization, Integer Programming, Stochastic Programming Tags , ,

    The vehicle routing problem with stochastic demands (VRPSD) generalizes the classic vehicle routing problem by considering customer demands as random variables. Similarly to other vehicle routing variants, state-of-the-art algorithms for the VRPSD are often based on set-partitioning formulations, which require efficient routines for the associated pricing problems. However, all these set-partitioning-based approaches have strong assumptions … Read more

    Robust Two-Dose Vaccination Schemes and the Directed b-Matching Problem

  • Jenny Segschneider
  • Arie M.C.A. Koster
    • Categories Applications - OR and Management Sciences, Robust Optimization Tags , , , ,

    In light of the recent pandemic and the shortage of vaccinations during their roll-out, questions arose regarding the best strategy to achieve immunity throughout the population by adjusting the time gap between the two necessary vaccination doses. This strategy has already been studied from different angles by various researches. However, the deliveries of vaccination doses … Read more

    Recognition of Facets for Knapsack Polytope is DP-complete

  • Haoran Zhu
    • Categories 0-1 Programming, Integer Programming Tags , , ,

    DP  is a complexity class that is the class of all languages that are the intersection of a language in NP and a language in co-NP, as coined by Papadimitriou and Yannakakis. In this paper, we will establish that, recognizing a facet for the knapsack polytope is DP-complete, as conjectured by Hartvigsen and Zemel in … Read more

    Using Taylor-Approximated Gradients to Improve the Frank-Wolfe Method for Empirical Risk Minimization

  • Zikai Xiong
  • Robert M. Freund
    • Categories Constrained Nonlinear Optimization, Convex Optimization, Stochastic Programming Tags , , , , ,

    The Frank-Wolfe method has become increasingly useful in statistical and machine learning applications, due to the structure-inducing properties of the iterates, and especially in settings where linear minimization over the feasible set is more computationally efficient than projection. In the setting of Empirical Risk Minimization — one of the fundamental optimization problems in statistical and … Read more

    Deciding the Feasibility of a Booking in the European Gas Market is coNP-hard

  • Johannes Thürauf
    • Categories Applications - OR and Management Sciences, Network Optimization Tags , , , ,

    We show that deciding the feasibility of a booking (FB) in the European entry-exit gas market is coNP-hard if a nonlinear potential-based flow model is used. The feasibility of a booking can be characterized by polynomially many load flow scenarios with maximum potential-difference, which are computed by solving nonlinear potential-based flow models. We use this … Read more