Dantzig Wolfe decomposition and objective function convexification for binary quadratic problems: the cardinality constrained quadratic knapsack case

  • Alberto Ceselli
  • Lucas Létocart
  • Emiliano Traversi
    • Categories (Mixed) Integer Nonlinear Programming, Combinatorial Optimization, Quadratic Programming Tags , , ,

    The purpose of this paper is to provide strong reformulations for binary quadratic problems. We propose a first methodological analysis on a family of reformulations combining Dantzig-Wolfe decomposition and Quadratic Convex Reformulation principles. As a representative case study, we apply them to a cardinality constrained quadratic knapsack problem, providing extensive experimental insights. We show that … Read more

    Random Sampling and Machine Learning to Understand Good Decompositions

  • Saverio Basso
  • Alberto Ceselli
  • Andrea Tettamanzi
    • Categories (Mixed) Integer Linear Programming, Data-Mining Tags , ,

    Motivated by its implications in the development of general purpose solvers for decomposable Mixed Integer Programs (MIP), we address a fundamental research question, that is to assess if good decomposition patterns can be consistently found by looking only at static properties of MIP input instances, or not. We adopt a data driven approach, devising a … Read more

    A randomized method for smooth convex minimization, motivated by probability maximization

  • Csaba I. Fábián
  • Tamas Szantai
    • Categories Nonlinear Optimization, Stochastic Programming Tags , ,

    We propose a randomized gradient method – or a randomized cutting-plane method from a dual viewpoint. From the primal viewpoint, our method bears a resemblance to the stochastic approximation family. But in contrast to stochastic approximation, the present method builds a model problem. CitationKecskemet College, Pallasz Athene University. Izsaki ut 10, 6000 Kecskemet, Hungary; and … Read more

    Optimal scenario generation and reduction in stochastic programming

  • René Henrion
  • Werner Romisch
    • Categories Semi-infinite Programming, Stochastic Programming Tags , , ,

    Scenarios are indispensable ingredients for the numerical solution of stochastic optimization problems. Earlier approaches for optimal scenario generation and reduction are based on stability arguments involving distances of probability measures. In this paper we review those ideas and suggest to make use of stability estimates based on distances containing minimal information, i.e., on data appearing … Read more

    An Active-Set Algorithmic Framework for Non-Convex Optimization Problems over the Simplex

  • Andrea Cristofari
  • Marianna De Santis
  • Stefano Lucidi
  • Francesco Rinaldi
    • Categories Nonlinear Optimization

    In this paper, we describe a new active-set algorithmic framework for minimizing a non-convex function over the unit simplex. At each iteration, the method makes use of a rule for identifying active variables (i.e., variables that are zero at a stationary point) and specific directions (that we name active-set gradient related directions) satisfying a new … Read more

    Symmetric ADMM with Positive-Indefinite Proximal Regularization for Linearly Constrained Convex Optimization

  • Bin Gao
  • Feng Ma
    • Categories Complementarity and Variational Inequalities, Convex Optimization, Parallel Algorithms Tags , , ,

    The proximal ADMM which adds proximal regularizations to ADMM’s subproblems is a popular and useful method for linearly constrained separable convex problems, especially its linearized case. A well-known requirement on guaranteeing the convergence of the method in the literature is that the proximal regularization must be positive semidefinite. Recently it was shown by He et … Read more

    Direct Search Methods on Reductive Homogeneous Spaces

  • Dreisigmeyer David
    • Categories Nonlinear Optimization, Nonsmooth Optimization Tags ,

    Direct search methods are mainly designed for use in problems with no equality constraints. However, there are many instances where the feasible set is of measure zero in the ambient space and no mesh point lies within it. There are methods for working with feasible sets that are (Riemannian) manifolds, but not all manifolds are … Read more

    Polynomial-Time Methods to Solve Unimodular Quadratic Programs With Performance Guarantees

  • Edwin K.P. Chong
  • Hans D Mittelmann
  • Shankarachary Ragi
    • Categories Applications - Science and Engineering Tags , , , ,

    We develop polynomial-time heuristic methods to solve unimodular quadratic programs (UQPs) approximately, which are known to be NP-hard. In the UQP framework, we maximize a quadratic function of a vector of complex variables with unit modulus. Several problems in active sensing and wireless communication applications boil down to UQP. With this motivation, we present three … Read more

    A block symmetric Gauss-Seidel decomposition theorem for convex composite quadratic programming and its applications

  • Xudong Li
  • Defeng Sun
  • Kim-Chuan Toh
    • Categories Nonsmooth Optimization, Quadratic Programming Tags , ,

    For a symmetric positive semidefinite linear system of equations $\mathcal{Q} {\bf x} = {\bf b}$, where ${\bf x} = (x_1,\ldots,x_s)$ is partitioned into $s$ blocks, with $s \geq 2$, we show that each cycle of the classical block symmetric Gauss-Seidel (block sGS) method exactly solves the associated quadratic programming (QP) problem but added with an … Read more

    Complex Number Formulation and Convex Relaxations for Aircraft Conflict Resolution

  • Hassan L. Hijazi
  • David Rey
    • Categories (Mixed) Integer Nonlinear Programming, Airline Optimization, Global Optimization Applications Tags , , , ,

    We present a novel complex number formulation along with tight convex relaxations for the aircraft conflict resolution problem. Our approach combines both speed and heading control and provides global optimality guarantees despite non-convexities in the feasible region. As a side result, we present a new characterization of the conflict separation condition in the form of … Read more