Month: February 2019

Interior Point Method on Semi-definite Linear Complementarity Problems using the Nesterov-Todd (NT) Search Direction: Polynomial Complexity and Local Convergence

  • Chee-Khian Sim
    • Categories Semi-definite Programming

    We consider in this paper an infeasible predictor-corrector primal-dual path following interior point algorithm using the Nesterov-Todd (NT) search direction to solve semi-definite linear complementarity problems. Global convergence and polynomial iteration complexity of the algorithm are established. Two sufficient conditions are also given for superlinear convergence of iterates generated by the algorithm. Preliminary numerical results … Read more

    Tangencies and Polynomial Optimization

  • Tiên-So'n Pham
    • Categories Constrained Nonlinear Optimization, Global Optimization Theory Tags , , , , , , , , ,

    Given a polynomial function $f \colon \mathbb{R}^n \rightarrow \mathbb{R}$ and a unbounded basic closed semi-algebraic set $S \subset \mathbb{R}^n,$ in this paper we show that the conditions listed below are characterized exactly in terms of the so-called {\em tangency variety} of $f$ on $S$: (i) The $f$ is bounded from below on $S;$ (ii) The … Read more

    Identifying the Optimal Value Function of a Negative Markov Decision Process: An Integer Programming Approach

  • Amin Dehghanian
    • Categories (Mixed) Integer Linear Programming, Dynamic Programming Tags , , ,

    Mathematical programming formulation to identify the optimal value function of a negative Markov decision process (MDP) is non-convex, non-smooth, and computationally intractable. Also note that other well-known solution methods of MDP do not work properly for a negative MDP. More specifically, the policy iteration diverges, and the value iteration converges but does not provide an … Read more

    Minimum Color-Degree Perfect b -Matchings

  • Mariia Anapolska
  • Christina Büsing
  • Martin Comis
  • Tabea Brandt
    • Categories Dynamic Programming, Graphs and Matroids Tags , , , , ,

    The minimum color-degree perfect b-matching roblem (Col-BM) is a new extension of the perfect b-matching problem to edge-colored graphs. The objective of Col-BM is to minimize the maximum number of differently colored edges in a perfect b-matching that are incident to the same node. We show that Col-BM is NP-hard on bipartite graphs by a … Read more

    Algorithms for the circle packing problem based on mixed-integer DC programming

  • Yoshiko Ikebe
  • Satoru Masuda
  • Takayuki Okuno
    • Categories (Mixed) Integer Nonlinear Programming, Applications - OR and Management Sciences Tags , ,

    Circle packing problems are a class of packing problems which attempt to pack a given set of circles into a container with no overlap. In this paper, we focus on the circle packing problem proposed by L{\’o}pez et.al. The problem is to pack circles of unequal size into a fixed size circular container, so as … Read more

    Single cut and multicut SDDP with cut selection for multistage stochastic linear programs: convergence proof and numerical experiments

  • Michelle Bandarra
  • Vincent Guigues
    • Categories Stochastic Programming

    We introduce a variant of Multicut Decomposition Algorithms (MuDA), called CuSMuDA (Cut Selection for Multicut Decomposition Algorithms), for solving multistage stochastic linear programs that incorporates a class of cut selection strategies to choose the most relevant cuts of the approximate recourse functions. This class contains Level 1 and Limited Memory Level 1 cut selection strategies, … Read more

    An Adaptive Sequential Sample Average Approximation Framework for Solving Two-stage Stochastic Programs

  • Raghu Pasupathy
  • Yongjia Song
    • Categories Stochastic Programming Tags , ,

    We present adaptive sequential SAA (sample average approximation) algorithms to solve large-scale two-stage stochastic linear programs. The iterative algorithm framework we propose is organized into \emph{outer} and \emph{inner} iterations as follows: during each outer iteration, a sample-path problem is implicitly generated using a sample of observations or “scenarios,” and solved only \emph{imprecisely}, to within a … Read more

    Improved Flow-based Formulations for the Skiving Stock Problem

  • Maxence Delorme
  • Manuel Iori
  • John Martinovic
  • Guntram Scheithauer
  • Nico Strasdat
    • Categories (Mixed) Integer Linear Programming, Applications - OR and Management Sciences, Combinatorial Optimization Tags , , ,

    Thanks to the rapidly advancing development of (commercial) MILP software and hardware components, pseudo-polynomial formulations have been established as a powerful tool for solving cutting and packing problems in recent years. In this paper, we focus on the one-dimensional skiving stock problem (SSP), where a given inventory of small items has to be recomposed to … Read more

    Optimal Residential Battery Storage Operations Using Robust Data-driven Dynamic Programming

  • Grani A. Hanasusanto
  • Benjamin Leibowicz
  • Nan Zhang
    • Categories Applications - Science and Engineering Tags , , , , ,

    In this paper, we consider the problem of operating a battery storage unit in a home with a rooftop solar photovoltaic (PV) system so as to minimize expected long-run electricity costs under uncertain electricity usage, PV generation, and electricity prices. Solving this dynamic program using standard techniques is computationally burdensome, and is often complicated by … Read more

    Conflict-Driven Heuristics for Mixed Integer Programming

  • Ambros Gleixner
  • Jakob Witzig
    • Categories (Mixed) Integer Linear Programming

    Two essential ingredients of modern mixed-integer programming (MIP) solvers are diving heuristics that simulate a partial depth-first search in a branch-and-bound search tree and conflict analysis of infeasible subproblems to learn valid constraints. So far, these techniques have mostly been studied independently: primal heuristics under the aspect of finding high-quality feasible solutions early during the … Read more