(Mixed) Integer Nonlinear Programming

Mixed-Integer Bilevel Optimization with Nonconvex Quadratic Lower-Level Problems: Complexity and a Solution Method

  • Immanuel M. Bomze
  • Martin Schmidt
  • Horländer Andreas
    • Categories (Mixed) Integer Linear Programming, (Mixed) Integer Nonlinear Programming Tags , , ,

    We study bilevel problems with a convex quadratic mixed-integer upper-level and a nonconvex quadratic, purely continuous lower-level problem. We prove $\Sigma_p^2$-hardness of this class of problems, derive an iterative lower- and upper-bounding scheme, and show its finiteness and correctness in the sense that it computes globally optimal points or proves infeasibility of the instance. To … Read more

    A Branch-and-Price-and-Cut Algorithm for Discrete Network Design Problems Under Traffic Equilibrium

  • David
  • Michael Levin
    • Categories (Mixed) Integer Nonlinear Programming, Game Theory, Transportation Tags , , , ,

    This study addresses discrete network design problems under traffic equilibrium conditions or DNDPs. Given a network and a budget, DNDPs aim to model all-or-nothing decisions such as link addition to minimize network congestion effects. Congestion is measured using traffic equilibrium theory where link travel times are modeled as convex flow-dependent functions and where users make … Read more

    Unboundedness in Bilevel Optimization

  • Bárbara Rodrigues
  • Margarida Carvalho
  • Miguel F. Anjos
    • Categories (Mixed) Integer Nonlinear Programming, Nonlinear Optimization, Polyhedra Tags , , ,

    Bilevel optimization has garnered growing interest over the past decade. However, little attention has been paid to detecting and dealing with unboundedness in these problems, with most research assuming a bounded high-point relaxation. In this paper, we address unboundedness in bilevel optimization by studying its computational complexity and developing algorithmic approaches to detect it. We … Read more

    Sparse Principal Component Analysis with Non-Oblivious Adversarial Perturbations

  • Yuqing He
  • Guanyi Wang
  • Yu Yang
    • Categories (Mixed) Integer Nonlinear Programming Tags , ,

    Sparse Principal Component Analysis (sparse PCA) is a fundamental dimension-reduction tool that enhances interpretability in various high-dimensional settings. An important variant of sparse PCA studies the scenario when samples are adversarially perturbed. Notably, most existing statistical studies on this variant focus on recovering the ground truth and verifying the robustness of classical algorithms when the … Read more

    Generator Subadditive Functions for Mixed-Integer Programs

  • Gustavo Angulo
  • Burak Kocuk
  • Diego Moran Ramirez
    • Categories (Mixed) Integer Nonlinear Programming, Cone Programming, Integer Programming Tags , , , ,

    For equality-constrained linear mixed-integer programs (MIP) defined by rational data, it is known that the subadditive dual is a strong dual and that there exists an optimal solution of a particular form, termed generator subadditive function. Motivated by these results, we explore the connection between Lagrangian duality, subadditive duality and generator subadditive functions for general … Read more

    Missing Value Imputation via Mathematical Optimization with Instance-and-Feature Neighborhoods

  • Yuichi Takano
    • Categories (Mixed) Integer Nonlinear Programming, Optimization in Data Science Tags , , , ,

    Datasets collected for analysis often contain a certain amount of incomplete instances, where some feature values are missing. Since many statistical analyses and machine learning algorithms depend on complete datasets, missing values need to be imputed in advance. Bertsimas et al. (2018) proposed a high-performance method that combines machine learning and mathematical optimization algorithms for … Read more

    Spanning and Splitting: Integer Semidefinite Programming for the Quadratic Minimum Spanning Tree Problem

  • Frank de Meijer
  • Melanie Siebenhofer
  • Renata Sotirov
  • Angelika Wiegele
    • Categories (Mixed) Integer Nonlinear Programming, Network Optimization, Semi-definite Programming Tags , , , ,

    In the quadratic minimum spanning tree problem (QMSTP) one wants to find the minimizer of a quadratic function over all possible spanning trees of a graph. We give two formulations of the QMSTP as mixed-integer semidefinite programs exploiting the algebraic connectivity of a graph. Based on these formulations, we derive a doubly nonnegative relaxation for … Read more

    A graphical framework for global optimization of mixed-integer nonlinear programs

  • Danial Davarnia
    • Categories (Mixed) Integer Nonlinear Programming, Global Optimization Applications, Global Optimization Theory Tags , , , , ,

    While mixed-integer linear programming and convex programming solvers have advanced significantly over the past several decades, solution technologies for general mixed-integer nonlinear programs (MINLPs) have yet to reach the same level of maturity. Various problem structures across different application domains remain challenging to model and solve using modern global solvers, primarily due to the lack … Read more

    Energy-efficient Timetables for Railway Traffic: Incorporating DC Power Models

  • Tobias Kuen
  • Robert Burlacu
  • Patrick Gemander
  • Jorge Weston
    • Categories (Mixed) Integer Nonlinear Programming, Cutting Plane Approaches, Transportation Tags , , ,

    Efficient operation of underground railway systems is critical not only for maintaining punctual service but also for minimizing energy consumption, a key factor in reducing operational costs and environmental impact. To evaluate the energy consumption of the timetables, this paper delves into the development of mathematical models to accurately represent energy dynamics within the underground … Read more

    The Augmented Factorization Bound for Maximum-Entropy Sampling

  • Yongchun Li
    • Categories (Mixed) Integer Nonlinear Programming, Combinatorial Optimization, Constrained Nonlinear Optimization

    The maximum-entropy sampling problem (MESP) aims to select the most informative principal submatrix of a prespecified size from a given covariance matrix. This paper proposes an augmented factorization bound for MESP based on concave relaxation. By leveraging majorization and Schur-concavity theory, we demonstrate that this new bound dominates the classic factorization bound of Nikolov (2015) and a recent … Read more