Integer Programming

Inverse Mixed Integer Optimization: Polyhedral Insights and Trust Region Methods

  • Merve Bodur
  • Timothy C.Y. Chan
  • Ian Yihang Zhu
    • Categories Integer Programming Tags , , , , ,

    Inverse optimization – determining parameters of an optimization problem that render a given solution optimal – has received increasing attention in recent years. While significant inverse optimization literature exists for convex optimization problems, there have been few advances for discrete problems, despite the ubiquity of applications that fundamentally rely on discrete decision-making. In this paper, … Read more

    Convexifying Multilinear Sets with Cardinality Constraints: Structural Properties, Nested Case and Extensions

  • Rui Chen
  • Sanjeeb Dash
  • Oktay Gunluk
    • Categories 0-1 Programming, Cutting Plane Approaches Tags , ,

    The problem of minimizing a multilinear function of binary variables is a well-studied NP-hard problem. The set of solutions of the standard linearization of this problem is called the multilinear set. We study a cardinality constrained version of it with upper and lower bounds on the number of nonzero variables. We call the set of … Read more

    Branch-and-Bound Solves Random Binary IPs in Polytime

  • Santanu S. Dey
  • Yatharth Dubey
  • Marco Molinaro
    • Categories 0-1 Programming, Branch and Cut Algorithms, Global Optimization Theory Tags ,

    Branch-and-bound is the workhorse of all state-of-the-art mixed integer linear programming (MILP) solvers. These implementations of branch-and-bound typically use variable branching, that is, the child nodes are obtained by fixing some variable to an integer value v in one node and to v + 1 in the other node. Even though modern MILP solvers are … Read more

    On Refinement Strategies for Solving MINLPs by Piecewise Linear Relaxations: A Generalized Red Refinement

  • Robert Burlacu
    • Categories (Mixed) Integer Nonlinear Programming Tags , , ,

    We investigate the generalized red refinement for n-dimensional simplices that dates back to Freudenthal in a mixed-integer nonlinear program (MINLP) context. We show that the red refinement meets sufficient convergence conditions for a known MINLP solution framework that is essentially based on solving piecewise linear relaxations. In addition, we prove that applying this refinement procedure … Read more

    An Adaptive Patch Approximation Algorithm for Bicriteria Convex Mixed Integer problems

  • Erik Diessel
    • Categories (Mixed) Integer Nonlinear Programming, Multi-Criteria Optimization Tags , , ,

    Pareto frontiers of bicriteria continuous convex problems can be efficiently computed and optimal theoretical performance bounds have been established. In the case of bicriteria mixed-integer problems, the approximation of the Pareto frontier becomes, however, significantly harder. In this paper, we propose a new algorithm for approximating the Pareto frontier of bicriteria mixed-integer programs with convex … Read more

    An Almost Exact Solution to the Min Completion Time Variance in a Single Machine

  • Stefano Nasini
  • Rabia Nessah
    • Categories 0-1 Programming, Combinatorial Optimization, Scheduling Tags , , ,

    We consider a single machine scheduling problem to minimize the completion time variance of n jobs. This problem is known to be NP-hard and our contribution is to establish a novel bounding condition for a characterization of an optimal sequence. Specifically, we prove a necessary and sufficient condition (which can be verified in O(n\log n)) … Read more

    A Separation Heuristic for 2-Partition Inequalities for the Clique Partitioning Problem

  • Michael M. Sørensen
    • Categories Branch and Cut Algorithms, Cutting Plane Approaches, Polyhedra

    We consider the class of 2-partition inequalities for the clique partitioning problem associated with complete graphs. We propose a heuristic separation algorithm for the inequalities and evaluate its usefulness in a cutting-plane algorithm. Our computational experiments fall into two parts. In the first part, we compare the LP objective values obtained by the proposed separator … Read more

    Multi-period investment pathways – Modeling approaches to design distributed energy systems under uncertainty

  • Markus Bohlayer
  • Marco Braun
  • Adrian Bürger
  • Markus Fleschutz
  • Gregor Zöttl
    • Categories (Mixed) Integer Linear Programming, Applications - OR and Management Sciences, Stochastic Programming

    Multi-modal distributed energy system planning is applied in the context of smart grids, industrial energy supply, and in the building energy sector. In real-world applications, these systems are commonly characterized by existing system structures of different age where monitoring and investment are conducted in a closed-loop, with the iterative possibility to invest. The literature contains … Read more

    The confined primal integral

  • Timo Berthold
  • Zsolt Csizmadia
    • Categories (Mixed) Integer Nonlinear Programming, Optimization Software Benchmark Tags , ,

    It is a challenging task to fairly compare local solvers and heuristics against each other and against global solvers. How does one weigh a faster termination time against a better quality of the found solution? In this paper, we introduce the confined primal integral, a new performance measure that rewards a balance of speed and … Read more

    Conflict Analysis for MINLP

  • Timo Berthold
  • Jakob Witzig
    • Categories (Mixed) Integer Nonlinear Programming

    The generalization of MIP techniques to deal with nonlinear, potentially non-convex, constraints have been a fruitful direction of research for computational MINLP in the last decade. In this paper, we follow that path in order to extend another essential subroutine of modern MIP solvers towards the case of nonlinear optimization: the analysis of infeasible subproblems … Read more