Main classes: BB_prob, BB_tm, and BB_lp

The main classes are BB_prob, BB_tm, and BB_lp. The class BB_prob (file include/BB.hpp) is used for the problem description and contains the definitions for handling core and indexed constraints. This is the class that the user modifies to store additional information about the problem.

The class BB_tm (tree manager) contains a single object of type BB_prob, named desc, holding the description of the problem (user data). The remaining functions are essentially those for setting up the LP at the root, and for packing and unpacking algorithmic cuts.

The class BB_tm (file include/BB_tm.hpp) is derived from the class BB_tm_user (file COIN/Bcp/include/BCP_tm_user.hpp). Some of the data members in BB_tm are:

• BB desc : object holding the description of the problem.

• double EPSILON : value used for numerical precision when comparing numbers of type double. This value is only for the user calculations, BCP having its own parameter for numerical precision. (BCP uses the value set for numerical precision in the LP solver.)

• bool *integer : integer[$j$] = true if and only if variable $j$ is an integer variable;

• double *clb, *cub : clb[$j$] = lower bound on variable $j$. cub[i]: upper bound on variable $j$. (Use $\pm$DBL_MAX for unbounded variables.)

• double *obj : obj[j] = objective value coefficient of variable $j$.

• *rlb_core, *rub_core : rlb_core[$i$] = lower bound for core constraint $i$. rlb_core[$i$] = upper bound for core constraint $i$.

• *rlb_indexed, *rub_indexed : rlb_indexed[$i$] = lower bound for indexed constraint $i$. rlb_indexed[$i$] = upper bound for indexed constraint $i$.

• CoinPackedMatrix *core, *indexed : matrices holding the coefficients of the core and indexed constraints. Core constraints will be transmitted to BCP through the function initialize_core() and BCP will manage them. Indexed constraints are managed by the user who decides which of them should be added to the formulation at the node level. Once an indexed constraint (or algorithmic cut) is added to the formulation at node $S$, it will remain in the formulation of all children of $S$, until deleted by BCP (based on row effectiveness).

Prominent function members in BB_tm are:

• readInput() : reads input data.

• pack_module_data() : packs the data stored in BB_prob that the user wants to be available at the nodes of the tree. The corresponding unpacking function unpack_module_data() is in the class BB_lp (in file LP/BB_lp.cpp). In the example, this function is quite simple, as it simply writes the address of the object desc of class BB_prob. (This is the type of packing that is impossible to use to run the program on parallel machines).

• pack_cut_algo() : encodes algorithmic cuts. It uses the packing function defined in the class BB_cut (files include/BB_cut.hpp and Member/BB_cut.cpp).

• unpack_cut_algo() : decodes encoded algorithmic cuts. It uses one of the constructors defined in the class BB_cut (files include/BB_cut.hpp and Member/BB_cut.cpp).

• initialize_core() : Transmits core constraints and core variables to BCP.

• display_feasible_solution() : self explanatory.

The class BB_lp contains the functions operating at the nodes of the tree: cut generation, branching selection, and heuristic solution generation among others. The main loop (exited by fathoming or branching decision) performs the steps in the following order (steps followed by a ``(u)'' indicate that the user has an entry point for that step):

• Initialize the new node (u).
• Solve the node LP.
• Test the feasibility of the node LP solution (u).
• Update the lower bound for the node LP.
• Fathom the node (if possible).
• Perform (logical, reduced cost) fixing on the variables (u).
• Update the row effectiveness records.
• Generate cuts (u).
• Generate a heuristic solution (u).
• Fathom the node (if possible).
• Decide to branch, fathom, or repeat the loop (u).
• Add to the node LP the cuts generated during the iteration, if the loop is repeated.
• Purge the constraint pool.

Note that if, in an iteration, cuts are generated but the decision to branch is taken, then the cuts are discarded unless the next node to be processed is one of the sons of the current node.

It is important to realize that BCP creates a single object of type BB_lp for the whole enumeration, instead of creating one per node of the enumeration tree. (This holds for a non-parallel execution; in the parallel case, BCP creates one such object per processor used to process nodes.) The data members are of course updated at each node of the tree, but the same object is used throughout the enumeration. This is somewhat counter-intuitive in an object-oriented setting, but is motivated by efficiency reasons: The amount of data that the user needs when processing a node might be quite large. Copying and sending it for each node would be rather inefficient. This implies that variables that the user add to the description of the class might need to be initialized somewhere else than in the constructor of BB_lp. The function initialize_new_search_tree_node() described below is available for this.

Some of the data members in class BB_lp are:

• BB *p_desc : pointer to the object desc of class BB_tm.

• int in_strong : An integer variable having value 1 while BCP is performing strong branching and zero otherwise. Its use will be explained below when describing the function test_feasibility().

• double EPS : A double holding the value of EPSILON defined in BB_prob.

• BCP_vec<BCP_cut*> algo_cuts : vector to hold pointers to algorithmic cuts generated but not yet transmitted to BCP.

• BCP_vec$<$int$>$ violated_cuts : Vector used to store the indices of the indexed cuts violated by the current LP solution.

Prominent function members in BB_lp are:

• initialize_solver_interface() : Entry point to communicate with the LP solver at the beginning of the execution (called only once from the root node). In the example, this function is used to turn off the printing of the output of CLP.

• initialize_new_search_tree_node() : Entry point at the beginning of the processing of a node. The associated LP is set up but not yet solved. Natural place for initializing user defined variables of BB_lp.

• modify_lp_parameters() : Called each time an LP is solved by the LP solver. Used primarily for changing the maximum number of simplex iterations to perform while doing strong branching. It is also used to set the variable in_strong to its correct value and to print the current node LP in the file lpnode.mps.

• test_feasibility() : If the current LP is feasible, the LP solution satisfies in particular all core constraints, but the user has to check himself if the indexed and algorithmic cuts not in the current LP are satisfied too. If some of these cuts are violated, they can be immediately transmitted to BCP through the function parameter cuts. In the example, an alternative way is used: the two vectors violated_cuts and algo_cuts are holding indices or pointers to the violated cuts and these will be transmitted to BCP in the function generate_cuts_in_lp(). If all the indexed and algorithmic cuts are satisfied, the user still has to check if the LP solution satisfies the integrality conditions. This is done by calling the function BCP_lp_user::test_feasibility(). The return value of the function is either a pointer to the current LP solution (when it is a feasible solution for the initial problem too) or the NULL pointer (otherwise).

  The function BB_lp::test_feasibility() is also called while the process is solving LPs for selecting the branching variable during strong branching. This is useful in particular in applications where heuristic solutions are generated during the feasibility check. In the example, the function returns immediately when it is called while doing strong branching (i.e. when called with in_strong == 1).

  The function is also called when the LP is infeasible. While this does not make much sense for a Branch-and-Cut, it does when column generation is possible. In the example, the function returns immediately if the last solved LP is infeasible.

• logical_fixing() : Empty function in the example. Might be useful for other applications.

• generate_cuts_in_lp() : Transmits to BCP the violated indexed cuts and generated algorithmic cuts. BCP can easily use the functions defined in the Cut Generation Library (CGL) included in COIN. Among others, Gomory cuts, Knapsack covers, Lift-and-Project, and Odd Hole cuts are available. See the example BranchAndCut for more on this.

• generate_heuristic_solution() : self explanatory. The function is active in the example only if the compilation flag HEUR_SOL is used. (See Section 4.) In the example, the solution simply rounds the current LP solution and checks if this rounded solution is feasible. The code is of course very similar to the code of the function test_feasibility() since the checking of indexed and algorithmic cuts is done in both functions. Introducing functions for those tests would certainly make sense, but this was not done to keep the code as simple as possible. The predefined type BCP_solution_generic derived from BCP_solution is used to encode the solution. (See files COIN/Bcp/include/BCP_solution.hpp and COIN/Bcp/Member/BCP_solution.cpp.)

• select_branching_candidates() : The function is active in the example only if the compilation flag CUSTOM_BRANCH is used. (See Section 4.) In the example, the variables are considered in order and branching is performed on the first fractional variable.

• cuts_to_rows() : Required function when algorithmic or indexed cuts are used. It describes how to get a row of the constraint matrix from the representation of the cut. If BB_cut is used, the two representations are close and this might seem to be a redundant function. However, for some problems, it is possible to store a cut in a compact form avoiding the storage of all its non-zero coefficients. (An extreme example of this is the case of the indexed cuts.) The function generating the coefficients from the compact representation is then necessary.