class_pricingcontroller.h

Go to the documentation of this file.

/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
/*                                                                           */
/*                  This file is part of the program                         */
/*          GCG --- Generic Column Generation                                */
/*                  a Dantzig-Wolfe decomposition based extension            */
/*                  of the branch-cut-and-price framework                    */
/*         SCIP --- Solving Constraint Integer Programs                      */
/*                                                                           */
/* Copyright (C) 2010-2021 Operations Research, RWTH Aachen University       */
/*                         Zuse Institute Berlin (ZIB)                       */
/*                                                                           */
/* This program is free software; you can redistribute it and/or             */
/* modify it under the terms of the GNU Lesser General Public License        */
/* as published by the Free Software Foundation; either version 3            */
/* of the License, or (at your option) any later version.                    */
/*                                                                           */
/* This program is distributed in the hope that it will be useful,           */
/* but WITHOUT ANY WARRANTY; without even the implied warranty of            */
/* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the             */
/* GNU Lesser General Public License for more details.                       */
/*                                                                           */
/* You should have received a copy of the GNU Lesser General Public License  */
/* along with this program; if not, write to the Free Software               */
/* Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301, USA.*/
/*                                                                           */
/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
 
/**@file   class_pricingcontroller.h
 * @brief  pricing controller managing the pricing strategy
 * @author Christian Puchert
 */
 
/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
 
#ifndef CLASS_PRICINGCONTROLLER_H_
#define CLASS_PRICINGCONTROLLER_H_
 
#include "colpool.h"
#include "pricestore_gcg.h"
#include "class_pricingtype.h"
#include "type_gcgpqueue.h"
#include "type_pricingjob.h"
#include "type_pricingprob.h"
#include "objscip/objscip.h"
 
namespace gcg {
 
class Pricingcontroller
{
 
private:
   SCIP*                 scip_;              /**< SCIP instance (master problem) */
   GCG_PRICINGPROB**     pricingprobs;       /**< pricing problems */
   int                   npricingprobs;      /**< number of pricing problems */
   int                   maxpricingprobs;    /**< capacity of pricingprobs */
   GCG_PRICINGJOB**      pricingjobs;        /**< pricing jobs */
   int                   npricingjobs;       /**< number of pricing jobs */
   int                   maxpricingjobs;     /**< capacity of pricingjobs */
 
   /* parameters */
   int                   heurpricingiters;   /**< maximum number of heuristic pricing iterations per pricing call and problem */
   int                   maxheurdepth;       /**< maximum depth at which heuristic pricing should be performed (-1 for infinity) */
   char                  sorting;            /**< order by which the pricing problems should be sorted */
   int                   nroundscol;         /**< number of previous pricing rounds for which the number of improving columns should be counted */
   int                   chunksize;          /**< maximal number of pricing problems to be solved during one pricing loop */
   int                   eagerfreq;          /**< frequency at which all pricing problems should be solved */
 
   /* strategy */
   GCG_PQUEUE*           pqueue;             /**< priority queue containing the pricing jobs */
   SCIP_Real*            score;              /**< scores of the pricing problems */
   int                   maxniters;          /**< maximal possible number of pricing iterations */
   int                   nchunks;            /**< number of pricing problem 'chunks' */
   int                   curchunk;           /**< index of current chunk of pricing problems */
   int                   startchunk;         /**< first chunk considered in a pricing call */
   PricingType*          pricingtype_;       /**< current pricing type */
 
   /* statistics */
   int                   eagerage;           /**< iterations since last eager iteration */
   int                   nsolvedprobs;       /**< number of completely solved pricing problems during the current pricing loop */
 
 
public:
   /** default constructor */
   Pricingcontroller();
 
   /** constructor */
   Pricingcontroller(SCIP* scip);
 
   /** destructor */
   virtual ~Pricingcontroller();
 
   SCIP_RETCODE addParameters();
 
   SCIP_RETCODE initSol();
 
   SCIP_RETCODE exitSol();
 
   /** pricing initialization, called right at the beginning of pricing */
   SCIP_RETCODE initPricing(
      PricingType*          pricingtype         /**< type of pricing */
   );
 
   /** pricing deinitialization, called when pricing is finished */
   void exitPricing();
 
   /** setup the priority queue (done once per stabilization round): add all pricing jobs to be performed */
   SCIP_RETCODE setupPriorityQueue(
      SCIP_Real*            dualsolconv         /**< dual solution values / Farkas coefficients of convexity constraints */
   );
 
   /** get the next pricing job to be performed */
   GCG_PRICINGJOB* getNextPricingjob();
 
   /** add the information that the next branching constraint must be added,
    * and for the pricing job, reset heuristic pricing counter and flag
    */
   SCIP_RETCODE pricingprobNextBranchcons(
      GCG_PRICINGPROB*      pricingprob         /**< pricing problem structure */
      );
 
   /** set an individual time limit for a pricing job */
   SCIP_RETCODE setPricingjobTimelimit(
      GCG_PRICINGJOB*       pricingjob          /**< pricing job */
      );
 
   /** update solution information of a pricing problem */
   void updatePricingprob(
      GCG_PRICINGPROB*      pricingprob,        /**< pricing problem structure */
      GCG_PRICINGSTATUS     status,             /**< new pricing status */
      SCIP_Real             lowerbound,         /**< new lower bound */
      int                   nimpcols            /**< number of new improving columns */
      );
 
   /** update solution statistics of a pricing job */
   void updatePricingjobSolvingStats(
      GCG_PRICINGJOB*       pricingjob          /**< pricing job */
   );
 
   /** decide whether a pricing job must be treated again */
   void evaluatePricingjob(
      GCG_PRICINGJOB*       pricingjob,        /**< pricing job */
      GCG_PRICINGSTATUS     status             /**< status of pricing job */
      );
 
   /** collect solution results from all pricing problems */
   void collectResults(
      GCG_COL**             bestcols,           /**< best found columns per pricing problem */
      SCIP_Bool*            infeasible,         /**< pointer to store whether pricing is infeasible */
      SCIP_Bool*            optimal,            /**< pointer to store whether all pricing problems were solved to optimality */
      SCIP_Real*            bestobjvals,        /**< array to store best lower bounds */
      SCIP_Real*            beststabobj,        /**< pointer to store total lower bound */
      SCIP_Real*            bestredcost,        /**< pointer to store best total reduced cost */
      SCIP_Bool*            bestredcostvalid    /**< pointer to store whether best reduced cost is valid */
      );
 
   /** check if the next chunk of pricing problems is to be used */
   SCIP_Bool checkNextChunk();
 
   /** decide whether the pricing loop can be aborted */
   SCIP_Bool canPricingloopBeAborted(
      PricingType*          pricingtype,        /**< type of pricing (reduced cost or Farkas) */
      int                   nfoundcols,         /**< number of negative reduced cost columns found so far */
      int                   nsuccessfulprobs    /**< number of pricing problems solved successfully so far */
      ) const;
 
   void resetEagerage();
 
   void increaseEagerage();
 
   /** for a given problem index, get the corresponding pricing problem (or NULL, if it does not exist) */
   GCG_PRICINGPROB* getPricingprob(
      int                   probnr              /**< index of the pricing problem */
      );
 
   /** get maximal possible number of pricing iterations */
   int getMaxNIters() const;
 
 
private:
   /** comparison operator for pricing jobs w.r.t. their solution priority */
   static
   SCIP_DECL_SORTPTRCOMP(comparePricingjobs);
 
   /** for each pricing problem, get its corresponding generic branching constraints */
   SCIP_RETCODE getGenericBranchconss();
 
   /** check if a pricing job is done */
   SCIP_Bool pricingprobIsDone(
      GCG_PRICINGPROB*      pricingprob        /**< pricing problem structure */
      ) const;
 
   /** check whether the next generic branching constraint of a pricing problem must be considered */
   SCIP_Bool pricingprobNeedsNextBranchingcons(
      GCG_PRICINGPROB*      pricingprob        /**< pricing problem structure */
      ) const;
};
 
} /* namespace gcg */
#endif /* CLASS_PRICINGCONTROLLER_H_ */