Generalized preprocessing techniques for Steiner tree and maximum-weight connected subgraph problems

  • Thorsten Koch
  • Daniel Rehfeldt
    • Categories Combinatorial Optimization Tags ,

    This article introduces new reduction techniques for the Steiner tree problem in graphs (SPG) and one of its most popular relatives, the maximum-weight connected subgraph problem. Several of the techniques generalize previous results from the literature. In particular, we introduce a generalization of the Steiner bottleneck distance—the arguably most important reduction concept for SPG. While … Read more

    Partial Policy Iteration for L1-Robust Markov Decision Processes

  • Chin Pang Ho
  • Marek Petrik
  • Wolfram Wiesemann
    • Categories Robust Optimization Tags ,

    Robust Markov decision processes (MDPs) allow to compute reliable solutions for dynamic decision problems whose evolution is modeled by rewards and partially-known transition probabilities. Unfortunately, accounting for uncertainty in the transition probabilities significantly increases the computational complexity of solving robust MDPs, which severely limits their scalability. This paper describes new efficient algorithms for solving the … Read more

    A simplified treatment of Ramana’s exact dual for semidefinite programming

  • Bruno F. Lourenço
  • Gabor Pataki
    • Categories Convex Optimization, Nonlinear Optimization, Semi-definite Programming Tags , , , ,

    In semidefinite programming the dual may fail to attain its optimal value and there could be a duality gap, i.e., the primal and dual optimal values may differ. In a striking paper, Ramana proposed a polynomial size extended dual that does not have these deficiencies and yields a number of fundamental results in complexity theory. … Read more

    Valid inequalities for quadratic optimisation with domain constraints

  • Laura Galli
  • Adam N. Letchford
    • Categories (Mixed) Integer Nonlinear Programming, Cutting Plane Approaches, Global Optimization

    In 2013, Buchheim and Wiegele introduced a quadratic optimisation problem, in which the domain of each variable is a closed subset of the reals. This problem includes several other important problems as special cases. We study some convex sets and polyhedra associated with the problem, and derive several families of strong valid inequalities. We also … Read more

    Branch-and-Refine for Solving Time-Dependent Problems

  • Armin Fügenschuh
  • Fabian Gnegel
    • Categories Combinatorial Optimization, Integer Programming, Transportation Tags , , ,

    One of the standard approaches for solving time-dependent discrete optimization problems, such as the traveling salesman problem with time-windows or the shortest path problem with time-windows, is to derive a so-called time-indexed formulation. If the problem has an underlying structure that can be described by a graph, the time-indexed formulation is usually based on a … Read more

    An Analysis of Constant Step Size SGD in the Non-convex Regime: Asymptotic Normality and Bias

  • Krishnakumar Balasubramanian
  • Stanislav Volgushev
  • Murat A. Erdogdu
  • Lu Yu
    • Categories Statistics, Stochastic Approaches, Stochastic Programming Tags , ,

    Structured non-convex learning problems, for which critical points have favorable statistical properties, arise frequently in statistical machine learning. Algorithmic convergence and statistical estimation rates are well-understood for such problems. However, quantifying the uncertainty associated with the underlying training algorithm is not well-studied in the non-convex setting. In order to address this short-coming, in this work, … Read more

    Calmness of a perturbed Cournot Oligopoly Game with nonsmooth cost functions

  • Matthieu Maréchal
    • Categories Basic Sciences Applications Tags , ,

    This article deals with the calmness of a solution map of a Cournot Oligopoly Game with nonsmooth cost functions. The fact that the cost functions are not supposed to be differentiable allows for considering cases where some firms have diferent units of production, which have diferent marginal costs. In order to obtain results about the … Read more

    A Line-Search Descent Algorithm for Strict Saddle Functions with Complexity Guarantees

  • Michael J. O'Neill
  • Stephen Wright
    • Categories Unconstrained Optimization Tags , ,

    We describe a line-search algorithm which achieves the best-known worst-case complexity results for problems with a certain “strict saddle” property that has been observed to hold in low-rank matrix optimization problems. Our algorithm is adaptive, in the sense that it makes use of backtracking line searches and does not require prior knowledge of the parameters … Read more

    Modeling Multi-stage Decision Making under Incomplete and Uncertain Information

  • Viktor Bindewald
  • Fabian Dunke
  • Stefan Nickel
    • Categories Applications - OR and Management Sciences, Robust Optimization, Stochastic Programming Tags , , , ,

    We propose a new universal framework for multi-stage decision making under limited information availability. It is developed as part of a larger research project which aims at providing analytical methods to compare and evaluate different models and algorithms for multi-stage decision making. In our setting, we have an open time horizon and limited information about … Read more

    An exact method for influence maximization based on deterministic linear threshold model

  • Eszter Julianna Csókás
  • Tamás Vinkó
    • Categories 0-1 Programming

    Influence maximization (IM) is a challenging combinatorial optimization problem on (social) networks given a diffusion model and limited choice for initial seed nodes. In a recent paper an integer programming formalization of IM using the so-called deterministic linear threshold diffusion model was proposed. In fact, it is a special 0-1 linear program in which the … Read more