(Mixed) Integer Nonlinear Programming

Automatic Reformulations for Convex Mixed-Integer Nonlinear Optimization: Perspective and Separability

  • Meenarli Sharma
  • Ashutosh Mahajan
    • Categories (Mixed) Integer Nonlinear Programming, Optimization Software and Modeling Systems Tags , , , ,

    Tight reformulations of combinatorial optimization problems like Convex Mixed-Integer Nonlinear Programs (MINLPs) enable one to solve these problems faster by obtaining tight bounds on the optimal value. We consider two techniques for reformulation: perspective reformulation and separability detection. We develop routines for the automatic detection of problem structures suitable for these reformulations and implement new … Read more

    Advancements in the computation of enclosures for multi-objective optimization problems

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

    A central goal for multi-objective optimization problems is to compute their nondominated sets. In most cases these sets consist of infinitely many points and it is not a practical approach to compute them exactly. One solution to overcome this problem is to compute an enclosure, a special kind of coverage, of the nondominated set. One … Read more

    A branch-and-prune algorithm for discrete Nash equilibrium problems

  • Stefan Schwarze
  • Oliver Stein
    • Categories (Mixed) Integer Nonlinear Programming, Game Theory Tags , , ,

    We present a branch-and-prune procedure for discrete Nash equilibrium problems with a convex description of each player’s strategy set. The derived pruning criterion does not require player convexity, but only strict convexity of some player’s objective function in a single variable. If satisfied, it prunes choices for this variable by stating activity of certain constraints. … Read more

    An approximation algorithm for optimal piecewise linear approximations of bounded variable products

  • Lukas Hager
  • Robert Burlacu
  • Andreas Bärmann
  • Katja Kutzer
    • Categories (Mixed) Integer Nonlinear Programming, Approximation Algorithms, Quadratic Programming Tags , , ,

    We investigate the optimal piecewise linear interpolation of the bivariate product xy over rectangular domains. More precisely, our aim is to minimize the number of simplices in the triangulation underlying the interpolation, while respecting a prescribed approximation error. First, we show how to construct optimal triangulations consisting of up to five simplices. Using these as … Read more

    A Reciprocity Between Tree Ensemble Optimization and Multilinear Optimization

  • Jongeun Kim
  • Jean-Philippe P. Richard
  • Mohit Tawarmalani
    • Categories (Mixed) Integer Nonlinear Programming Tags , , ,

    In this paper, we establish a polynomial equivalence between tree ensemble optimization and optimization of multilinear functions over the Cartesian product of simplices. We use this insight to derive new formulations for tree ensemble optimization problems and to obtain new convex hull results for multilinear polytopes. A computational experiment on multi-commodity transportation problems with costs … Read more

    Mixed-Integer Programming Techniques for the Minimum Sum-of-Squares Clustering Problem

  • Jan Pablo Burgard
  • Carina Moreira Costa
  • Christopher Hojny
  • Kleinert Thomas
  • Martin Schmidt
    • Categories (Mixed) Integer Nonlinear Programming, Cutting Plane Approaches, Data-Mining Tags , , ,

    The minimum sum-of-squares clustering problem is a very important problem in data mining and machine learning with very many applications in, e.g., medicine or social sciences. However, it is known to be NP-hard in all relevant cases and to be notoriously hard to be solved to global optimality in practice. In this paper, we develop … Read more

    An SDP Relaxation for the Sparse Integer Least Square Problem

  • Alberto Del Pia
  • Dekun Zhou
    • Categories (Mixed) Integer Nonlinear Programming, Global Optimization Theory, Semi-definite Programming Tags , , ,

    In this paper, we study the polynomial approximability or solvability of sparse integer least square problem (SILS), which is the NP-hard variant of the least square problem, where we only consider sparse {0, ±1}-vectors. We propose an l1-based SDP relaxation to SILS, and introduce a randomized algorithm for SILS based on the SDP relaxation. In … Read more

    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