Program Listing for File epec.h

↰ Return to documentation for file (include/games/epec.h)

/* #############################################
 *             This file is part of
 *                    ZERO
 *
 *             Copyright (c) 2020
 *     Released under the Creative Commons
 *         CC BY-NC-SA 4.0 License
 *
 *              Find out more at
 *        https://github.com/ds4dm/ZERO
 * #############################################*/


#pragma once
#include "support/codes.h"
#include "zero.h"
#include <armadillo>
#include <gurobi_c++.h>
#include <iostream>
#include <mathopt/lcp/lcp.h>
#include <memory>
#include <set>
#include <string>

namespace Data::EPEC {

  enum class Algorithms {

     FullEnumeration,
     InnerApproximation,
     CombinatorialPne,
     OuterApproximation
  };
  enum class RecoverStrategy {
     IncrementalEnumeration,
     Combinatorial
  };

  enum class BranchingStrategy {
     HybridBranching,
     DeviationBranching,
  };


  class DataObject : public ZEROAlgorithmData {
  public:
     Attr<Data::EPEC::Algorithms> Algorithm = {
          Data::EPEC::Algorithms::FullEnumeration};
     Attr<Data::EPEC::RecoverStrategy> RecoverStrategy = {
          Data::EPEC::RecoverStrategy::IncrementalEnumeration};
     Attr<Data::LCP::PolyhedraStrategy>
                              PolyhedraStrategy;
     Attr<unsigned int> Aggressiveness{
          1};
     Attr<std::vector<unsigned int>> FeasiblePolyhedra =
          std::vector<unsigned int>();
     Attr<std::vector<unsigned int>> OuterComplementarities =
          std::vector<unsigned int>();
     Attr<int> LostIntermediateEq = {0};
     Attr<Data::LCP::Algorithms>
          LCPSolver;

     Attr<Data::EPEC::BranchingStrategy> BranchingStrategy =
          Data::EPEC::BranchingStrategy::HybridBranching;

     DataObject()
          : PolyhedraStrategy{static_cast<Data::LCP::PolyhedraStrategy>(0)},
             LCPSolver{static_cast<Data::LCP::Algorithms>(0)} {};
  };

} // namespace Data::EPEC

namespace Game {

  class EPEC : public AbstractGame<Data::EPEC::DataObject> {
  private:
     std::shared_ptr<Algorithms::EPEC::PolyBase>
          Algorithm{};
     std::vector<unsigned int>
          SizesWithoutHull{};
     std::unique_ptr<MathOpt::LCP> TheLCP;
     std::unique_ptr<GRBModel>     LCPModel;
     std::unique_ptr<GRBModel> LCPModelBase;
  protected:
     std::vector<std::shared_ptr<Game::NashGame>>
          PlayersLowerLevels{};
     std::vector<std::shared_ptr<MathOpt::LCP>>
          PlayersLCP{};

     std::vector<std::shared_ptr<MathOpt::QP_Param>>
          PlayersQP{};
     std::vector<std::shared_ptr<MathOpt::QP_Objective>>
          LeaderObjective{};
     std::vector<std::shared_ptr<MathOpt::QP_Objective>>
          LeaderObjectiveConvexHull{};

     std::unique_ptr<Game::NashGame> TheNashGame;

     std::vector<unsigned int> LeaderLocations{};
     std::vector<const unsigned int *>
          LocEnds{};
     std::vector<unsigned int>
                      ConvexHullVariables{};
     unsigned int numMCVariables{0};

     bool      Finalized{false};
     arma::vec SolutionZ,
          SolutionX;
     bool warmstart(const arma::vec &x);

  private:
     void addDummyLead(unsigned int i);
     void makePlayerQP(unsigned int i);

     void makePlayersQPs();

     void makeTheLCP();


     void computeLeaderLocations(unsigned int addSpaceForMC = 0);

     void getXMinusI(const arma::vec &x, const unsigned int &i, arma::vec &xMinusI) const;

     bool computeNashEq(
          bool pureNE, double localTimeLimit, bool check, bool linearWelfare, bool quadraticWelfare);

  protected:
     virtual void makeObjectivePlayer(const unsigned int i, MathOpt::QP_Objective &QP_obj) = 0;

     virtual void preFinalize() = 0;

     virtual void postFinalize() = 0;

     virtual void updateLocations() = 0;
     virtual void makeMCConstraints(arma::sp_mat &MC, arma::vec &RHS) const {
        MC.zeros();
        RHS.zeros();
     };

  public: // functions
     // Friends algorithmic classes
     friend class Algorithms::EPEC::PolyBase;

     friend class Algorithms::EPEC::InnerApproximation;

     friend class Algorithms::EPEC::CutAndPlay;

     friend class Algorithms::EPEC::CombinatorialPNE;

     friend class Algorithms::EPEC::FullEnumeration;

     EPEC(GRBEnv *env) { this->Env = env; };

     void finalize();

     // Override AbstractGame methods
     void findNashEq() override;
     bool isSolved(double tol = 1e-5) const override;
     bool isPureStrategy(double tol = 1e-5) const override;

     std::unique_ptr<GRBModel> bestResponseProgram(const unsigned int i, const arma::vec &x, MathOpt::PolyLCP *customLCP = nullptr) const;

     double bestResponse(arma::vec &       sol,
                             unsigned int      player,
                             const arma::vec & x,
                             const arma::vec & prevDev   = {},
                             MathOpt::PolyLCP *customLCP = nullptr) const;

     const arma::vec getX() const { return this->SolutionX; }

     const arma::vec getZ() const { return this->SolutionZ; }

     void setAlgorithm(Data::EPEC::Algorithms algorithm);

     void setRecoverStrategy(Data::EPEC::RecoverStrategy strategy);

     void setBranchingStrategy(Data::EPEC::BranchingStrategy strategy);

     void setAggressiveness(unsigned int a) { this->Stats.AlgorithmData.Aggressiveness = a; }

     void setAddPolyMethod(Data::LCP::PolyhedraStrategy add) {
        this->Stats.AlgorithmData.PolyhedraStrategy.set(add);
     }

     unsigned int getPositionLeadFoll(unsigned int i, unsigned int j) const;

     unsigned int getPositionLeadLead(unsigned int i, unsigned int j) const;

     // The following obtain the variable values
     double getValLeadFoll(unsigned int i, unsigned int j) const;

     double getValLeadLead(unsigned int i, unsigned int j) const;

    double getValProbab(unsigned int i, unsigned int k);
    double getValLeadFollPoly(unsigned int i,
                              unsigned int j,
                              unsigned int k,
                              double       tol=1e-5) const;
    double getValLeadLeadPoly(unsigned int i,
                              unsigned int j,
                              unsigned int k,
                              double       tol=1e-5) const;

    std::vector<unsigned int> mixedStrategyPoly(unsigned int i, double tol=1e-5) const;

     const MathOpt::LCP &getLCPDescription() const { return *this->TheLCP.get(); }

     const GRBModel &getLCPModel() const { return *this->LCPModel.get(); }

     void writeLCPModel(const std::string &filename) const { this->LCPModel->write(filename); }

     void getXWithoutHull(const arma::vec &x, arma::vec &xWithoutHull) const;
     void
     getXofI(const arma::vec &x, const unsigned int &i, arma::vec &xOfI, bool hull = false) const;
     void setWelfareObjective(bool linear, bool quadratic);
  };
}; // namespace Game

namespace std {

  string to_string(Data::EPEC::Algorithms al);

  string to_string(Data::EPEC::RecoverStrategy st);

  string to_string(Data::EPEC::BranchingStrategy st);

}; // namespace std

#include "interfaces/epec_models.h"