CapacitatedFacilityLocationBlock

test/CapacitatedFacilityLocationBlock

A tester which provides initial tests for CapacitatedFacilityLocationBlock, possibly MCFBlock and MCFSolver, possibly BinaryKnapsackBlock and any specialised Solver for it, possibly LagrangianDualSolver, LagBFunction, BendersBFunction, any CDASolver able to handle C05Function in the Objective (such as BundleSolver), any Solver able to handle (Mixed Integer) Linear Programs (such as MILPSolver and its derived classes CPXMILPSolver , GRBMILPSolver, etc.), as well as for quite a lot of the mechanics of the "core" SMS++ library.

This executable, given the filename and (optionally) filetype of one Capacitated Facility Location (CFL) instance in one of the several supported file formats, reads the instance in a CapacitatedFacilityLocationBlock. It then creates one or more other Block via the R3Block mechanism; each can be either another CapacitatedFacilityLocationBlock or a MCFBlock representing the continuous relaxation of CFL (as a Min-Cost Flow problem). What they are is the list of formulations given with -F, a SimpleConfiguration< std::vector< Configuration * > >: its first element is the pair BlockConfig + BlockSolverConfig of the original Block, each of the others the vector of three Configuration of an R3Block, the one it is made with [see get_R3_Block()], its BlockConfig and its BlockSolverConfig. Also, an UpdateSolver is manually registered to the original CapacitatedFacilityLocationBlock for each R3Block, so that any change on it is automatically map_forward-ed to the other Block (but not vice-versa).

According to the value of the -s parameter, the Slope Scaling iterations, this is all: the Solver are supposed to be exact (but it may well be that they are all exactly solving the continuous relaxation), and the lower bounds of all of them, those of the original Block and those of every R3Block, are compared with each other.

Otherwise, the first Solver attached to each R3Block is supposed to be solving some kind of continuous relaxation and a certain number of rounds of a simple slope scaling heuristic are ran on that Block: the continuous solution is map_back-ed to the original CapacitatedFacilityLocationBlock, it is used to temporarily change the facility costs according to the standard slope scaling idea, and then it is rounded up to obtain a feasible solution (in this case expecting that the CapacitatedFacilityLocationBlock is in the "splittable" version where continuous X[ i ][ j ] variables are feasible). This is repeated for a maximum number of iterations, or until the solution (value) of the relaxation stops changing. In this case the results (both lower and upper bound) are compared with the optimal value of the other Solver, but not expecting them to be equal. Note that there are at least four significantly different implementations for the R3Block and its Solver:

• The R3Block is a CapacitatedFacilityLocationBlock (in any formulation) and the Solver is, say, a :MILPSolver solving its continuous relaxation by standard LP tools, possibly with the dynamic generation of the strong forcing constraints to improve the bound.

• The R3Block is a MCFBlock solved by a MCFSolver: a much weaker bound, and the much worse/more fractional solution that comes with it, but obtained (possibly, much) faster.

• The R3Block is a CapacitatedFacilityLocationBlock in the KF and the Solver is a LagrangianDualSolver, say using BundleSolver to drive the solution of the Lagrangian Dual and DPBinaryKnapsackSolver to solve the Lagrangian subproblems: a much stronger bound, and the much better/less fractional solution that comes with it, but obtained at a (much) higher computational cost.

• The R3Block is a CapacitatedFacilityLocationBlock in the "Benders friendly" formulation (BenForm), whose hidden BendersBFunction separates Benders optimality/feasibility cuts from an inner MCFBlock; solved as a pure LP with an explicit user-cut separation loop (MILPSolver with intRelaxIntVars == 2), it reproduces the natural-formulation LP bound.

This shows how these completely different arrangements can be obtained with exactly the same executable by just changing the configuration files. Each arrangement is one list of formulations, all in this directory: CFLBForm.txt (natural-formulation LP vs flow relaxation), CFLBForm-mcf.txt (the same with the LEMON solvers first), CFLBForm-cuts.txt (LP + user cuts), CFLBForm-ld.txt and CFLBForm-ldvscuts.txt (Lagrangian dual of the knapsack relaxation) and CFLBForm-ben.txt (the Benders formulation), which name the CFLBCfg-*.txt and MCFBCfg.txt BlockConfig, the CFLBSCfg-*.txt and MCFBSCfg*.txt BlockSolverConfig and the R3BCfg-copy.txt and R3BCfg-MCF.txt R3Block Configuration. All the batch scripts live in batches; each one runs from this directory and gives its list.

All this is possibly repeated a number of times in a loop where data of the CFLproblem (fixed and transportation costs, demands, capacities, facilities being open, closed or fixed-open, and the problem being splittable or not) are modified at random. Note that:

• changing the problem type will not go well with the slope scaling heuristic, since that only works with the splittable version of the problem;

• the MCF R3Block has an unavoidable issue with negative facility costs, that should therefore be avoided if one wants to be sure that the optimal values of the continuous relaxation coincide (see NEGATIVE\_F\_COSTS in test.cpp);

• Many MCFSolver are based on the algorithms of the rather old MCFClass project, that have a questionable habit of requiring well-scaled absolute numerical tolerances to work; this may be necessary, again, when testing the MCFBlock R3Block (see SET\_EPS in test.cpp, and please don't complain that this is not Solver-independent as it should be: it's the MCFClass solvers that are not properly implemented).

The usage of the executable is the following:

  ./CFL_test name -F formulations [-t typ] [-s niter] [-e seed] [-k wchg]
             [-n #rounds] [-m #chng] [-q %chng] [-T cmptol]
  typ = [C], F, L, ignored if name ends in .nc4
  niter: how many Slope Scaling iterations [0]
  seed: seed of the random generator [1]
  wchg: what to change, coded bit-wise [31]
        0 = facility cost, 1 = transportation cost
        2 = capacities, 3 = demands
        4 = close, 5 = re-open, 6 = fix-open fac.
        7 = change problem type (split/unsplit)
        8 (+256) = change abstract representation
        9 (+512) = set eps & no negative design
  #rounds: number of changing rounds [40]
  #chng: average number of elements to change [10]
  %chng: probability of any single change [0.5]
  cmptol: relative tolerance of the comparison of the bounds [1e-5]

The batches folder collects all the batch scripts; each runs the test on a set of CFL instances taken from the data/ folder of the CapacitatedFacilityLocationBlock repo (not the very large ones, so that the tests end in reasonable time):

• batch / batch-s: the default arrangement (natural-formulation LP vs the MCF flow relaxation), on a largish / small set of instances respectively;
• batch-mcf: the MCF flow-relaxation arrangement;
• batch-ben: the Benders-formulation arrangement;
• batch-cuts: the LP + user-cuts arrangement;
• batch-ld / batch-ldvscuts: the Lagrangian-dual (knapsack relaxation) arrangement.

The -s scripts are restricted to instances small and easy enough that the test can be run while solving them to integer optimality (required, e.g., to test changing the problem type from splittable to unsplittable). Whenever the R3Block is the MCF flow relaxation (the default and batch-mcf) the wchg bitmask must include the +512 bit ("set eps & no negative design"), otherwise the natural-LP and MCF bounds diverge after a few modification rounds. Only the scenarios that currently pass are registered with ctest (see the CMakeLists.txt for the per-batch status); the batch-ld and batch-ldvscuts arrangements are known to be broken and are kept off.

A makefile is also provided that builds the executable including the LagrangianDualSolver module, the BundleSolver module, the MILPSolver module, the MCFBlock module, the BinaryKnapsackBlock module, together of course with the core SMS++ library.

A second tester, CFL_BDS_test, puts the two Benders decompositions of the same instance one against the other: the ad hoc one the Block carries in its BenForm formulation, where the BendersBFunction separating the cuts is hidden inside it and its subproblem is an MCFBlock, and the generic one of BendersDecompositionSolver, which is given the same problem written as a master holding the facility-opening Variable and one transportation sub-Block per customer. The two describe one problem, hence what is checked is that they agree with each other and with the monolithic solve, and what is reported is what each of them costs, in the convex regime and in the MILP one, with and without the Pareto-optimal cuts. It is built only where BendersDecompositionSolver is in the build, the rest of the suite running without it, and it reads one of the ORLib instances the Block downloads and unpacks.

All the tests passing give some confidence that no regressions have been done for the involved Block (CapacitatedFacilityLocationBlock, MCFBlock, and BinaryKnapsackBlock) and the Solver used in the solution process.

The scenarios of a facility location, and their reduction

CFLScenarioGenerator reads a facility location instance and writes a set of scenarios out of it, the uncertainty being the demand of the customers, plus the TwoStageStochasticBlock that carries them, which is what the reduction reads:

./CFLScenarioGenerator -i <instance.nc4> -o <scenarios.nc4>
                       --tssb-output <tssb.nc4> -n 50 -v 0.5 -s 1
                       --no-validate

-i is the instance (required), -o where the scenarios go, --tssb-output the file the reduction reads, -n how many scenarios, -v how much the demand varies between them, -s the seed, and --no-validate skips a slow feasibility check, which also makes what is written depend on the seed alone. How many scenarios there are is fixed when the file is written, so a sweep over that number is a file each.

The reduction is asked of TSSB_scenred_test, the generic tester of the scenario reduction of the TwoStageStochasticBlock suite, which reads the same file whatever Block wrote it:

./TSSB_scenred_test -i <tssb.nc4> -m cssc -r 5 -c BSCfg-scenred.txt

with -m the method (baseline, dupacova, bestfit, firstfit, cssc), -r how many representatives to keep and -c the BlockSolverConfig. What it prints is the value of the whole set, the value of the reduced one and the relative difference between the two, which is how well the representatives stand for the whole.

batches-scenred/batch walks the two steps over instances, numbers of scenarios and of representatives and methods, writing one file per number of scenarios since the reduction cannot take a smaller set out of a larger pool, and collects what each run gives into a CSV.

Authors

• Antonio Frangioni
  Dipartimento di Informatica
  Università di Pisa

License

This code is provided free of charge under the GNU Lesser General Public License version 3.0 - see the LICENSE file for details.