(Mixed) Integer Nonlinear Programming

Convex Relaxations of Non-Convex Mixed Integer Quadratically Constrained Programs: Extended Formulations

  • Pierre Bonami
  • Jon Lee
  • Anureet Saxena
    • Categories (Mixed) Integer Nonlinear Programming, Global Optimization Tags , ,

    This paper addresses the problem of generating strong convex relaxations of Mixed Integer Quadratically Constrained Programming (MIQCP) problems. MIQCP problems are very difficult because they combine two kinds of non-convexities: integer variables and non-convex quadratic constraints. To produce strong relaxations of MIQCP problems, we use techniques from disjunctive programming and the lift-and-project methodology. In particular, … Read more

    Branching and bounds tightening techniques for non-convex MINLP

  • Pietro Belotti
  • Jon Lee
  • Leo Liberti
  • François Margot
    • Categories (Mixed) Integer Nonlinear Programming, Global Optimization Tags , , ,

    Many industrial problems can be naturally formulated using Mixed Integer Nonlinear Programming (MINLP). Motivated by the demand for Open-Source solvers for real-world MINLP problems, we have developed a spatial Branch-and-Bound software package named COUENNE (Convex Over- and Under-ENvelopes for Nonlinear Estimation). In this paper, we present the structure of couenne and discuss in detail our … Read more

    The Submodular Knapsack Polytope

  • Alper Atamturk
  • Vishnu Narayanan
    • Categories (Mixed) Integer Nonlinear Programming, Cutting Plane Approaches, Robust Optimization

    The submodular knapsack set is the discrete lower level set of a submodular function. The modular case reduces to the classical linear 0-1 knapsack set. One motivation for studying the submodular knapsack polytope is to address 0-1 programming problems with uncertain coefficients. Under various assumptions, a probabilistic constraint on 0-1 variables can be modeled as … Read more

    Perspective Reformulations of Mixed Integer Nonlinear Programs with Indicator Variables

  • Oktay Gunluk
  • Jeff Linderoth
    • Categories (Mixed) Integer Nonlinear Programming

    We study mixed integer nonlinear programs (MINLP)s that are driven by a collection of indicator variables where each indicator variable controls a subset of the decision variables. An indicator variable, when it is “turned off”, forces some of the decision variables to assume fixed values, and, when it is “turned on”, forces them to belong … Read more

    Nonlinear Optimization over a Weighted Independence System

  • Shmuel Onn
  • Robert Weismantel
  • Jon Lee
    • Categories (Mixed) Integer Nonlinear Programming, Combinatorial Optimization Tags , ,

    We consider the problem of optimizing a nonlinear objective function over a weighted independence system presented by a linear-optimization oracle. We provide a polynomial-time algorithm that determines an r-best solution for nonlinear functions of the total weight of an independent set, where r is a constant that depends on certain Frobenius numbers of the individual … Read more

    Water Network Design by MINLP

  • Cristiana Bragalli
  • Claudia D'Ambrosio
  • Jon Lee
  • Andrea Lodi
  • Paolo Toth
    • Categories (Mixed) Integer Nonlinear Programming, Civil and Environmental Engineering

    We propose a solution method for a water-network optimization problem using a nonconvex continuous NLP (nonlinear programming) relaxation and a MINLP (mixed integer nonlinear programming) search. Our approach employs a relatively simple and accurate model that pays some attention to the requirements of the solvers that we employ. Our view is that in doing so, … Read more

    Disjunctive Cuts for Non-Convex Mixed Integer Quadratically Constrained Programs

  • Pierre Bonami
  • Jon Lee
  • Anureet Saxena
    • Categories (Mixed) Integer Nonlinear Programming, Constrained Nonlinear Optimization, Global Optimization Tags , , , ,

    This paper addresses the problem of generating strong convex relaxations of Mixed Integer Quadratically Constrained Programming (MIQCP) problems. MIQCP problems are very difficult because they combine two kinds of non-convexities: integer variables and non-convex quadratic constraints. To produce strong relaxations of MIQCP problems, we use techniques from disjunctive programming and the lift-and-project methodology. In particular, … Read more

    Building separating concentric balls to solve a multi-instance classification problem

  • Emilio Carrizosa
  • José F. Gordillo
  • Frank Plastria
    • Categories (Mixed) Integer Nonlinear Programming, Data-Mining, Meta Heuristics Tags , , ,

    In this work, we consider a classification problem where the objects to be classified are bags of instances which are vectors measuring d different attributes. The classification rule is defined in terms of a ball, whose center and radius are the parameters to be computed. Given a bag, it is assigned to the positive class … Read more

    Hilbert’s Nullstellensatz and an Algorithm for Proving Combinatorial Infeasibility

  • Jesús A. De Loera
  • Jon Lee
  • Peter Malkin
  • Susan Margulies
    • Categories (Mixed) Integer Nonlinear Programming, Combinatorial Optimization, Graphs and Matroids Tags , ,

    Systems of polynomial equations over an algebraically-closed field K can be used to concisely model many combinatorial problems. In this way, a combinatorial problem is feasible (e.g., a graph is 3-colorable, hamiltonian, etc.) if and only if a related system of polynomial equations has a solution over K. In this paper, we investigate an algorithm … Read more

    Polymatroids and Mean-Risk Minimization in Discrete Optimization

  • Alper Atamturk
  • Vishnu Narayanan
    • Categories (Mixed) Integer Nonlinear Programming, Graphs and Matroids, Integer Programming Tags , , ,

    In financial markets high levels of risk are associated with large returns as well as large losses, whereas with lower levels of risk, the potential for either return or loss is small. Therefore, risk management is fundamentally concerned with finding an optimal trade-off between risk and return matching an investor’s risk tolerance. Managing risk is … Read more