Overview

ZERO’s components – or modules – are abstract objects defined inside a suitable namespace, which groups modules with a similar function or goal.

MathOpt

The MathOpt namespace contains the utilities and class managing the mathematical optimization objects that ZERO supports. The main class are:

MP_Program(s)

  • MathOpt::MP_Param is an abstract class managing the parametrized convex quadratic problems (quadratic objective function with linear constraints).

  • MathOpt::QP_Param an inheritor class managing parametrized quadratic programs.

  • MathOpt::IP_Param an inheritor class managing parametrized bi-linear integer programs.

LCPs

The class MathOpt::LCP manages Linear Complementarity Problems (LCPs). Such problems are fundamental components for the computation of Nash Equilibria in games among quadratic linear programs. _LCPs_ can be seen as “feasibility” mathematical programs whose feasible region is given by a finite union of polyhedra.

  • MathOpt::LCP is the base class for LCP problems.

  • MathOpt::PolyLCP extends the LCP class to handle its polyhedral aspects. For instance, outer and inner approximations of the feasible region.

Additionally, the namespace includes some utilities and shared components (e.g., MathOpt::convexHull(), MathOpt::getDualMembershipLP()).

Games

The Game namespace contains the definitions of various types of games.

EPECs

Equilibrium Problems with Equilibrium Constraints (EPECs) are powerful modeling paradigms for modeling two-level hierarchical games involving equilibria both in the upper and lower level. ZERO handles EPECs where:

  • Each (“player”) is the leader of a Bilevel program

  • Each leader has a set of followers playing a simultaneous game among each other. Each follower solves a convex quadratic continuous problem

  • While leaders can interact among themselves, followers can only interact with other followers from the same leader.

For more information, take a look at the material here. Game::EPEC has a generic implementation for EPEC problems. You may want to look at Models::EPEC for the associated modeling paradigm.

ZERO currently supports the following algorithms for EPECs:

  • Algorithms::EPEC::FullEnumeration a full-enumeration algorithm for EPECs (more here). This is an exact method capable of finding an equilibrium maximizing a given function in the players’ variables.

  • Algorithms::EPEC::InnerApproximation an inner approximation algorithm for EPECs (more here). This algorithm inner-approximate each player feasible region (namely, it approximates an LCP and hence a finite union of polyhedra) with increasingly bigger representations.

  • Algorithms::EPEC::CombinatorialPNE a sort of inner approximation algorithm for EPECs (more here). This algorithm only computes pure equilibria by inner approximating each player’s finite union of polyhedra with a single polyhedron. All the combinations are tested for a PNE.

  • Algorithms::EPEC::CutAndPlay outer approximates each player’s feasible region with an increasingly tight polyhedral approximation. It uses the CutAndPlay algorithm scheme.

IPG

Integer Programming Games (IPGs) are a class of simultaneous non-cooperative games where each player solves an integer program fully parametrized in the player’s variable. In other words, the constraints of each player solely depend on the variables of that player. ZERO currently supports IPGs where the objective functions are at most bilinear (w.r.t. the other players) and quadratic in each player’s variables. Game::IPG implements such games, and there is only one algorithm available:

  • Algorithms::IPG::CutAndPlay an outer approximation algorithm (similar to Algorithms::EPEC::CutAndPlay) again using the CutAndPlay algorithm scheme.. Each player’s integer program is approximated with its linear relaxation. A sequence of cutting planes and branching decisions guide the algorithm towards the computation of an equilibrium.

Algorithms

The namespace Algorithms works as a container for any algorithm of ZERO. The children namespace are named after the respective game (e.g, IPG)

Models

The namespace Models implements some high-level APIs to access the Game modules.

Utils

The namespace Utils is an utility namespace with some common methods (e.g., numerical tolerances, comparisons, etc).

Solvers

The namespace Solvers implements some external solvers through a customized interface (e.g., PATH). In future releases, we hope to move also Gurobi and other solvers such as SCIP in this namespace and abstract their interface with ZERO.

Shells

There are currently two command-line interfaces for IPGs and EPECs. You can find them in the directory shells:

Other stuff