(Mixed) Integer Nonlinear Programming

Improving the Performance of MIQP Solvers for Quadratic Programs with Cardinality and Minimum Threshold Constraints: A Semidefinite Program Approach

  • Duan Li
  • Xiaoling Sun
  • Xiaojin Zheng
    • Categories (Mixed) Integer Nonlinear Programming, Second-Order Cone Programming, Semi-definite Programming

    We consider in this paper quadratic programming problems with cardinality and minimum threshold constraints which arise naturally in various real-world applications such as portfolio selection and subset selection in regression. We propose a new semidefinite program (SDP) approach for computing the “best” diagonal decomposition that gives the tightest continuous relaxation of the perspective reformulation. We … Read more

    On the Chvtal-Gomory Closure of a Compact Convex Set

  • Daniel Dadush
  • Santanu S. Dey
  • Juan Pablo Vielma
    • Categories (Mixed) Integer Nonlinear Programming Tags ,

    In this paper, we show that the Chatal-Gomory closure of a compact convex set is a rational polytope. This resolves an open question discussed in Schrijver 1980 and generalizes the same result for the case of rational polytopes (Schrijver 1980), rational ellipsoids (Dey and Vielma 2010) and strictly convex sets (Dadush et. al 2010). In … Read more

    Construction of Risk-Averse Enhanced Index Funds

  • Miguel A. Lejeune
  • Gulay Samatli-Pac
    • Categories (Mixed) Integer Nonlinear Programming, Finance and Economics, Stochastic Programming Tags , , , ,

    We propose a partial replication strategy to construct risk-averse enhanced index funds. Our model takes into account the parameter estimation risk by defining the asset returns and the return covariance terms as random variables. The variance of the index fund return is forced to be below a low-risk threshold with a large probability, thereby limiting … Read more

    Non-linear approximations for solving 3D-packing MIP models: a heuristic approach

  • Giorgio Fasano
    • Categories (Mixed) Integer Linear Programming, (Mixed) Integer Nonlinear Programming, Applications - Science and Engineering Tags , , ,

    This article extends a previous work focused on a mixed integer programming (MIP) based heuristic approach, aimed at solving non-standard three-dimensional problems with additional conditions. The paper that follows considers a mixed integer non-linear (MINLP) reformulation of the previous model, to improve the former heuristic, based on linear relaxation. The approach described herewith is addressed, … Read more

    Semidefinite Relaxations for Non-Convex Quadratic Mixed-Integer Programming

  • Christoph Buchheim
  • Angelika Wiegele
    • Categories (Mixed) Integer Nonlinear Programming, Linear, Cone and Semidefinite Programming, Quadratic Programming Tags , ,

    We present semidefinite relaxations for unconstrained non-convex quadratic mixed-integer optimization problems. These relaxations yield tight bounds and are computationally easy to solve for medium-sized instances, even if some of the variables are integer and unbounded. In this case, the problem contains an infinite number of linear constraints; these constraints are separated dynamically. We use this … Read more

    An Effective Branch-and-Bound Algorithm for Convex Quadratic Integer Programming

  • Christoph Buchheim
  • Alberto Caprara
  • Andrea Lodi
    • Categories (Mixed) Integer Nonlinear Programming, Convex Optimization, Quadratic Programming Tags ,

    We present a branch-and-bound algorithm for minimizing a convex quadratic objective function over integer variables subject to convex constraints. In a given node of the enumeration tree, corresponding to the fixing of a subset of the variables, a lower bound is given by the continuous minimum of the restricted objective function. We improve this bound … Read more

    Inclusion Certificates and Simultaneous Convexification of Functions

  • Mohit Tawarmalani
    • Categories (Mixed) Integer Nonlinear Programming, 0-1 Programming, Global Optimization Theory Tags , , ,

    We define the inclusion certificate as a measure that expresses each point in the domain of a collection of functions as a convex combination of other points in the domain. Using inclusion certificates, we extend the convex extensions theory to enable simultaneous convexification of functions. We discuss conditions under which the domain of the functions … Read more

    A polynomial case of cardinality constrained quadratic optimization problem

  • Jianjun Gao
  • Duan Li
    • Categories (Mixed) Integer Nonlinear Programming, Combinatorial Optimization, Global Optimization Tags , , ,

    We investigate in this paper a fixed parameter polynomial algorithm for the cardinality constrained quadratic optimization problem, which is NP-hard in general. More specifically, we prove that, given a problem of size $n$, the number of decision variables, and $s$, the cardinality, if, for some $0

    Some Results on the Strength of Relaxations of Multilinear Functions

  • Jeff Linderoth
  • James R. Luedtke
  • Mahdi Namazifar
    • Categories (Mixed) Integer Nonlinear Programming, Global Optimization Tags , ,

    We study approaches for obtaining convex relaxations of global optimization problems containing multilinear functions. Specifically, we compare the concave and convex envelopes of these functions with the relaxations that are obtained with a standard relaxation approach, due to McCormick. The standard approach reformulates the problem to contain only bilinear terms and then relaxes each term … Read more

    On semidefinite programming relaxations of maximum k-section

  • Etienne de Klerk
  • Cristian Dobre
  • Renata Sotirov
  • Dmitrii V. Pasechnik
    • Categories (Mixed) Integer Nonlinear Programming, Combinatorial Optimization, Semi-definite Programming Tags , , ,

    We derive a new semidefinite programming bound for the maximum k-section problem. For k=2 (i.e. for maximum bisection), the new bound is least as strong as the well-known bound by Frieze and Jerrum [A. Frieze and M. Jerrum. Improved Approximation Algorithms for MAX k-CUT and MAX BISECTION. Algorithmica, 18(1): 67-81, 1997]. For k > 2 … Read more