granularity

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

    Feasible rounding approaches for equality constrained mixed-integer optimization problems

  • Christoph Neumann
  • Oliver Stein
    • Categories (Mixed) Integer Linear Programming, (Mixed) Integer Nonlinear Programming Tags , , , ,

    A feasible rounding approach is a novel technique to compute good feasible points for mixed-integer optimization problems. The central idea of this approach is the construction of a continuously described inner parallel set for which any rounding of any of its elements is feasible in the original mixed-integer problem. It is known that this approach … Read more

    A feasible rounding approach for granular optimization problems

  • Christoph Neumann
  • Oliver Stein
  • Nathan Sudermann-Merx
    • Categories (Mixed) Integer Linear Programming, (Mixed) Integer Nonlinear Programming Tags , , , ,

    We introduce a new technique to generate good feasible points of mixed-integer nonlinear optimization problems. It makes use of the so-called inner parallel set of the relaxed feasible set, which was employed in O. Stein, Error bounds for mixed integer linear optimization problems, Mathematical Programming, Vol. 156 (2016), 101-123, as well as O. Stein, Error … Read more

    Error bounds for mixed integer nonlinear optimization problems

  • Oliver Stein
    • Categories (Mixed) Integer Nonlinear Programming Tags , , ,

    We introduce a-posteriori and a-priori error bounds for optimality and feasibility of a point generated as the rounding of an optimal point of the NLP relaxation of a mixed-integer nonlinear optimization problem. Our analysis mainly bases on the construction of a tractable approximation of the so-called grid relaxation retract. Under appropriate Lipschitz assumptions on the … Read more

    Error bounds for mixed integer linear optimization problems

  • Oliver Stein
    • Categories (Mixed) Integer Linear Programming Tags , , ,

    We introduce computable a-priori and a-posteriori error bounds for optimality and feasibility of a point generated as the rounding of an optimal point of the LP relaxation of a mixed integer linear optimization problem. Treating the mesh size of integer vectors as a parameter allows us to study the effect of different `granularities’ in the … Read more