(Mixed) Integer Nonlinear Programming

A solver for multiobjective mixed-integer convex and nonconvex optimization

  • Gabriele Eichfelder
  • Oliver Stein
  • Leo Warnow
    • Categories (Mixed) Integer Nonlinear Programming, Global Optimization, Multi-Criteria Optimization Tags , , , , ,

    This paper proposes a general framework for solving multiobjective nonconvex optimization problems, i.e., optimization problems in which multiple objective functions have to be optimized simultaneously. Thereby, the nonconvexity might come from the objective or constraint functions, or from integrality conditions for some of the variables. In particular, multiobjective mixed-integer convex and nonconvex optimization problems are … Read more

    Solving Two-Trust-Region Subproblems using Semidefinite Optimization with Eigenvector Branching

  • Kurt M. Anstreicher
    • Categories (Mixed) Integer Nonlinear Programming, Global Optimization Theory, Semi-definite Programming Tags , , , ,

    Semidefinite programming (SDP) problems typically utilize the constraint that X-xx’ is PSD to obtain a convex relaxation of the condition X=xx’, where x is an n-vector. In this paper we consider a new hyperplane branching method for SDP based on using an eigenvector of X-xx’. This branching technique is related to previous work of Saxeena, … Read more

    The impact of passive social media viewers in influence maximization

  • Michael Kahr
  • Markus Leitner
  • Ivana Ljubić
    • Categories (Mixed) Integer Nonlinear Programming, Branch and Cut Algorithms, Marketing Tags , ,

    A frequently studied problem in the context of digital marketing for online social networks is the influence maximization problem that seeks for an initial seed set of influencers to trigger an information propagation cascade (in terms of active message forwarders) of expected maximum impact. Previously studied problems typically neglect that the probability that individuals passively … Read more

    The Chvátal-Gomory Procedure for Integer SDPs with Applications in Combinatorial Optimization

  • Frank de Meijer
  • Renata Sotirov
    • Categories (Mixed) Integer Nonlinear Programming, Cutting Plane Approaches, Semi-definite Programming Tags , , , ,

    In this paper we study the well-known Chvátal-Gomory (CG) procedure for the class of integer semidefinite programs (ISDPs). We prove several results regarding the hierarchy of relaxations obtained by iterating this procedure. We also study different formulations of the elementary closure of spectrahedra. A polyhedral description of the elementary closure for a specific type of … Read more

    New Algorithm to Solve Mixed Integer Quadratically Constrained Quadratic Programming Problems Using Piecewise Linear Approximation

  • Loay Alkhalifa
  • Hans D Mittelmann
    • Categories (Mixed) Integer Nonlinear Programming Tags , ,

    Techniques and methods of linear optimization underwent a significant improvement in the 20th century which led to the development of reliable mixed integer linear programming (MILP) solvers. It would be useful if these solvers could handle mixed integer nonlinear programming (MINLP) problems. Piecewise linear approximation (PLA) is one of most popular methods used to transform … Read more

    On the convex hull of convex quadratic optimization problems with indicators

  • Linchuan Wei
  • Alper Atamturk
  • Andrés Gómez
  • Simge Küçükyavuz
    • Categories (Mixed) Integer Nonlinear Programming Tags , ,

    We consider the convex quadratic optimization problem with indicator variables and arbitrary constraints on the indicators. We show that a convex hull description of the associated mixed-integer set in an extended space with a quadratic number of additional variables consists of a single positive semidefinite constraint (explicitly stated) and linear constraints. In particular, convexification of … Read more

    Multiple-Periods Locally-Facet-Based MIP Formulations for the Unit Commitment Problem

  • Linfeng Yang
  • Shifei Chen
  • Zhaoyang Dong
    • Categories (Mixed) Integer Nonlinear Programming, Applications - OR and Management Sciences, Polyhedra Tags , , , , , , ,

    The thermal unit commitment (UC) problem has historically been formulated as a mixed integer quadratic programming (MIQP), which is difficult to solve efficiently, especially for large-scale systems. The tighter characteristic reduces the search space, therefore, as a natural consequence, significantly reduces the computational burden. In literatures, many tightened formulations for a single unit with parts … Read more

    A Finitely Convergent Cutting Plane, and a Bender’s Decomposition Algorithm for Mixed-Integer Convex and Two-Stage Convex Programs using Cutting Planes

  • Fengqiao Luo
  • Sanjay Mehrotra
    • Categories (Mixed) Integer Nonlinear Programming, Cutting Plane Approaches, Stochastic Programming Tags , , ,

    We consider a general mixed-integer convex program. We first develop an algorithm for solving this problem, and show its nite convergence. We then develop a finitely convergent decomposition algorithm that separates binary variables from integer and continuous variables. The integer and continuous variables are treated as second stage variables. An oracle for generating a parametric … Read more

    Modeling Design and Control Problems Involving Neural Network Surrogates

  • Dominic Yang
  • Prasanna Balaprakash
  • Sven Leyffer
    • Categories (Mixed) Integer Nonlinear Programming, Control Applications, Nonsmooth Optimization Tags , , , ,

    We consider nonlinear optimization problems that involve surrogate models represented by neural net-works. We demonstrate first how to directly embed neural network evaluation into optimization models, highlight a difficulty with this approach that can prevent convergence, and then characterize stationarity of such models. We then present two alternative formulations of these problems in the specific … Read more

    Exact Methods for Discrete Γ-Robust Interdiction Problems with an Application to the Bilevel Knapsack Problem

  • Yasmine Beck
  • Ivana Ljubić
  • Martin Schmidt
    • Categories (Mixed) Integer Nonlinear Programming, Cutting Plane Approaches, Robust Optimization Tags , , , ,

    Developing solution methods for discrete bilevel problems is known to be a challenging task – even if all parameters of the problem are exactly known. Many real-world applications of bilevel optimization, however, involve data uncertainty. We study discrete min-max problems with a follower who faces uncertainties regarding the parameters of the lower-level problem. Adopting a … Read more