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

    Globally linearly convergent nonlinear conjugate gradients without Wolfe line search

  • Arnold Neumaier
  • Morteza Kimiaei
  • Behzad Azmi
    • Categories Nonlinear Optimization Tags

    This paper introduces a new nonlinear conjugate gradient (CG) method using an efficient gradient-free line search method. Unless function values diverge to $-\infty$, global convergence to a stationary point is proved for continuously differentiable objective functions with Lipschitz continuous gradient, and global linear convergence if this stationary point is a strong local minimizer. The $n$-iterations … Read more

    Regularized Nonsmooth Newton Algorithms for Best Approximation

  • Yair Censor
  • Walaa M. Moursi
  • Tyler Weames
  • Henry Wolkowicz
    • Categories Convex Optimization, Linear Programming, Nonsmooth Optimization Tags , , , , ,

    We consider the problem of finding the best approximation point from a polyhedral set, and its applications, in particular to solving large-scale linear programs. The classical projection problem has many various and many applications. We study a regularized nonsmooth Newton type solution method where the Jacobian is singular; and we compare the computational performance to … Read more

    Γ-robust Optimization of Project Scheduling Problems

  • Arie M.C.A. Koster
  • Jenny Segschneider
    • Categories Applications - OR and Management Sciences, Scheduling Tags , , , ,

    \(\) In this paper, we investigate the problem of finding a robust baseline schedule for the project scheduling problem under uncertain process times. We assume that the probability distribution for the duration is unknown but an estimation together with an interval in which this time can vary is given. At most $ \Gamma $ of … Read more

    Global Optimization of Mixed-Integer Nonlinear Programs with SCIP 8.0

  • Ksenia Bestuzheva
  • Antonia Chmiela
  • Benjamin Müller
  • Felipe Serrano
  • Stefan Vigerske
  • Fabian Wegscheider
    • Categories (Mixed) Integer Nonlinear Programming, Global Optimization, Optimization Software and Modeling Systems Tags , , ,

    For over ten years, the constraint integer programming framework SCIP has been extended by capabilities for the solution of convex and nonconvex mixed-integer nonlinear programs (MINLPs). With the recently published version 8.0, these capabilities have been largely reworked and extended. This paper discusses the motivations for recent changes and provides an overview of features that … Read more

    Distributionally robust chance-constrained Markov decision processes

  • Hoang Nam Nguyen
  • Abdel Lisser
  • Vikas Vikram Singh
    • Categories Stochastic Programming Tags , , , , ,

    Markov decision process (MDP) is a decision making framework where a decision maker is interested in maximizing the expected discounted value of a stream of rewards received at future stages at various states which are visited according to a controlled Markov chain. Many algorithms including linear programming methods are available in the literature to compute … Read more

    A Branch and Bound Algorithm for Biobjective Mixed Integer Quadratic Programs

  • Pubudu L.W. Jayasekara Merenchige
  • Margaret Wiecek
    • Categories (Mixed) Integer Nonlinear Programming, Integer Programming, Multi-Criteria Optimization Tags , , , , ,

    Multiobjective quadratic programs (MOQPs) are appealing since convex quadratic programs have elegant mathematical properties and model important applications. Adding mixed-integer variables extends their applicability while the resulting programs become global optimization problems. We design and implement a branch and bound (BB) algorithm for biobjective mixed-integer quadratic programs (BOMIQPs). In contrast to the existing algorithms in … Read more

    Second-order Partial Outer Convexification for Switched Dynamical Systems

  • Christoph Plate
  • Sebastian Sager
  • Martin Stoll
  • Manuel Tetschke
    • Categories Nonlinear Optimization, Systems governed by Differential Equations Optimization Tags , , ,

    Mixed-integer optimal control problems arise in many practical applications combining nonlinear, dynamic, and combinatorial features. To cope with the resulting complexity, several approaches have been suggested in the past. Some of them rely on solving a reformulated and relaxed control problem, referred to as partial outer convexification. Inspired by an efficient algorithm for switching time … Read more

    A comparison of different approaches for the vehicle routing problem with stochastic demands

  • Matheus Jun Ota
  • Ricardo Fukasawa
    • Categories Branch and Cut Algorithms, Production and Logistics, Stochastic Programming Tags , ,

    The vehicle routing problem with stochastic demands (VRPSD) is a well studied variant of the classic (deterministic) capacitated vehicle routing problem (CVRP) where the customer demands are given by random variables. Two prominent approaches for solving the VRPSD model it either as a chance-constraint program (CC-VRPSD) or as a two-stage stochastic program (2S-VRPSD). In this … Read more