ZERO’s components – or modules – are abstract objects defined inside a suitable namespace, which groups modules with a similar function or goal.
The MathOpt namespace contains the utilities and class managing the mathematical optimization objects that ZERO supports. The main class are:
MathOpt::MP_Paramis an abstract class managing the parametrized convex quadratic problems (quadratic objective function with linear constraints).
MathOpt::QP_Paraman inheritor class managing parametrized quadratic programs.
MathOpt::IP_Paraman inheritor class managing parametrized bi-linear integer programs.
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::LCPis the base class for LCP problems.
MathOpt::PolyLCPextends 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.,
The Game namespace contains the definitions of various types of games.
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::FullEnumerationa 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::InnerApproximationan 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::CombinatorialPNEa 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::CutAndPlayouter approximates each player’s feasible region with an increasingly tight polyhedral approximation. It uses the CutAndPlay algorithm scheme.
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::CutAndPlayan 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.
The namespace Algorithms works as a container for any algorithm of ZERO. The children namespace are named after the respective game (e.g, IPG)
The namespace Models implements some high-level APIs to access the
Models::EPEC::EPEChigh-level access to
Models::IPG::IPGhigh-level access to
The namespace Utils is an utility namespace with some common methods (e.g., numerical tolerances, comparisons, etc).
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.
There are currently two command-line interfaces for IPGs and EPECs. You can find them in the directory shells:
The EPEC Shell
The IPG Shell
ZEROAlgorithmDatais an abstract class to manage the data of the various algorithms, for instance,
ZEROExceptionis custom exception class.
ZEROAssert()is a custom assertion global method.
ZEROStatusis an enum of status codes for successful computations/executions, and
ZEROErrorCodesis an enum of error codes.
version defines some macros related to the versioning