(Mixed) Integer Nonlinear Programming

Mixed-Integer Quadratic Optimization and Iterative Clustering Techniques for Semi-Supervised Support Vector Machines

  • Martin Schmidt
  • Jan Pablo Burgard
  • Maria Eduarda Pinheiro
    • Categories (Mixed) Integer Nonlinear Programming, Data Science Algorithms, Data Science Applications Tags , , ,

    Among the most famous algorithms for solving classification problems are support vector machines (SVMs), which find a separating hyperplane for a set of labeled data points. In some applications, however, labels are only available for a subset of points. Furthermore, this subset can be non-representative, e.g., due to self-selection in a survey. Semi-supervised SVMs tackle … Read more

    An approximation algorithm for multi-objective mixed-integer convex optimization

  • Ina Lammel
  • Karl-Heinz Küfer
  • Philipp Süss
    • Categories (Mixed) Integer Nonlinear Programming, Multi-Criteria Optimization Tags , ,

    In this article we introduce an algorithm that approximates Pareto fronts of multiobjective mixed-integer convex optimization problems. The algorithm constructs an inner and outer approximation of the front exploiting the convexity of the patches and is applicable to problems with an arbitrary number of criteria. In the algorithm, the problem is decomposed into patches, which … Read more

    Submodular maximization and its generalization through an intersection cut lens

  • Liding Xu
  • Leo Liberti
    • Categories (Mixed) Integer Nonlinear Programming, Cutting Plane Approaches Tags , , , , ,

    We study a mixed-integer set \(\mathcal{S}:=\{(x,t) \in \{0,1\}^n \times \mathbb{R}: f(x) \ge t\}\) arising in the submodular maximization problem, where \(f\) is a submodular function defined over \(\{0,1\}^n\). We use intersection cuts to tighten a polyhedral outer approximation of \(\mathcal{S}\). We construct a continuous extension \(\mathsf{F}\) of \(f\), which is convex and defined over the … Read more

    A Test Instance Generator for Multiobjective Mixed-integer Optimization

  • Gabriele Eichfelder
  • Tobias Gerlach
  • Leo Warnow
    • Categories (Mixed) Integer Nonlinear Programming, Multi-Criteria Optimization Tags , , ,

    Application problems can often not be solved adequately by numerical algorithms as several difficulties might arise at the same time. When developing and improving algorithms which hopefully allow to handle those difficulties in the future, good test instances are required. These can then be used to detect the strengths and weaknesses of different algorithmic approaches. … Read more

    Variable Selection for Kernel Two-Sample Tests

  • Jie Wang
  • Santanu S. Dey
  • Yao Xie
    • Categories (Mixed) Integer Nonlinear Programming, Optimization in Data Science Tags , ,

    We consider the variable selection problem for two-sample tests, aiming to select the most informative variables to distinguish samples from two groups. To solve this problem, we propose a framework based on the kernel maximum mean discrepancy (MMD). Our approach seeks a group of variables with a pre-specified size that maximizes the variance-regularized MMD statistics. … Read more

    A classification method based on a cloud of spheres

  • Tiago Dias
  • Paula Alexandra Amaral
    • Categories (Mixed) Integer Nonlinear Programming, Data Science Algorithms, Quadratic Programming Tags , , ,

    In this article we propose a binary classification model to distinguish a specific class that corresponds to a characteristic that we intend to identify (fraud, spam, disease). The classification model is based on a cloud of spheres that circumscribes the points of the class to be identified. It is intended to build a model based … Read more

    Enhancements of Discretization Approaches for Non-Convex Mixed-Integer Quadratically Constraint Quadratic Programming: Part II

  • Ben Beach
  • Robert Burlacu
  • Andreas Bärmann
  • Lukas Hager
  • Robert Hildebrand
    • Categories (Mixed) Integer Nonlinear Programming, Nonlinear Optimization, Quadratic Programming Tags , , , ,

    Abstract. This is Part II of a study on mixed-integer programming (MIP) relaxation techniques for the solution of non-convex mixed-integer quadratically constrained quadratic programs (MIQCQPs). We set the focus on MIP relaxation methods for non-convex continuous variable products and extend the well-known MIP relaxation normalized multiparametric disaggregation technique (NMDT), applying a sophisticated discretization to both … Read more

    Gas Transport Network Optimization: Mixed-Integer Nonlinear Models

  • Falk M. Hante
  • Martin Schmidt
    • Categories (Mixed) Integer Linear Programming, (Mixed) Integer Nonlinear Programming, Applications - Science and Engineering Tags , , ,

    Although modern societies strive towards energy systems that are entirely based on renewable energy carriers, natural gas is still one of the most important energy sources. This became even more obvious in Europe with Russia’s 2022 war against the Ukraine and the resulting stop of gas supplies from Russia. Besides that it is very important … Read more

    Tightening Quadratic Convex Relaxations for the AC Optimal Transmission Switching Problem

  • Cheng Guo
  • Harsha Nagarajan
  • Merve Bodur
    • Categories (Mixed) Integer Nonlinear Programming Tags , , ,

    The Alternating Current Optimal Transmission Switching (ACOTS) problem incorporates line switching decisions into the fundamental AC optimal power flow (ACOPF) problem. The advantages of the ACOTS problem are well-known in terms of reducing the operational cost and improving system reliability. ACOTS optimization models contain discrete variables and nonlinear, non-convex constraints, which make it difficult to … Read more

    Global Optimization of Mixed-Integer Nonlinear Programs with SCIP 8.0

  • Ksenia Bestuzheva
  • Antonia Chmiela
  • Benjamin Müller
  • Felipe Serrano
  • Stefan Vigerske
  • Fabian Wegscheider
    • Categories (Mixed) Integer Nonlinear Programming, Global Optimization, Optimization Software and Modeling Systems Tags , , ,

    For over ten years, the constraint integer programming framework SCIP has been extended by capabilities for the solution of convex and nonconvex mixed-integer nonlinear programs (MINLPs). With the recently published version 8.0, these capabilities have been largely reworked and extended. This paper discusses the motivations for recent changes and provides an overview of features that … Read more