(Mixed) Integer Nonlinear Programming

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

    A solution algorithm for chance-constrained problems with integer second-stage recourse decisions

  • Andrea Lodi
  • Enrico Malaguti
  • Michele Monaci
  • Giacomo Nannicini
  • Paolo Paronuzzi
    • Categories (Mixed) Integer Nonlinear Programming, Stochastic Programming

    We study a class of chance-constrained two-stage stochastic optimization problems where the second-stage recourse decisions belong to mixed-integer convex sets. Due to the nonconvexity of the second-stage feasible sets, standard decomposition approaches cannot be applied. We develop a provably convergent branch-and-cut scheme that iteratively generates valid inequalities for the convex hull of the second-stage feasible … Read more

    A Penalty Branch-and-Bound Method for Mixed-Binary Linear Complementarity Problems

  • Marianna De Santis
  • Sven de Vries
  • Martin Schmidt
  • Lukas Winkel
    • Categories (Mixed) Integer Nonlinear Programming, Branch and Cut Algorithms, Complementarity and Variational Inequalities Tags , , , ,

    Linear complementarity problems (LCPs) are an important modeling tool for many practically relevant situations but also have many important applications in mathematics itself. Although the continuous version of the problem is extremely well studied, much less is known about mixed-integer LCPs (MILCPs) in which some variables have to be integer-valued in a solution. In particular, … Read more

    Exact Logit-Based Product Design

  • İrem Akçakuş
  • Velibor Mišić
    • Categories (Mixed) Integer Linear Programming, (Mixed) Integer Nonlinear Programming, Marketing

    The share-of-choice product design (SOCPD) problem is to find the product, as defined by its attributes, that maximizes market share arising from a collection of customer types or segments. When customers follow a logit model of choice, the market share is given by a weighted sum of logistic probabilities, leading to the logit-based share-of-choice product … Read more

    SDP-quality bounds via convex quadratic relaxations for global optimization of mixed-integer quadratic programs

  • Carlos Nohra
  • Arvind U. Raghunathan
  • Nikolaos Sahinidis
    • Categories (Mixed) Integer Nonlinear Programming, Global Optimization Tags , , , ,

    We consider the global optimization of nonconvex mixed-integer quadratic programs with linear equality constraints. In particular, we present a new class of convex quadratic relaxations which are derived via quadratic cuts. To construct these quadratic cuts, we solve a separation problem involving a linear matrix inequality with a special structure that allows the use of … Read more

    Cardinality Minimization, Constraints, and Regularization: A Survey

  • Daniel Bienstock
  • Andrea Lodi
  • Andreas M. Tillmann
  • Alexandra Schwartz
    • Categories (Mixed) Integer Linear Programming, (Mixed) Integer Nonlinear Programming, Constrained Nonlinear Optimization Tags , , , , , , ,

    We survey optimization problems that involve the cardinality of variable vectors in constraints or the objective function. We provide a unified viewpoint on the general problem classes and models, and give concrete examples from diverse application fields such as signal and image processing, portfolio selection, or machine learning. The paper discusses general-purpose modeling techniques and … Read more

    Alternative Regularizations for OA Algorithms for Convex MINLP

  • David E. Bernal Neira
  • Ignacio E. Grossmann
  • Jan Kronqvist
  • Zedong Peng
    • Categories (Mixed) Integer Nonlinear Programming, Integer Programming, Nonsmooth Optimization

    In this work, we extend the regularization framework from Kronqvist et al. (https://doi.org/10.1007/s10107-018-1356-3) by incorporating several new regularization functions and develop a regularized single-tree search method for solving convex mixed-integer nonlinear programming (MINLP) problems. We propose a set of regularization functions based on distance-metrics and Lagrangean approximations, used in the projection problem for finding new … Read more

    Inductive Linearization for Binary Quadratic Programs with Linear Constraints: A Computational Study

  • Sven Mallach
    • Categories (Mixed) Integer Nonlinear Programming, 0-1 Programming, Quadratic Programming Tags , , ,

    The computational performance of inductive linearizations for binary quadratic programs in combination with a mixed-integer programming solver is investigated for several combinatorial optimization problems and established benchmark instances. Apparently, a few of these are solved to optimality for the first time. Citationpreprint (no internal series / number): University of Bonn, Germany June 11, 2021ArticleDownload View … Read more