(Mixed) Integer Nonlinear Programming

Feasible rounding approaches and diving strategies in branch-and-bound methods for mixed-integer optimization

  • Christoph Neumann
  • Stefan Schwarze
  • Oliver Stein
  • Benjamin Müller
    • Categories (Mixed) Integer Linear Programming, (Mixed) Integer Nonlinear Programming Tags , , , , ,

    In this paper, we study the behavior of feasible rounding approaches for mixed-integer linear and nonlinear optimization problems (MILP and MINLP, respectively) when integrated into tree search of branch-and-bound. Our research addresses two important aspects. First, we develop insights into how an (enlarged) inner parallel set, which is the main component for feasible rounding approaches, … Read more

    An Improved Penalty Algorithm using Model Order Reduction for MIPDECO problems with partial observations

  • Dominik Garmatter
  • Margherita Porcelli
  • Francesco Rinaldi
  • Martin Stoll
    • Categories (Mixed) Integer Nonlinear Programming, Optimization of Systems modeled by PDEs Tags , , , ,

    This work addresses optimal control problems governed by a linear time-dependent partial differential equation (PDE) as well as integer constraints on the control. Moreover, partial observations are assumed in the objective function. The resulting problem poses several numerical challenges due to the mixture of combinatorial aspects, induced by integer variables, and large scale linear algebra … Read more

    Presolving for Mixed-Integer Semidefinite Optimization

  • Frederic Matter
  • Marc E. Pfetsch
    • Categories (Mixed) Integer Nonlinear Programming, Semi-definite Programming Tags , , ,

    This paper provides a discussion and evaluation of presolving methods for mixed-integer semidefinite programs. We generalize methods from the mixed-integer linear case and introduce new methods that depend on the semidefinite condition. The considered methods include adding linear constraints, bounds relying on 2 × 2 minors of the semidefinite constraints, bound tightening based on solving … Read more

    Applications of stochastic mixed-integer second-order cone optimization

  • Baha Alzalg
  • Hadjer Alioui
    • Categories (Mixed) Integer Nonlinear Programming, Applications - Science and Engineering, Second-Order Cone Programming Tags , , ,

    Second-order cone programming problems are a tractable subclass of convex optimization problems and there are known polynomial algorithms for solving them. Stochastic second-order cone programming problems have also been studied in the past decade and efficient algorithms for solving them exist. A new class of interest to optimization community and practitioners is the mixed-integer version … Read more

    Time-Domain Decomposition for Mixed-Integer Optimal Control Problems

  • Falk M. Hante
  • Richard Krug
  • Martin Schmidt
    • Categories (Mixed) Integer Nonlinear Programming, Systems governed by Differential Equations Optimization Tags , , ,

    We consider mixed-integer optimal control problems, whose optimality conditions involve global combinatorial optimization aspects for the corresponding Hamiltonian pointwise in time. We propose a time-domain decomposition, which makes this problem class accessible for mixed-integer programming using parallel-in-time direct discretizations. The approach is based on a decomposition of the optimality system and the interpretation of the … Read more

    Projective Cutting Planes for General QP with Indicator Constraints

  • Ulf Friedrich
  • Dennis Kreber
    • Categories (Mixed) Integer Nonlinear Programming, Cutting Plane Approaches Tags , , ,

    General quadratic optimization problems with linear constraints and additional indicator constraints on the variables are studied. Based on the well-known perspective reformulation for mixed-integer quadratic optimization problems, projective cuts are introduced as new valid inequalities for the general problem. The key idea behind the theory of these cutting planes is the projection of the continuous … Read more

    A hybrid patch decomposition approach to compute an enclosure for multi-objective mixed-integer convex optimization problems

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

    In multi-objective mixed-integer convex optimization multiple convex objective functions need to be optimized simultaneously while some of the variables are only allowed to take integer values. In this paper we present a new algorithm to compute an enclosure of the nondominated set of such optimization problems. More precisely, we decompose the multi-objective mixed-integer convex optimization … Read more

    On implementation details and numerical experiments for the HyPaD algorithm to solve multi-objective mixed-integer convex optimization problems

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

    In this paper we present insights on the implementation details of the hybrid patch decomposition algorithm (HyPaD) for convex multi-objective mixed-integer optimization problems. We discuss how to implement the SNIA procedure which is basically a black box algorithm in the original work by Eichfelder and Warnow. In addition, we present and discuss results for various … Read more

    A Reformulation Technique to Solve Polynomial Optimization Problems with Separable Objective Functions of Bounded Integer Variables

  • Andrew C. Trapp
  • Pitchaya Wiratchotisatian
    • Categories (Mixed) Integer Nonlinear Programming, Global Optimization Theory, Nonlinear Optimization Tags , , ,

    Real-world problems are often nonconvex and involve integer variables, representing vexing challenges to be tackled using state-of-the-art solvers. We introduce a mathematical identity-based reformulation of a class of polynomial integer nonlinear optimization (PINLO) problems using a technique that linearizes polynomial functions of separable and bounded integer variables of any degree. We also introduce an alternative … Read more

    On the exactness of the eps-constraint method for bi-objective integer nonlinear programming

  • Marianna De Santis
  • Daniele Patria
    • Categories (Mixed) Integer Nonlinear Programming, Multi-Criteria Optimization Tags , , ,

    The eps-constraint method is a well-known scalarization technique used for multiobjective optimization. We explore how to properly define the step size parameter of the method in order to guarantee its exactness when dealing with problems having two nonlinear objective functions and integrality constraints on the variables. Under specific assumptions, we prove that the number of … Read more