(Mixed) Integer Nonlinear Programming

On two relaxations of quadratically-constrained cardinality minimization

  • Dennis Wei
    • Categories (Mixed) Integer Nonlinear Programming, Approximation Algorithms, Branch and Cut Algorithms Tags , , , ,

    This paper considers a quadratically-constrained cardinality minimization problem with applications to digital filter design, subset selection for linear regression, and portfolio selection. Two relaxations are investigated: the continuous relaxation of a mixed integer formulation, and an optimized diagonal relaxation that exploits a simple special case of the problem. For the continuous relaxation, an absolute upper … Read more

    On Perspective Functions and Vanishing Constraints in Mixed-Integer Nonlinear Optimal Control

  • Michael N. Jung
  • Christian Kirches
  • Sebastian Sager
    • Categories (Mixed) Integer Nonlinear Programming, Systems governed by Differential Equations Optimization Tags ,

    Logical implications appear in a number of important mixed-integer nonlinear optimal control problems (MIOCPs). Mathematical optimization offers a variety of different formulations that are equivalent for boolean variables, but result in different relaxations. In this article we give an overview over a variety of different modeling approaches, including outer versus inner convexification, generalized disjunctive programming, … Read more

    Threshold Boolean Form for Joint Probabilistic Constraints with Random Technology Matrix

  • Alexander Kogan
  • Miguel A. Lejeune
    • Categories (Mixed) Integer Nonlinear Programming, Data-Mining, Stochastic Programming Tags , , , , ,

    We develop a new modeling and exact solution method for stochastic programming problems that include a joint probabilistic constraint in which the multirow random technology matrix is discretely distributed. We binarize the probability distribution of the random variables in such a way that we can extract a threshold partially defined Boolean function (pdBf) representing the … Read more

    An Outer-Inner Approximation for separable MINLPs

  • Pierre Bonami
  • Hassan L. Hijazi
  • Adam Ouorou
    • Categories (Mixed) Integer Nonlinear Programming, Optimization Software and Modeling Systems Tags , ,

    A common structure in convex mixed-integer nonlinear programs is separable nonlinear functions. In the presence of such structures, we propose three improvements to the outer approximation algorithms. The first improvement is a simple extended formulation, the second is a refined outer approximation, and the third is a heuristic inner approximation of the feasible region. These … Read more

    On valid inequalities for quadratic programming with continuous variables and binary indicators

  • Hongbo Dong
  • Jeff Linderoth
    • Categories (Mixed) Integer Nonlinear Programming, Global Optimization Theory, Quadratic Programming Tags ,

    In this paper we study valid inequalities for a fundamental set that involves a continuous vector variable x in [0,1]^n, its associated quadratic form x x’ and its binary indicators. This structure appears when deriving strong relaxations for mixed integer quadratic programs (MIQPs). We treat valid inequalities for this set as lifted from QPB, which … Read more

    Graver basis and proximity techniques for block-structured separable convex integer minimization problems

  • Raymond Hemmecke
  • Matthias Köppe
  • Robert Weismantel
    • Categories (Mixed) Integer Nonlinear Programming Tags , , , , , ,

    We consider N-fold 4-block decomposable integer programs, which simultaneously generalize N-fold integer programs and two-stage stochastic integer programs with N scenarios. In previous work [R. Hemmecke, M. Koeppe, R. Weismantel, A polynomial-time algorithm for optimizing over N-fold 4-block decomposable integer programs, Proc. IPCO 2010, Lecture Notes in Computer Science, vol. 6080, Springer, 2010, pp. 219–229], … Read more

    Aircraft deconfliction with speed regulation: new models from mixed-integer optimization

  • Sonia Cafieri
  • Nicolas Durand
    • Categories (Mixed) Integer Nonlinear Programming, Applications - OR and Management Sciences, Global Optimization Tags , , , , ,

    Detecting and solving aircraft conflicts, which occur when aircraft sharing the same airspace are too close to each other according to their predicted trajectories, is a crucial problem in Air Traffic Management. We focus on mixed-integer optimization models based on speed regulation. We first solve the problem to global optimality by means of an exact … Read more

    A conic representation of the convex hull of disjunctive sets and conic cuts for integer second order cone optimization

  • Pietro Belotti
  • Julio C. Góez
  • Imre Pólik
  • Ted K. Ralphs
  • Tamás Terlaky
    • Categories (Mixed) Integer Nonlinear Programming, Second-Order Cone Programming Tags , ,

    We study the convex hull of the intersection of a convex set E and a linear disjunction. This intersection is at the core of solution techniques for Mixed Integer Conic Optimization. We prove that if there exists a cone K (resp., a cylinder C) that has the same intersection with the boundary of the disjunction … Read more

    An Exact Algorithm for Quadratic Integer Minimization using Ellipsoidal Relaxations

  • Christoph Buchheim
  • Marianna De Santis
  • Laura Palagi
  • Mauro Piacentini
    • Categories (Mixed) Integer Nonlinear Programming, Global Optimization, Quadratic Programming Tags ,

    We propose a branch-and-bound algorithm for minimizing a not necessarily convex quadratic function over integer variables. The algorithm is based on lower bounds computed as continuous minima of the objective function over appropriate ellipsoids. In the nonconvex case, we use ellipsoids enclosing the feasible region of the problem. In spite of the nonconvexity, these minima … Read more

    Sparse Approximation via Penalty Decomposition Methods

  • Zhaosong Lu
  • Yong Zhang
    • Categories (Mixed) Integer Nonlinear Programming, Constrained Nonlinear Optimization, Nonsmooth Optimization Tags , , , , ,

    In this paper we consider sparse approximation problems, that is, general $l_0$ minimization problems with the $l_0$-“norm” of a vector being a part of constraints or objective function. In particular, we first study the first-order optimality conditions for these problems. We then propose penalty decomposition (PD) methods for solving them in which a sequence of … Read more