(Mixed) Integer Nonlinear Programming

An Adaptive Discretization MINLP Algorithm for Optimal Synthesis of Decentralized Energy Supply Systems

  • Björn Bahl
  • André Bardow
  • Arie M.C.A. Koster
  • Marco E. Lübbecke
  • Sebastian Goderbauer
  • Philip Voll
    • Categories (Mixed) Integer Nonlinear Programming, Applications - Science and Engineering Tags , , , ,

    Decentralized energy supply systems (DESS) are highly integrated and complex systems designed to meet time-varying energy demands, e.g., heating, cooling, and electricity. The synthesis problem of DESS addresses combining various types of energy conversion units, choosing their sizing and operations to maximize an objective function, e.g., the net present value. In practice, investment costs and … Read more

    Three ideas for a Feasibility Pump for nonconvex MINLP

  • Pietro Belotti
  • Timo Berthold
    • Categories (Mixed) Integer Nonlinear Programming Tags , ,

    We describe an implementation of the Feasibility Pump heuristic for nonconvex MINLPs. Our implementation takes advantage of three novel techniques, which we discuss here: a hierarchy of procedures for obtaining an integer solution, a generalized definition of the distance function that takes into account the nonlinear character of the problem, and the insertion of linearization … Read more

    Minimization of Akaike’s Information Criterion in Linear Regression Analysis via Mixed Integer Nonlinear Program

  • Keiji Kimura
  • Hayato Waki
    • Categories (Mixed) Integer Nonlinear Programming Tags ,

    Akaike’s information criterion (AIC) is a measure of the quality of a statistical model for a given set of data. We can determine the best statistical model for a particular data set by the minimization of the AIC. Since we need to evaluate exponentially many candidates of the model by the minimization of the AIC, … Read more

    Ellipsoidal Mixed-Integer Representability

  • Alberto Del Pia
  • Jeffrey Poskin
    • Categories (Mixed) Integer Nonlinear Programming, Global Optimization Theory

    Representability results for mixed-integer linear systems play a fundamental role in optimization since they give geometric characterizations of the feasible sets that can be formulated by mixed-integer linear programming. We consider a natural extension of mixed-integer linear systems obtained by adding just one ellipsoidal inequality. The set of points that can be described, possibly using … Read more

    On Decomposability of Multilinear Sets

  • Alberto Del Pia
  • Aida Khajavirad
    • Categories (Mixed) Integer Nonlinear Programming, Global Optimization Theory, Polyhedra

    In this paper, we consider the Multilinear set defined as the set of binary points satisfying a collection of multilinear equations. Such sets appear in factorable reformulations of many types of nonconvex optimization problems, including binary polynomial optimization. A great simplification in studying the facial structure of the convex hull of the Multilinear set is … Read more

    On Approximation Algorithms for Concave Mixed-Integer Quadratic Programming

  • Alberto Del Pia
    • Categories (Mixed) Integer Nonlinear Programming, Global Optimization Theory

    Concave Mixed-Integer Quadratic Programming is the problem of minimizing a concave quadratic polynomial over the mixed-integer points in a polyhedral region. In this work we describe an algorithm that finds an ε-approximate solution to a Concave Mixed-Integer Quadratic Programming problem. The running time of the proposed algorithm is polynomial in the size of the problem … Read more

    A feasible rounding approach for granular optimization problems

  • Christoph Neumann
  • Oliver Stein
  • Nathan Sudermann-Merx
    • Categories (Mixed) Integer Linear Programming, (Mixed) Integer Nonlinear Programming Tags , , , ,

    We introduce a new technique to generate good feasible points of mixed-integer nonlinear optimization problems. It makes use of the so-called inner parallel set of the relaxed feasible set, which was employed in O. Stein, Error bounds for mixed integer linear optimization problems, Mathematical Programming, Vol. 156 (2016), 101-123, as well as O. Stein, Error … Read more

    SCIP: Global Optimization of Mixed-Integer Nonlinear Programs in a Branch-and-Cut Framework

  • Ambros Gleixner
  • Stefan Vigerske
    • Categories (Mixed) Integer Nonlinear Programming, Global Optimization

    This paper describes the extensions that were added to the constraint integer programming framework SCIP in order to enable it to solve convex and nonconvex mixed-integer nonlinear programs (MINLPs) to global optimality. SCIP implements a spatial branch-and-bound algorithm based on a linear outer-approximation, which is computed by convex over- and underestimation of nonconvex functions. An … Read more

    An Exact Algorithm for a Resource Allocation Problem in Mobile Wireless Communications

  • Adam N. Letchford
  • Qiang Ni
  • Zhaoyu Zhong
    • Categories (Mixed) Integer Nonlinear Programming, Telecommunications Tags ,

    We consider a challenging resource allocation problem arising in mobile wireless communications. The goal is to allocate the available channels and power in a so-called OFDMA system, in order to maximise the transmission rate, subject to quality of service (QoS) constraints. Standard MINLP software struggled to solve even small instances of this problem. Using outer … Read more

    Low-Complexity Relaxations and Convex Hulls of Disjunctions on the Positive Semidefinite Cone and General Regular Cones

  • Fatma Kılınç-Karzan
  • Sercan Yildiz
    • Categories (Mixed) Integer Nonlinear Programming Tags , , ,

    In this paper we analyze general two-term disjunctions on a regular cone $\K$ and derive a general form for a family of convex inequalities which are valid for the resulting nonconvex sets. Under mild technical assumptions, these inequalities collectively describe the closed convex hulls of these disjunctions, and if additional conditions are satisfied, a single … Read more