127. BNPBLK - BNP Block Determination

The BNPBLK parameter controls how the the branch-and-price (BNP) solver determines the block structure of the model.  The BNP solver is a mixed integer programming solver for solving models with block structures like the following:

Minimize: Σ c(k) * x(k)
Subject To:
              Σ A(k) * x(k)  =  d        (linking constraints)
              x(k)  in X(k), for all k        (decomposition structure)

where d, c(k) and x(k)  are vectors and A(k) is a matrix with appropriate dimensions.  x(k) contains decision variables and X(k) denotes a linear feasible domain for x(k).

The BNP solver is a hybrid of branch-and-bound, column generation, and Lagrangean relaxation methods.  It can help to find either the optimal solution or a better lower bound (the Lagrangean bound) for a minimization problem.  Based on the decomposition structure, the solver divides the original problem into several subproblems, or blocks, and solves them (almost) independently, exploiting parallel processing if multiple cores are available.

BNP may perform better than the default MIP solver if: a) the number of linking constraints is small, b) the number of blocks is large and they are of approximately the same size, and c) the number of available processors (or cores) is large, e.g., 4 or more.  Also, there may be some models for which BNP finds a good solution and good bound more quickly than the default MIP algorithm, although it may take longer to prove optimality.

The Blocks option for the BNP solver controls the number of subproblems, or blocks, that the model will be partitioned into.  Possible setting for the Blocks parameter are:

•-1 - Row Names - Row names are constructed in such a way as to specify each row's block (an example is given below).
•0 - Off - This will disable the BNP solver, in which case, the standard MIP solver will be used to solve all mixed integer linear programs.
•1 - Specified - The user explicitly specifies each row's block using the @BLOCKROW function.
•N - A positive integer, greater-than-or-equal-to 2, indicating the number of independent blocks to try and partition the model into via one of the graph partitioning algorithms provided by LINGO.  The actual heuristic used is chosen with the Heuristic parameter.

The default setting for Blocks is 0, or Off, i.e., the BNP solver will not be used on integer programming models.

Note:The BNP solver can run the independent subproblems on separate threads to improve performance.  So, if your machine has multiple cores, be sure to set the thread limit to allow for multithreading.  Refer to the NTHRDS parameter above.

For more information on block determination, the BNP solver and the BNPBLK parameter, refer to the section BNP Solver in Chapter 5.