(Mixed) Integer Nonlinear Programming

On Tractable Convex Relaxations of Standard Quadratic Optimization Problems under Sparsity Constraints

  • Immanuel M. Bomze
  • Bo Peng
  • Yuzhou Qiu
  • E. Alper Yildirim
    • Categories (Mixed) Integer Nonlinear Programming, Quadratic Programming, Semi-definite Programming Tags , , , ,

    Standard quadratic optimization problems (StQPs) provide a versatile modelling tool in various applications. In this paper, we consider StQPs with a hard sparsity constraint, referred to as sparse StQPs. We focus on various tractable convex relaxations of sparse StQPs arising from a mixed-binary quadratic formulation, namely, the linear optimization relaxation given by the reformulation-linearization technique, … Read more

    A Computational Study for Piecewise Linear Relaxations of Mixed-Integer Nonlinear Programs

  • Kristin Braun
  • Robert Burlacu
    • Categories (Mixed) Integer Nonlinear Programming Tags , , ,

    Solving mixed-integer nonlinear problems by means of piecewise linear relaxations can be a reasonable alternative to the commonly used spatial branch-and-bound. These relaxations have been modeled by various mixed-integer models in recent decades. The idea is to exploit the availability of mature solvers for mixed-integer problems. In this work, we compare different reformulations in terms … Read more

    A hybrid branch-and-bound and interior-point algorithm for stochastic mixed-integer nonlinear second-order cone programming

  • Baha Alzalg
    • Categories (Mixed) Integer Nonlinear Programming, Cutting Plane Approaches, Second-Order Cone Programming Tags , , , ,

    One of the chief attractions of stochastic mixed-integer second-order cone programming is its diverse applications, especially in engineering (Alzalg and Alioui, {\em IEEE Access}, 10:3522-3547, 2022). The linear and nonlinear versions of this class of optimization problems are still unsolved yet. In this paper, we develop a hybrid optimization algorithm coupling branch-and-bound and primal-dual interior-point … Read more

    Information Complexity of Mixed-integer Convex Optimization

  • Amitabh Basu
  • Hongyi Jiang
  • Phillip Kerger
  • Marco Molinaro
    • Categories (Mixed) Integer Nonlinear Programming, Convex and Nonsmooth Optimization, Convex Optimization Tags , , ,

    We investigate the information complexity of mixed-integer convex optimization under different types of oracles. We establish new lower bounds for the standard first-order oracle, improving upon the previous best known lower bound. This leaves only a lower order linear term (in the dimension) as the gap between the lower and upper bounds. This is derived … Read more

    Switching Time Optimization for Binary Quantum Optimal Control

  • Xinyu Fei
  • Lucas Brady
  • Jeffrey Larson
  • Sven Leyffer
  • Siqian Shen
    • Categories (Mixed) Integer Nonlinear Programming, Basic Sciences Applications, Control Applications Tags , ,

    Quantum optimal control is a technique for controlling the evolution of a quantum system and has been applied to a wide range of problems in quantum physics. We study a binary quantum control optimization problem, where control decisions are binary-valued and the problem is solved in diverse quantum algorithms. In this paper, we utilize classical … Read more

    Gain Confidence, Reduce Disappointment: A New Approach to Cross-Validation for Sparse Regression

  • Ryan Cory-Wright
  • Andrés Gómez
    • Categories (Mixed) Integer Nonlinear Programming, Data Science Algorithms

    Ridge regularized sparse linear regression involves selecting a subset of features that explains the relationship between a high-dimensional design matrix and an output vector in an interpretable manner. To select the sparsity and robustness of linear regressors, techniques like leave-one-out cross-validation are commonly used for hyperparameter tuning. However, cross-validation typically increases the cost of sparse … Read more

    Distributionally Risk-Receptive and Robust Multistage Stochastic Integer Programs and Two-player Interdiction Games with(out) Decision-Dependent Uncertainty

  • Sumin Kang
  • Manish Bansal
    • Categories (Mixed) Integer Nonlinear Programming, Robust Optimization, Stochastic Programming Tags , , , , , ,

    In this paper, we study distributionally risk-receptive and distributionally robust (or risk-averse) multistage stochastic mixed-integer programs (denoted by DRR- and DRA-MSIPs). These frameworks are useful for optimization problems under uncertainty where the focus is on analyzing outcomes based on multiple decision-makers’ differing perspectives, such as interdiction problems that are attacker-defender games having non-cooperative players. We … Read more

    Using dual relaxations in multiobjective mixed-integer quadratic programming

  • Marianna De Santis
  • Gabriele Eichfelder
  • Daniele Patria
  • Leo Warnow
    • Categories (Mixed) Integer Nonlinear Programming, Multi-Criteria Optimization Tags , , ,

    We present a branch-and-bound method for multiobjective mixed-integer convex quadratic programs that computes a superset of efficient integer assignments and a coverage of the nondominated set. The method relies on outer approximations of the upper image set of continuous relaxations. These outer approximations are obtained addressing the dual formulations of specific subproblems where the values … Read more

    Compressed Sensing: A Discrete Optimization Approach

  • Dimitris Bertsimas
  • Nicholas A. G. Johnson
    • Categories (Mixed) Integer Nonlinear Programming, Second-Order Cone Programming, Statistics Tags , , , ,

    We study the Compressed Sensing (CS) problem, which is the problem of finding the most sparse vector that satisfies a set of linear measurements up to some numerical tolerance. CS is a central problem in Statistics, Operations Research and Machine Learning which arises in applications such as signal processing, data compression, image reconstruction, and multi-label … Read more