Stefan Schwarze

A branch-and-bound algorithm for non-convex Nash equilibrium problems

  • Peter Kirst
  • Stefan Schwarze
  • Oliver Stein
    • Categories Game Theory Tags , , , ,

    This paper introduces a spatial branch-and-bound method for the approximate computation of the set of all epsilon-Nash equilibria of continuous box-constrained non-convex Nash equilibrium problems. We explain appropriate discarding and fathoming techniques, provide a termination proof for a prescribed approximation tolerance, and report our computational experience. Article Download View A branch-and-bound algorithm for non-convex Nash … 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

    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