linearization

A Reformulation Technique to Solve Polynomial Optimization Problems with Separable Objective Functions of Bounded Integer Variables

  • Andrew C. Trapp
  • Pitchaya Wiratchotisatian
    • Categories (Mixed) Integer Nonlinear Programming, Global Optimization Theory, Nonlinear Optimization Tags , , ,

    Real-world problems are often nonconvex and involve integer variables, representing vexing challenges to be tackled using state-of-the-art solvers. We introduce a mathematical identity-based reformulation of a class of polynomial integer nonlinear optimization (PINLO) problems using a technique that linearizes polynomial functions of separable and bounded integer variables of any degree. We also introduce an alternative … Read more

    Inductive Linearization for Binary Quadratic Programs with Linear Constraints: A Computational Study

  • Sven Mallach
    • Categories (Mixed) Integer Nonlinear Programming, 0-1 Programming, Quadratic Programming Tags , , ,

    The computational performance of inductive linearizations for binary quadratic programs in combination with a mixed-integer programming solver is investigated for several combinatorial optimization problems and established benchmark instances. Apparently, a few of these are solved to optimality for the first time. Citation preprint (no internal series / number): University of Bonn, Germany June 11, 2021 … Read more

    Mathematical Models and Approximate Solution Approaches for the Stochastic Bin Packing Problem

  • John Martinovic
  • Maximilian Selch
    • Categories 0-1 Programming, Combinatorial Optimization, Stochastic Programming Tags , , , , ,

    We consider the (single-stage) stochastic bin packing problem (SBPP) which is based on a given list of items the sizes of which are represented by stochastically independent random variables. The SBPP requires to determine the minimum number of unit capacity bins needed to pack all the items, such that for each bin the probability of … Read more

    Robust Convex Optimization: A New Perspective That Unifies And Extends

  • Dimitris Bertsimas
  • Dick den Hertog
  • Jean Pauphilet
  • Jianzhe Zhen
    • Categories Convex Optimization, Robust Optimization Tags , , ,

    Robust convex constraints are difficult to handle, since finding the worst-case scenario is equivalent to maximizing a convex function. In this paper, we propose a new approach to deal with such constraints that unifies approaches known in the literature and extends them in a significant way. The extension is either obtaining better solutions than the … Read more

    A Classifier to Decide on the Linearization of Mixed-Integer Quadratic Problems in CPLEX

  • Pierre Bonami
  • Andrea Lodi
  • Giulia Zarpellon
    • Categories (Mixed) Integer Linear Programming, Integer Programming, Optimization Software Design Principles Tags , , ,

    We translate the algorithmic question of whether to linearize convex Mixed-Integer Quadratic Programming problems (MIQPs) into a classification task, and use machine learning (ML) techniques to tackle it. We represent MIQPs and the linearization decision by careful target and feature engineering. Computational experiments and evaluation metrics are designed to further incorporate the optimization knowledge in … Read more

    Integrality of Linearizations of Polynomials over Binary Variables using Additional Monomials

  • Christopher Hojny
  • Marc E. Pfetsch
  • Matthias Walter
    • Categories (Mixed) Integer Nonlinear Programming, Polyhedra Tags , ,

    Polynomial optimization problems over binary variables can be expressed as integer programs using a linearization with extra monomials in addition to those arising in the given polynomial. We characterize when such a linearization yields an integral relaxation polytope, generalizing work by Del Pia and Khajavirad (SIAM Journal on Optimization, 2018) and Buchheim, Crama and Rodríguez-Heck … Read more

    The Multi-Hour Bandwidth Packing Problem with Queuing Delays: Bounds and Exact Solution Approach

  • Arjun Bhardwaj
  • Niraj Sinha
  • Navneet Vidyarthi
    • Categories Applications - OR and Management Sciences Tags , , , , , , ,

    The multi-hour bandwidth packing problem arises in telecommunication networks that span several time horizon. The problem seeks to select and route a set of messages from a given list of messages with prespecified requirement on demand for bandwidth under time varying traffic conditions on an undirected communication network such that the total profit is maximized. … Read more

    Linearizing the Method of Conjugate Gradients

  • Serge Gratton
  • David Titley-Peloquin
  • Philippe L. Toint
  • Jean Tshimanga Ilunga
    • Categories Basic Sciences Applications, Unconstrained Optimization Tags , , , ,

    The method of conjugate gradients (CG) is widely used for the iterative solution of large sparse systems of equations $Ax=b$, where $A\in\Re^{n\times n}$ is symmetric positive definite. Let $x_k$ denote the $k$–th iterate of CG. In this paper we obtain an expression for $J_k$, the Jacobian matrix of $x_k$ with respect to $b$. We use … Read more

    A LINEAR TIME ALGORITHM FOR THE KOOPMANS-BECKMANN QAP LINEARIZATION AND RELATED PROBLEMS

  • Santosh N. Kabadi
  • Abraham Punnen
    • Categories Combinatorial Optimization Tags , ,

    An instance of the quadratic assignment problem (QAP) with cost matrix Q is said to be linearizable if there exists an instance of the linear assignment problem (LAP) with cost matrix C such that for each assignment, the QAP and LAP objective function values are identical. The QAP linearization problem can be solved in O(n4) … Read more

    Linearized Alternating Direction Method with Gaussian Back Substitution for Separable Convex Programming

  • Bingsheng He
  • Xiao-Ming Yuan
    • Categories Convex Optimization Tags , , , ,

    Recently, we have proposed to combine the alternating direction method (ADM) with a Gaussian back substitution procedure for solving the convex minimization model with linear constraints and a general separable objective function, i.e., the objective function is the sum of many functions without coupled variables. In this paper, we further study this topic and show … Read more