(Mixed) Integer Nonlinear Programming

Computing Feasible Points of Bilevel Problems with a Penalty Alternating Direction Method

  • Thomas Kleinert
  • Martin Schmidt
    • Categories (Mixed) Integer Linear Programming, (Mixed) Integer Nonlinear Programming Tags , , , ,

    Bilevel problems are highly challenging optimization problems that appear in many applications of energy market design, critical infrastructure defense, transportation, pricing, etc. Often, these bilevel models are equipped with integer decisions, which makes the problems even harder to solve. Typically, in such a setting in mathematical optimization one develops primal heuristics in order to obtain … Read more

    A switching cost aware rounding method for relaxations of mixed-integer optimal control problems

  • Felix Bestehorn
  • Christoph Hansknecht
  • Christian Kirches
  • Paul Manns
    • Categories (Mixed) Integer Nonlinear Programming, Systems governed by Differential Equations Optimization Tags ,

    This article investigates a class of Mixed-Integer Optimal Control Problems (MIOCPs) with switching costs. We introduce the problem class of Minimal-Switching-Cost Optimal Control Problems (MSCP) with an objective function that consists of two summands, a continuous term depending on the state vector and an encoding of the discrete switching costs. State vectors of Mixed-Integer Optimal … Read more

    Algorithms for the circle packing problem based on mixed-integer DC programming

  • Yoshiko Ikebe
  • Satoru Masuda
  • Takayuki Okuno
    • Categories (Mixed) Integer Nonlinear Programming, Applications - OR and Management Sciences Tags , ,

    Circle packing problems are a class of packing problems which attempt to pack a given set of circles into a container with no overlap. In this paper, we focus on the circle packing problem proposed by L{\’o}pez et.al. The problem is to pack circles of unequal size into a fixed size circular container, so as … Read more

    Rank-one Convexification for Sparse Regression

  • Alper Atamturk
  • Andrés Gómez
    • Categories (Mixed) Integer Nonlinear Programming, Semi-definite Programming, Statistics Tags , , , , ,

    Sparse regression models are increasingly prevalent due to their ease of interpretability and superior out-of-sample performance. However, the exact model of sparse regression with an L0 constraint restricting the support of the estimators is a challenging non-convex optimization problem. In this paper, we derive new strong convex relaxations for sparse regression. These relaxations are based … Read more

    A Status Report on Conflict Analysis in Mixed Integer Nonlinear Programming

  • Timo Berthold
  • Stefan Heinz
  • Jakob Witzig
    • Categories (Mixed) Integer Nonlinear Programming Tags , , ,

    Mixed integer nonlinear programs (MINLPs) are arguably among the hardest optimization problems, with a wide range of applications. MINLP solvers that are based on linear relaxations and spatial branching work similar as mixed integer programming (MIP) solvers in the sense that they are based on a branch-and-cut algorithm, enhanced by various heuristics, domain propagation, and … Read more

    Intersection disjunctions for reverse convex sets

  • James R. Luedtke
  • Eli Towle
    • Categories (Mixed) Integer Nonlinear Programming, Constrained Nonlinear Optimization, Global Optimization Theory Tags , , , ,

    We present a framework to obtain valid inequalities for optimization problems constrained by a reverse convex set, which is defined as the set of points in a polyhedron that lie outside a given open convex set. We are particularly interested in cases where the closure of the convex set is either non-polyhedral, or is defined … Read more

    Submodularity in conic quadratic mixed 0-1 optimization

  • Alper Atamturk
  • Andrés Gómez
    • Categories (Mixed) Integer Nonlinear Programming, Cutting Plane Approaches Tags , , , , , , ,

    We describe strong convex valid inequalities for conic quadratic mixed 0-1 optimization. These inequalities can be utilized for solving numerous practical nonlinear discrete optimization problems from value-at-risk minimization to queueing system design, from robust interdiction to assortment optimization through appropriate conic quadratic mixed 0-1 relaxations. The inequalities exploit the submodularity of the binary restrictions and … Read more

    Successive Quadratic Upper-Bounding for Discrete Mean-Risk Minimization and Network Interdiction

  • Alper Atamturk
  • Carlos Deck
  • Hyemin Jeon
    • Categories (Mixed) Integer Nonlinear Programming, Robust Optimization Tags , , , ,

    The advances in conic optimization have led to its increased utilization for modeling data uncertainty. In particular, conic mean-risk optimization gained prominence in probabilistic and robust optimization. Whereas the corresponding conic models are solved efficiently over convex sets, their discrete counterparts are intractable. In this paper, we give a highly effective successive quadratic upper-bounding procedure … Read more

    Intersection cuts for factorable MINLP

  • Felipe Serrano
    • Categories (Mixed) Integer Nonlinear Programming, Global Optimization Tags , ,

    Given a factorable function f, we propose a procedure that constructs a concave underestimor of f that is tight at a given point. These underestimators can be used to generate intersection cuts. A peculiarity of these underestimators is that they do not rely on a bounded domain. We propose a strengthening procedure for the intersection … Read more

    Insight into the computation of Steiner minimal trees in Euclidean space of general dimension

  • Marcia Fampa
    • Categories (Mixed) Integer Nonlinear Programming, Global Optimization

    We present well known properties related to the topology of Steiner minimal trees and to the geometric position of Steiner points, and investigate their application in the main exact algorithms that have been proposed for the Euclidean Steiner problem. We discuss the difficulty in the application of properties that were very successfully applied to solve … Read more