CHANGELOG.md

Changelog

All notable changes to this project will be documented in this file.

The format is based on Keep a Changelog, and this project adheres to Semantic Versioning.

Unreleased

Added

• the makefiles build the C++20 module smspp.singleflowdcrblock when SMSppMOD is not empty (e.g., make SMSppMOD=1), with clang++ 16 or later [see lib/makefile-mod of SMS++]

• SingleFlowDCRBendersSolver reuses its cuts across the calls of compute() with intReuseCuts 1 (0 by default): a call starts from the cuts of an earlier one when the instance is the same save for capacities and speeds that are not larger and costs that are not smaller, which is what makes them valid, as across the iterations of a Lagrangian method whose costs are the original ones plus nonnegative multipliers; the cuts can also be taken out and offered explicitly [see get_cut_memory() and seed_cuts(), and BenBound::getCutMemory() and BenBound::seedCuts()]

• with intWarmLambda 1 (0 by default) the search for the multiplier of DCRLagrangianSolver starts from the critical pairs of the points solved earlier, re-evaluated with the present costs, instead of from 1, and the delay-feasible path found while doubling it is kept as the heuristic value [see DCRLagrangianSolver::setWarmStart()]

• the C++20 module smspp.singleflowdcrblock (src/SingleFlowDCRBlock.cppm), which exports every name that the headers declare at namespace scope and re-exports smspp, so that a source file can write import smspp.singleflowdcrblock; in place of the #include of the headers; it is built with the CMake option SMSpp_BUILD_MODULE, as the target SMS++::SingleFlowDCRBlock_module

Changed

• the Modification of the module say what they change to the constructor of Modification, since changes() is no longer virtual and returns that value, which whoever forwards them can refine with set_changes()

• the pipeline builds the module also with its makefiles, after CMake, and runs on a change of the makefiles too [see ci/makefile of the umbrella]

• SMSpp_BUILD_MODULE no longer stops the configuration when the C++20 module cannot be built, i.e., with a CMake older than 3.28, a generator other than Ninja or Visual Studio, a compiler other than Clang 16 (with clang-scan-deps) or MSVC 19.34, or a module it imports that is not there: the option is turned off with a warning that says why, and the build goes on with the headers [see cmake/CheckModule.cmake of SMS++]

• FACTOR, the oversubscription factor with which MultiFlowDCRBlock::load() computes the mutual capacity of an arc out of the individual ones of a textual instance, is 1 (formerly 0.8), so that the mutual capacity is the sum of the individual ones; the multi-flow instances of data/ are written anew with it, as the data version 2026-10-18, the single-flow ones being the same as before

• the instances of data/ are downloaded and extracted by the targets download_dcr_<fmt> and extract_dcr_<fmt>, written as in every module that keeps its instances in the Package Registry, and the marker of the extraction carries the format in its name, so that a tree extracted before extracts once more

Fixed

• SingleFlowDCRBlockMod says again what it changes to the constructor of Modification: a merge had brought back its changes(), which overrides nothing since Modification::changes() is no longer virtual, and the module did not compile

• the makefiles of the tests and of the tools build also with g++: they take the option that stops at the first error and the one of the debugging information, which clang++ and g++ spell differently (-ferror-limit=1 and -glldb against -fmax-errors=1 and -ggdb), from SMSppSWERR and SMSppSWDBG of lib/makefile-OS of SMS++

0.2.0 - 2026-10-09

Added

• a tester of the module in test/, needing nothing but the core SMS++ and run by ctest -L SingleFlowDCRBlock, which on tiny graphs built in memory compares SPT, both heuristics of DCR_SPT and the two bounds of DCRLagrangianSolver with the enumeration of the paths, and checks the feasibility of given solutions, the netCDF round trip, the feasibility of the instance and the Modification issued by the changes of the SingleFlowDCRBlock, the edge cases (source equal to sink, no path, every path over the deadline, the deadline met with equality, ties, zero-cost, parallel and closed arcs) each on its own

• the instances of the module, as netCDF files downloaded from the Package Registry into data/nc4 [see data/README.md], out of 307 networks in four sets (garr, sndlib, topo and waxman): 3070 SingleFlowDCRBlock, the first 10 flows of each network on its own, and 1535 MultiFlowDCRBlock, each network with its first 1 to 5 flows, which is what a formulation holding all of them solves exactly; the textual instances they are written from are in txt.tgz under the same version, and data/make-nc4 rebuilds the former out of the latter

• tools/dcr2nc4, which writes a MultiFlowDCRBlock out of the multi-file textual format that load() reads, or out of the raw one of the data sets it comes from, possibly keeping its first flows only, or with -s the SingleFlowDCRBlock of one of its flows, each arc with its own capacity and cost, working in a temporary directory, since load() writes its own files in the current one

Changed

• MultiFlowDCRBlock::is_feasible() accepts the relative violation Block::DefaultFeasTol of the core when no Configuration gives a tolerance, instead of none

• whoever links the module keeps it: the classes of a module register themselves in the factory from a static initialiser, and a linker that drops what looks unused takes the registration away with it, so the target now tells whoever links it to keep the symbol that forces the module in, and on ELF, where naming the symbol is not enough, the library as a whole

• chg_costs(), chg_ucaps() and chg_dfcts() take their data as a std::span< const double >, whose length they check against the Range or the Subset instead of reading past the end, and the first two are registered in the methods factory in that form too; the forms taking an iterator stay, and defer to the span ones

Fixed

• a flow ColVariable fixed at a value other than 0 makes the SingleFlowDCRBlock throw, as documented, instead of closing the arc as if it were fixed at 0

• SingleFlowDCRBlock::delay_feasible(), link_feasible() and min_rate() take an arc as used when its x exceeds the tolerance of the check (1e-6 at least, used_threshold()), and check an unused one at x = 0: a solution of Gurobi leaves x of the order of 1e-6 on unused arcs, inside its integrality tolerance, which made r_min that small and the burst delay huge (topo/Heanet_9 of batch-instances), or violated rho x <= r, which the indicator constraints of the model read at x = 0 (topo/Shentel_4)

• load() read m (or n) entries of the capacities and of the delays when they were given empty, which its documentation allows and which means all infinite, or all 0: it looks at them only when they are there

• chg_ucap() did nothing on a SingleFlowDCRBlock whose capacities are all infinite, the test on the new capacity being the other way round

• deserialize() over a SingleFlowDCRBlock that had link delays kept them when the file has none, since they were not cleared with the rest

• is_feasible_instance() counted the closed arcs as usable: they are given an infinite cost, which DCR_SPT now reads as closed

• DCR_SPT routed through the arcs closed with DCRcloseArcs(), whose infinite cost ERA-I could even return as the objective: both heuristics skip them, and ERA-H accepts a path that meets the deadline with equality, as ERA-I does, rather than only one that meets it strictly

• DCRLagrangianSolver could not route through an arc of zero cost at lambda = 0, where its rate came out as sqrt( 0 / 0 ), a NaN the shortest path never takes, so that an instance whose paths all use one was found infeasible: an arc of zero cost reserves its capacity, as one of negative cost does; and after the first LoadProblem() the heuristic value started at 0 instead of +Inf, so that getHeurVal() returned 0 whenever the delay constraint binds

• dcr2nc4 did not build with MSVC, which has no mkdtemp(): the temporary directory of a run is made with std::filesystem::create_directory() on a random name, tried again while the name is already there

• on macOS a program linking the module lost the classes the module registers in the factories when the linker dropped the library, as it does under -dead_strip_dylibs, which conda sets: the target now asks the linker for the symbol that forces the module in (-u), which ld64, unlike the ELF linker, counts as a use of the library

• is_sol_feasible() declared infeasible a routing where an arc the flow does not use reserves a rate of the order of the tolerance of the Solver: r <= U x was checked against a tolerance relative to U x, i.e., an absolute one when x = 0, and it is now relative to U, the size of the terms of the constraint

• a MultiFlowDCRBlock could not be read back from the netCDF file it wrote: serialize() wrote the topology and the costs alone, leaving out the data of the flows, and deserialize() built no SingleFlowDCRBlock and kept the previous instance, so that generating the abstract representation of what it read crashed. The file now holds the mutual capacities, the data of each flow and the SingleFlowDCRBlock of each flow in a group of its own, which deserialize() rebuilds; the matrices of the costs, of the capacities and of the deficits of an earlier file are still read, and no longer written, the costs being in the flows

• map_forward_Modification() passed a change of the deficits on to the other SingleFlowDCRBlock as a change of its capacities, and, when this one had no capacities or no deficits, read them out of the empty vector rather than passing on the infinite capacities and the zero deficits it has

• BenBound.cpp no longer includes unistd.h, which it does not use and which MSVC does not have

0.1.1 - 2026-09-13

Fixed

• is_sol_feasible() reads the DCRSolution, and the Variable are left alone

0.1.0 - 2026-09-12

Added

• the standard SMS++ module build system: the CMake project (with the package configuration files and the version derived from the git tag), the CI for both GitLab and GitHub, and the makefile / makefile-c / makefile-s triple of every other module

• SingleFlowDCRBlock::is_sol_feasible(), which checks the solution held by a DCRSolution without touching the Block, i.e., without requiring its abstract representation to exist at all

• the accessors and the setters of DCRSolution, so that a Solver can fill it directly out of its own data structures

• SingleFlowDCRBendersSolver::get_Solution(), which does exactly that: the DCRSolution is filled out of what BenBound found, and the Variable of the Block are not written at all

• SingleFlowDCRBlock::link_feasible() and delay_feasible(), the two halves of the feasibility check that were nowhere to be found: the constraints tying the reserved rates to the routing decisions, and the end-to-end delay constraint

Changed

• SingleFlowDCRBlock::is_feasible() checks all the constraints of the problem, the bounds of the variables and the two cone constraints comprised, and its "physical" branch reads the solution out of the Variable and checks it against the data, where it used to do nothing

• each of the four feasibility checks has a version taking the solution to be checked from the outside, which is what the "physical" version and is_sol_feasible() both boil down to

• SingleFlowDCRBendersSolver::get_var_solution() also writes the two "aggregate" variables r_min and theta_min, which it used to compute and drop; is_DCR_feasible() asks SingleFlowDCRBlock::delay_feasible() rather than repeating the network calculus formula, and the data of the Block are translated for BenBound in one place instead of two

• SingleFlowDCRBendersSolver::has_var_solution() says no unless the point BenBound stopped at is feasible for the DCR problem, which is now checked in full (the routing, the rates and the delay) and with a tolerance of 1e-6 rather than the 1e-2 of the delay alone; get_ub() accordingly returns +INF where there is no feasible solution, in place of the (possibly optimistic) relaxed value of BenBound::getHeurVal(): neither that value nor the value of an infeasible point bounds the optimum

• SingleFlowDCRBendersSolver::get_var_value() computes the value of the solution BenBound found rather than of whatever the Variable of the Block happen to hold, which is what anybody could have written there

• MultiFlowDCRBlock::is_feasible() asks each commodity sub-Block about the commodity it describes, where it only checked the mutual capacity constraints of its own

• which of the two formulations is in use is asked for in the Configuration of the static Constraint of the BlockConfig, the one of the static Variable being still honoured as it used to be; the two methods that ask no longer disagree on the default, which is the SOCP formulation for both

• SingleFlowDCRBlock::load() takes the starting nodes before the ending ones, as its own documentation says

• get_NodeDelays() and get_LinkDelays() return a reference, as every other datum of the Block does

• the timer of the DCR solvers is the std::chrono-based DCRtimer, which builds everywhere, in place of the POSIX-only OPTtimers

• the version of the module is the git tag of its repository, or the VERSION.txt of a release tarball, and the shared library carries it: its SONAME is major.minor while the major is 0, and it is installed with an RPATH relative to itself, so that an installed tree keeps working wherever it is moved

Removed

• the local copies of OPTUtils.h, OPTtypes.h and OPTvect.h, some 3700 lines of somebody else's code that the module carried around

• SingleFlowDCRBlock::is_feasible_flow(), which did exactly the same checks as is_feasible() under a name saying otherwise

Fixed

• the aggregate cone constraint was added to the abstract representation even when the "P/C" formulation was asked for, so that formulation was not linear at all and a :MILPSolver that does not do conic constraints could not solve it

• the debug output that the solvers wrote on std::cout at every iteration, and the exit( 1 ) calls with which they killed the whole process where they should throw

• is_feasible_instance() read the node deficits, the arc capacities and the delays out of vectors that are allowed to be empty, and left the source and the sink uninitialised when the instance had none

• DCR_SPT::DCRgetLink() fell off the end of the function when the arc was not there, and DCRLagrangianSolver compared a double through the integer abs()

• BenBound moved a trial value of r_min that it had already solved for by shrinking it multiplicatively, which walks past the left endpoint of the window where an r_min can be feasible at all: it could therefore reserve less than the sustained rate of the flow, and hand back a point that is not a solution together with a value below the optimum. The point is now moved towards that endpoint, and stops there