How to add variable pricers

A pricer performs the dynamic generation of new variables in a column generation algorithm. It is an algorithmic representation of a (usually exponential) number of variables. The PRICERREDCOST and PRICERFARKAS methods are called after each LP solve to generate additional variables which may improve the objective value or decrease the LP infeasibility, respectively.
A complete list of all pricers contained in this release can be found here.

If the pricer finds one or more variables with negative reduced costs or negative Farkas value, it should call SCIPcreateVar() and SCIPaddPricedVar() to create and add the variable to the problem. Additionally, the pricer has to add the variable to all constraints in which it appears. Therefore, a pricer needs to know the constraints of the model and their meaning. Note that all constraints for which additional variables are generated by a pricer have to be flagged as "modifiable" in the SCIPcreateCons() call.

We now explain how users can add their own pricers. For example, look into the variable pricer for the binpacking problem (examples/Binpacking/src/pricer_binpacking.c) of the Binpacking example project. The example is written in C. C++ users can easily adapt the code by using the scip::scip::ObjPricer wrapper base class and implement the scip_...() virtual methods instead of the SCIP_DECL_PRICER... callback methods.

Additional documentation for the callback methods of a pricer can be found in the file type_pricer.h.

Notice that if your pricer cannot cope with variable bounds other than 0 and infinity, you have to mark all constraints containing priced variables as modifiable, and you may have to disable reduced cost strengthening by setting propagating/rootredcost/freq to -1.

Here is what you have to do to implement a pricer:

1. Copy the template files src/scip/pricer_xyz.c and src/scip/pricer_xyz.h into files "pricer_mypricer.c" and "pricer_mypricer.h".
   Make sure to adjust your build system such that these files are compiled and linked to your project.
   If you are adding a new default plugin, this means updating the src/CMakeLists.txt and Makefile files in the SCIP distribution.
2. Use SCIPincludePricerMypricer() in order to include the pricer into your SCIP instance, e.g., in the main file of your project (see, e.g., src/cmain.c in the Binpacking example).
   If you are adding a new default plugin, this include function must be added to src/scipdefplugins.c.
3. Open the new files with a text editor and replace all occurrences of "xyz" by "mypricer".
4. Adjust the properties of the pricer (see Properties of a Pricer).
5. Define the pricer data (see Pricer Data). This is optional.
6. Implement the interface methods (see Interface Methods).
7. Implement the fundamental callback methods (see Fundamental Callback Methods of a Pricer).
8. Implement the additional callback methods (see Additional Callback Methods of a Pricer). This is optional.

Properties of a Pricer

At the top of the new file "pricer_mypricer.c" you can find the pricer properties. These are given as compiler defines. In the C++ wrapper class, you have to provide the pricer properties by calling the constructor of the abstract base class scip::ObjPricer from within your constructor. The properties you have to set have the following meaning:

PRICER_NAME: the name of the pricer.

This name is used in the interactive shell to address the pricer. Additionally, if you are searching for a pricer with SCIPfindPricer(), this name is looked up. Names have to be unique: no two pricers may have the same name.

PRICER_DESC: the description of the pricer.

This string is printed as a description of the pricer in the interactive shell.

PRICER_PRIORITY: the priority of the pricer.

In each pricing round during the price-and-cut loop of the subproblem processing, the included pricers are called in a predefined order, which is given by the priorities of the pricers. The higher the priority, the earlier the pricer is called. Usually, you will have only one pricer in your application and the priority is therefore irrelevant.

PRICER_DELAY: the default for whether the pricer should be delayed, if other variables with negative reduced

costs have already been found in the current pricing round. Variables may be declared to be "removable" in the SCIPcreateVar() call. This means that SCIP may remove the variable from the LP if it was inactive (i.e., sitting at zero) for a number of LP solves. Nevertheless, after the removal of the column from the LP, the variable still exists, and SCIP can calculate reduced costs and add it to the LP again if necessary.
If the PRICER_DELAY flag is set to TRUE (which is the common setting), all those existing variables with negative reduced costs are added to the LP, and the LP is resolved before the pricer is called. Thus, the pricer can assume that all existing variables have non-negative reduced costs if the PRICERREDCOST method is called or non-positive Farkas value if the PRICERFARKAS method is called.
In some applications, this inner pricing loop on the already existing variables can significantly slow down the solving process, since it may lead to the addition of only very few variables in each pricing round. If this is an issue in your application, you should consider setting the PRICER_DELAY flag to FALSE. You must, however, be aware of the fact that there may be already existing variables with negative reduced costs. For example, this may lead to the issue that your pricer generates the same variable twice. In some models, this is not critical because an optimal solution would choose only one of the two identical variables anyway, but for other models this can lead to wrong results because the duplication of a variable essentially doubles the upper bound of the variable.

Pricer Data

Below the header "Data structures" you can find a struct which is called "struct SCIP_PricerData". In this data structure, you can store the data of your pricer. For example, it may be convenient to store pointers to the constraints of the problem instance here, because the pricer has to add variables to those constraints. If you are using C++, you can add pricer data, as usual, as object variables to your class.
Defining pricer data is optional. You can leave the struct empty.

Interface Methods

At the bottom of "pricer_mypricer.c" you can find the interface method SCIPincludePricerMypricer(), which also appears in "pricer_mypricer.h". It is called by the user, if (s)he wants to include the pricer, i.e., if (s)he wants to solve a model for which variables should be generated by this pricer.

This method only has to be adjusted slightly. It is responsible for notifying SCIP of the presence of the pricer. For this, you can either call SCIPincludePricer(), or SCIPincludePricerBasic() since SCIP version 3.0. In the latter variant, additional callbacks must be added via setter functions as, e.g., SCIPsetPricerCopy(). We recommend this latter variant because it is more stable towards future SCIP versions which might have more callbacks, whereas source code using the first variant must be manually adjusted with every SCIP release containing new callbacks for pricers in order to compile.

In addition, the pricer has to be activated before the solution process starts, like it is done in the pricer of the Coloring application (applications/Coloring/src/reader_col.c) by calling

SCIP_CALL( SCIPactivatePricer(scip, SCIPfindPricer(scip, "coloring")) );

If you are using pricer data, you have to allocate the memory for the data at this point. You can do this by calling:

SCIP_CALL( SCIPallocBlockMemory(scip, &pricerdata) );

You also have to initialize the fields in struct SCIP_PricerData afterwards.

You may also add user parameters for your pricer, see the method SCIPincludePricerColoring() in the pricer of the Coloring application for an example of how to add user parameters.

Fundamental Callback Methods of a Pricer

The fundamental callback methods have to be implemented in order to obtain an operational algorithm. They are passed together with the pricer itself to SCIP using SCIPincludePricer() or SCIPincludePricerBasic(), see Interface Methods.

In the case of a pricer, there are two fundamental callback methods, namely the PRICERREDCOST and the PRICERFARKAS callbacks, which both search for new variables and add them to the problem. These methods have to be implemented for every pricer; the other callback methods are optional. In the C++ wrapper class scip::ObjPricer, the scip_redcost() method (which corresponds to the PRICERREDCOST callback) is a virtual abstract member function. You have to implement it in order to be able to construct an object of your pricer class.

Additional documentation for the callback methods can be found in type_pricer.h.

PRICERREDCOST

The PRICERREDCOST callback is called inside the price-and-cut loop of the subproblem solving process if the current LP relaxation is feasible. It should search for additional variables that can contribute to improve the current LP's solution value. In standard branch-and-price, these are variables with negative dual feasibility, that is negative reduced costs for non-negative variables, positive reduced costs for non-positive variables, and non-zero reduced costs for variables that can be negative and positive.

Whenever the pricer finds a variable with negative dual feasibility, it should call SCIPcreateVar() and SCIPaddPricedVar() to add the variable to the problem. Furthermore, it should call the appropriate methods of the constraint handlers to add the necessary variable entries to the constraints, see pub_cons.h.

In the usual case that the pricer either adds a new variable or ensures that there are no further variables with negative dual feasibility, the result pointer should be set to SCIP_SUCCESS. Only if the pricer aborts pricing without creating a new variable, but there might exist additional variables with negative dual feasibility, the result pointer should be set to SCIP_DIDNOTRUN. In this case, which sometimes is referred to as "early branching", the LP solution will not be used as a lower bound. The pricer can, however, store a valid lower bound in the lowerbound pointer.

Pricers usually need the dual LP solution as input for the pricing algorithm. Since SCIP does not know the semantics of the individual constraints in the problem, the dual solution has to be provided by the constraint handlers. For example, the setppc constraint handler, which deals with set partitioning, packing, and covering constraints, provides the method SCIPgetDualsolSetppc() to access the dual solution value for a single constraint. Similarly, the dual solution of a linear constraint can be queried with the method SCIPgetDualsolLinear() of cons_linear.h. The reduced costs of the existing variables can be accessed with the method SCIPgetVarRedcost().

PRICERFARKAS

If the current LP relaxation is infeasible, it is the task of the pricer to generate additional variables that can potentially render the LP feasible again. In standard branch-and-price, these are variables with positive Farkas values, and the PRICERFARKAS method should identify those variables.

If the LP was proven to be infeasible, we have an infeasibility proof by the dual Farkas multipliers \(y\). With the values of \(y\), an implicit inequality \(y^T A x \ge y^T b\) is associated, with \(b\) given by the sides of the LP rows and the sign of \(y\):

• if \(y_i\) is positive, \(b_i\) is the left hand side of the row,
• if \(y_i\) is negative, \(b_i\) is the right hand side of the row.

\(y\) is chosen in a way, such that the valid inequality \(y^T A x \ge y^T b\) is violated by all \(x\), especially by the (for this inequality least infeasible solution) \(x'\) defined by

• \(x'_i := ub_i\), if \(y^T A_i \ge 0\)
• \(x'_i := lb_i\), if \(y^T A_i < 0\). Pricing in this case means to add variables \(i\) with positive Farkas value, i.e., \(y^T A_i x'_i > 0\).

To apply Farkas pricing, the pricer needs to know the Farkas values of the constraints. Like the dual solution values for feasible LP solutions, the dual Farkas values for infeasible solutions can be obtained by constraint handler interface methods such as the SCIPgetDualfarkasLinear() method of the linear constraint handler. The Farkas values for the bounds of the variables can be accessed with SCIPgetVarFarkasCoef().

It is useful to note that Farkas pricing is the same as the regular pricing with a zero objective function. Therefore, a typical implementation of a pricer would consist of a generic pricing algorithm that gets a dual solution and an objective function vector as input and generates variables by calling SCIPcreateVar() and SCIPaddPricedVar(). The PRICERREDCOST callback would call this function with the regular objective function and the regular dual solution vector, while the PRICERFARKAS callback would call this function with a zero objective function and the Farkas vector. From a practical point of view, it is usually the simplest approach to provide just one Boolean flag to the generic pricing algorithm in order to identify whether it is reduced cost or Farkas pricing. Then, the algorithm would just call the appropriate methods to access the dual solution or objective function, depending on the Boolean flag.

Additional Callback Methods of a Pricer

The additional callback methods do not need to be implemented in every case. However, some of them have to be implemented for most applications. They can either be passed directly with SCIPincludePricer() to SCIP or via specific setter functions after a call of SCIPincludePricerBasic(), see also Interface Methods.

PRICERFREE

If you are using pricer data, you have to implement this method in order to free the pricer data. This can be done by the procedure described in stp/src/pricer_stp.c, see https://scipjack.zib.de/.

If you have allocated memory for fields in your pricer data, remember to free this memory before freeing the pricer data itself. If you are using the C++ wrapper class, this method is not available. Instead, just use the destructor of your class to free the member variables of your class.

PRICERCOPY

The PRICERCOPY callback is executed when the SCIP instance is copied, e.g. to solve a sub-SCIP. By defining this callback as NULL the user disables the inclusion of the pricer into all copied SCIP instances. This means that primal heuristics will work on a sub-SCIP that contains only a part of the variables and no variables are priced in during the solving process of the sub-SCIP. Therefore, primal solutions found in the copied problem are typically still valid for the original problem and used for its solving process, but dual reductions cannot be transferred to the original problem.

Note: If you implement this callback, be careful when setting the valid pointer. The valid pointer should be set to TRUE if (and only if!) you can make sure that all necessary data of the pricer are copied correctly. If the complete problem is validly copied, i.e. if the copy methods of all problem defining plugins (constraint handlers and pricers) return *valid = TRUE, then dual reductions found for the copied problem can be transferred to the original SCIP instance. Thus, if the valid pointer is wrongly set to TRUE, it might happen that optimal solutions are cut off.

PRICERINIT

The PRICERINIT callback is executed after the problem is transformed. The pricer may, e.g., use this call to replace the original constraints stored in its pricer data by transformed constraints, or to initialize other elements of its pricer data.

PRICEREXIT

The PRICEREXIT callback is executed before the transformed problem is freed. In this method, the pricer should free all resources that have been allocated for the solving process in PRICERINIT.

PRICERINITSOL

The PRICERINITSOL callback is executed when the presolving is finished and the branch-and-bound process is about to begin. The pricer may use this call to initialize its branch-and-bound specific data.

PRICEREXITSOL

The PRICEREXITSOL callback is executed before the branch-and-bound process is freed. The pricer should use this call to clean up its branch-and-bound data, which was allocated in PRICERINITSOL.

Further remarks

If you use your own branching rule (e.g., to branch on constraints), make sure that it is able to branch on "pseudo solutions". Otherwise, SCIP will use its default branching rules, if necessary (which all branch on variables). This could disturb the pricing problem or branching might not even be possible, e.g., if all variables created thus far have already been fixed.

Note that if the original problem is a maximization problem, SCIP will transform the problem into a minimization problem by multiplying the objective function by -1. The pricer has to take care of this by multiplying the original objective function value of all variables created during the solving process by -1.

In some cases, bounds on variables are implicitly enforced by constraints of the problem and the objective function. Therefore, these bounds do not need to be added to the LP explicitly, which has the advantage that the pricing routine does not need to care about the corresponding dual values. We call these bounds lazy bounds, they may be set by SCIPchgVarLbLazy() and SCIPchgVarUbLazy() for upper or lower bounds, respectively. If the lazy bound equals the local bound, the corresponding bound is not put into the LP. In diving mode, lazy bounds are explicitly put into the LP, because changing the objective (which is only possible in diving) might reverse the implicitly given bounds. When diving is finished, the bounds are again removed from the LP.