v1.2.0

Fixed some stuff from previous commit

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 the VIOLATION_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 using 2-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. The zero_reduced_cost_threshold is now redundant and thus removed.
  • Removed parsing of ZERO_REDUCED_COST_THRESHOLD field in VRPLIB parser src/parser.c
• Introduced COST_TOLERANCE constant. A valid reduced cost tour is reported only if it is less than COST_TOLERANCE=-1e-6 which is the default constant imposed in BaPCod.
• Improved handling of infeasible solutions, both from cptp executable and from the perfprof wrapper program.

v1.1.0

CPTP v1.1.0

• Implemented PRICER_MODE. Pricer mode allows stopping the MIP optimization as soon a negative reduced cost tour is found, regardless if it is proven to be optimal or not. It is disabled by default when the program is called interactively from the command line, and is enabled by default when the program is called from the perfprof wrapper program.
  • NOTE: There still exist "difficult" instances to which a negative reduced cost incumbent is hard to find (example: when none exist). In this case the PRICER_MODE does not provide any benefit and the problem must be solved optimally regardless.
• Implemented UPPER_CUTOFF using the zero_reduced_cost_threshold by setting the CPLEX param called CPX_PARAM_CUTUP. UPPER_CUTOFF is disabled by default from the command line, but is enabled by default when the program is called from the perfprof wrapper program.
• Implemented a fast Insertion Heuristic based on nearest insertion for feeding the MIP with valid warm start solutions
  • In most cases, the heuristic algorithm can find negative reduced cost tours which allows easily short-circuiting the MIP optimization call in case PRICER_MODE is enabled. Under these conditions, the running times improve tremendously.
• Implemented APPLY_POLISHING_AFTER_WARM_START cmdline argument (disabled by default) which invokes the solutions polishing of the warm start solutions instead of solving the original MIP formulation. Solution polishing doesn't seem to be productive, and for this reason, this feature is disabled by default.
• Implemented Gomory-Hu Tree for fast all pairs (s,t) max-flow/min-cut queries
• Tested and ironed out GSEC cuts separation for both fractional and integral solutions. When GSEC fractional separation is turned on, the MIP formulation can potentially be solved at the root without resulting in any branching. GSEC integral separation is mandatory as it enforces that an optimal incumbent must contain a single sub-tour only.
• Implemented and ironed out GLM cuts separation for both fractional and integral solutions.
• Implemented and tested RCI (Rounded Capacity Inequalities) for both fractional and integral solutions

v1.0.0-alpha

Implemented CPTP cut separation using GSEC applied on full integral solutions