A Tutorial on Solving Single-Leader-Multi-Follower Problems using SOS1 Reformulations

In this tutorial we consider single-leader-multi-follower games in which the models of the lower-level players have polyhedral feasible sets and convex objective functions. This situation allows for classic KKT reformulations of the separate lower-level problems, which lead to challenging single-level reformulations of MPCC type. The main contribution of this tutorial is to present a ready-to-use … Read more

A new single-layer inverse-free fixed-time dynamical system for absolute value equations

In this technical note, a novel single-layer inverse-free fixed-time dynamical system (SIFDS) is proposed to address absolute value equations. The proposed SIFDS directly employs coefficient matrix and absolute value equation function that aims at circumventing matrix inverse operation and achieving fixed-time convergence. The equilibria of the proposed SIFDS is proved to be the unique solution … Read more

Polyhedral Newton-min algorithms for complementarity problems

The semismooth Newton method is a very efficient approach for computing a zero of a large class of nonsmooth equations. When the initial iterate is sufficiently close to a regular zero and the function is strongly semismooth, the generated sequence converges quadratically to that zero, while the iteration only requires to solve a linear system. … Read more

On the Number of Pivots of Dantzig’s Simplex Methods for Linear and Convex Quadratic Programs

Refining and extending works by Ye and Kitahara-Mizuno, this paper presents new results on the number of pivots of simplex-type methods for solving linear programs of the Leontief kind, certain linear complementarity problems of the P kind, and nonnegative constrained convex quadratic programs. Our results contribute to the further understanding of the complexity and efficiency … Read more

On the B-differential of the componentwise minimum of two affine vector functions

This paper focuses on the description and computation of the B-differential of the componentwise minimum of two affine vector functions. This issue arises in the reformulation of the linear complementarity problem with the Min C-function. The question has many equivalent formulations and we identify some of them in linear algebra, convex analysis and discrete geometry. … Read more

On the Relation Between Affinely Adjustable Robust Linear Complementarity and Mixed-Integer Linear Feasibility Problems

We consider adjustable robust linear complementarity problems and extend the results of Biefel et al.~(2022) towards convex and compact uncertainty sets. Moreover, for the case of polyhedral uncertainty sets, we prove that computing an adjustable robust solution of a given linear complementarity problem is equivalent to solving a properly chosen mixed-integer linear feasibility problem. Article … Read more

A Penalty Branch-and-Bound Method for Mixed-Integer Quadratic Bilevel Problems

We propose an algorithm for solving bilevel problems with mixed-integer convex-quadratic upper level as well as convex-quadratic and continuous lower level. The method is based on a classic branch-and-bound procedure, where branching is performed on the integer constraints and on the complementarity constraints resulting from the KKT reformulation of the lower-level problem. However, instead of … Read more

A Ramsey-Type Equilibrium Model with Spatially Dispersed Agents

We present a spatial and time-continuous Ramsey-type equilibrium model for households and firms that interact on a spatial domain to model labor mobility in the presence of commuting costs. After discretization in space and time, we obtain a mixed complementarity problem that represents the spatial equilibrium model. We prove existence of equilibria using the theory … Read more

Monotonicity and Complexity of Multistage Stochastic Variational Inequalities

In this paper, we consider multistage stochastic variational inequalities (MSVIs). First, we give multistage stochastic programs and multistage multi-player noncooperative game problems as source problems. After that, we derive the monotonicity properties of MSVIs under less restrictive conditions. Finally, the polynomial rate of convergence with respect to sample sizes between the original problem and its … Read more

BilevelJuMP.jl: Modeling and Solving Bilevel Optimization in Julia

In this paper we present BilevelJuMP, a new Julia package to support bilevel optimization within the JuMP framework. The package is a Julia library that enables the user to describe both upper and lower-level optimization problems using the JuMP algebraic syntax. Due to the generality and flexibility our library inherits from JuMP’s syntax, our package … Read more