text: /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
  /*                                                                       */
  /*    This file is part of the HiGHS linear optimization suite           */
  /*                                                                       */
  /*    Written and engineered 2008-2020 at the University of Edinburgh    */
  /*                                                                       */
  /*    Available as open-source under the MIT License                     */
  /*                                                                       */
  /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
  /**@file simplex/HDualRow.h
   * @brief Dual simplex ratio test for HiGHS
   * @author Julian Hall, Ivet Galabova, Qi Huangfu and Michael Feldmeier
   */
  #ifndef SIMPLEX_HDUALROW_H_
  #define SIMPLEX_HDUALROW_H_
  
  #include <set>
  #include <vector>
  
  #include "lp_data/HighsModelObject.h"
  
  class HVector;
  const double initial_total_change = 1e-12;
  const double initial_remain_theta = 1e100;
  const double max_select_theta = 1e18;
  
  /**
   * @brief Dual simplex ratio test for HiGHS
   *
   * Performs the dual bound-flipping ratio test and some update
   * dual/flip tasks
   */
  class HDualRow {
   public:
    HDualRow(HighsModelObject& hmo) : workHMO(hmo) {}
  
    /**
     * @brief Calls setupSlice to set up the packed indices and values for
     * the dual ratio test
     */
    void setup();
  
    /**
     * @brief Set up the packed indices and values for the dual ratio test
     *
     * Done either for the whole pivotal row (see HDualRow::setup), or
     * just for a slice (see HDual::initSlice)
     */
    void setupSlice(int size  //!< Dimension of slice
    );
    /**
     * @brief Clear the packed data by zeroing packCount and workCount
     */
    void clear();
  
    /**
     * @brief Pack the indices and values for the row.
     *
     * Offset of numCol is used when packing row_ep
     */
    void chooseMakepack(const HVector* row,  //!< Row to be packed
                        const int offset     //!< Offset for indices
    );
    /**
     * @brief Determine the possible variables - candidates for CHUZC
     *
     * TODO: Check with Qi what this is doing
     */
    void choosePossible();
  
    /**
     * @brief Join pack of possible candidates in this row with possible
     * candidates in otherRow
     */
    void chooseJoinpack(const HDualRow* otherRow  //!< Other row to join with this
    );
    /**
     * @brief Chooses the entering variable via BFRT and EXPAND
     *
     * Can fail when there are excessive dual values due to EXPAND
     * perturbation not being relatively too small
     */
    bool chooseFinal();
  
    /**
     * @brief Identifies the groups of degenerate nodes in BFRT after a
     * heap sort of ratios
     */
    bool chooseFinalWorkGroupQuad();
    bool chooseFinalWorkGroupHeap();
  
    void chooseFinalLargeAlpha(
        int& breakIndex, int& breakGroup, int pass_workCount,
        const std::vector<std::pair<int, double>>& pass_workData,
        const std::vector<int>& pass_workGroup);
  
    void reportWorkDataAndGroup(
        const std::string message, const int reportWorkCount,
        const std::vector<std::pair<int, double>>& reportWorkData,
        const std::vector<int>& reportWorkGroup);
    bool compareWorkDataAndGroup();
  
    /**
     * @brief Update bounds when flips have occurred, and accumulate the
     * RHS for the FTRAN required to update the primal values after BFRT
     */
    void updateFlip(HVector* bfrtColumn  //!< RHS for FTRAN BFRT
    );
    /**
     * @brief Update the dual values
     */
    void updateDual(
        double theta  //!< Multiple of pivotal row to add int to duals
                      //      int columnOut  //!< Index of leaving column
    );
    /**
     * @brief Create a list of nonbasic free columns
     */
    void createFreelist();
  
    /**
     * @brief Set a value of nonbasicMove for all free columns to
     * prevent their dual values from being changed
     */
    void createFreemove(HVector* row_ep  //!< Row of \f$B^{-1}\f$ to be used to
                                         //!< compute pivotal row entry
    );
    /**
     * @brief Reset the nonbasicMove values for free columns
     */
    void deleteFreemove();
  
    /**
     * @brief Delete the list of nonbasic free columns
     */
    void deleteFreelist(int iColumn  //!< Index of column to remove from Freelist
    );
  
    /**
     * @brief Compute (contribution to) the Devex weight
     */
    void computeDevexWeight(const int slice = -1);
  
    HighsModelObject& workHMO;  //!< Local copy of pointer to model
    int workSize = -1;  //!< Size of the HDualRow slice: Initialise it here to
                        //!< avoid compiler warning
    const int* workNumTotPermutation = NULL;  //!< Pointer to model->numTotPermutation();
    const int* workMove = NULL;     //!< Pointer to workHMO.simplex_basis_.nonbasicMove_;
    const double* workDual = NULL;  //!< Pointer to workHMO.simplex_info_.workDual_;
    const double* workRange = NULL;  //!< Pointer to workHMO.simplex_info_.workRange_;
    const int* work_devex_index = NULL;  //!< Pointer to workHMO.simplex_info_.devex_index;
  
    // Freelist:
    std::set<int> freeList;  //!< Freelist itself
  
    // packed data:
    int packCount = 0;                  //!< number of packed indices/values
    std::vector<int> packIndex;     //!< Packed indices
    std::vector<double> packValue;  //!< Packed values
  
    // (Local) value of computed weight
    double computed_edge_weight = 0.;
  
    double workDelta = 0.;  //!< Local copy of dual.deltaPrimal
    double workAlpha = 0.;  //!< Original copy of pivotal computed row-wise
    double workTheta = 0.;  //!< Original copy of dual step workDual[workPivot] /
                       //!< workAlpha;
    int workPivot = 0;     //!< Index of the column entering the basis
    int workCount = 0;     //!< Number of BFRT flips
  
    std::vector<std::pair<int, double>>
        workData;  //!< Index-Value pairs for ratio test
    std::vector<int>
        workGroup;  //!< Pointers into workData for degenerate nodes in BFRT
  
    // Independent identifiers for heap-based sort in BFRT
    int alt_workCount = 0;
    std::vector<std::pair<int, double>> original_workData;
    std::vector<std::pair<int, double>> sorted_workData;
    std::vector<int> alt_workGroup;
  
    HighsSimplexAnalysis* analysis = NULL;
  };
  
  #endif /* SIMPLEX_HDUALROW_H_ */
  