v1.1.1
CPTP v1.1.1
This minor version doesn't add much functionality, it's mostly about fixing and rounding edges here and there.
See changes of v1.1.0 release
New features
- Partially implemented #10:
VIOLATION_TOLERANCE
, a constant baked at compile time, is specified independently for each cut. When the cut does not violate the constraint within theVIOLATION_TOLERANCE
appreciable tolerance, it is not separated. In the future, we aim to remove this constant and make the violation tolerance more dynamic. - Closed #14: Added capacity lower bound constraint to improve the linear relaxation.
- Closed #7: Implemented
2-OPT
refinement for warm start solutions. After the insertion heuristic creates a valid warm start solution, it is refined using2-OPT
to try to improve it. At a first glance, it doesn't seem to achieve remarkable results.
Fixes and improvements
- Removed the now redundant
zero_reduced_cost_threshold
variable. This variable was introduced as a hack for modeling BaPCod reduced cost variables. Now from the CVRP application that we implemented in BaPCod, before generating the instances used for CPTP, we compute the duals (profits for each node) using the reduced cost variables. We then output a normal CPTP problem instance composed of euclidean distance between cities, and profits associated to each city and the depot. Thezero_reduced_cost_threshold
is now redundant and thus removed.- Removed parsing of
ZERO_REDUCED_COST_THRESHOLD
field in VRPLIB parsersrc/parser.c
- Removed parsing of
- Introduced
COST_TOLERANCE
constant. A valid reduced cost tour is reported only if it is less thanCOST_TOLERANCE=-1e-6
which is the default constant imposed in BaPCod. - Improved handling of infeasible solutions, both from
cptp
executable and from theperfprof
wrapper program.