All notable changes to this project will be documented in this file.
To see info about this project, please refer to the Readme.
- Added GZD, BD and GZD+BD tie-breaking policies for LM-Cut
- [3.1.9.2] If we computed LM-Cut but CPLEX couldn't solve the root node due to time limit breaching, CPLEXs lower bound (0) would overwrite LM-Cuts (>0)
- [3.1.9.3] Executing the VDM tie-breaking policy first in LM-cut used unitialized vector
- Option to just execute LM-Cut
- [3.1.9.1] Additional statistics for LM-cut execution
- Better time/memory limit handling
- Gathering LP bounds (Issue #5) with consistent reporting
- [3.1.7.1] Uncaught exception in lmcut computation
- [3.1.7.2] Added integrity check in reading CPLEX solution
- [3.1.7.3] Fixed issues #1,#2 and #4
- [3.1.7.4] Swapped unordered set, which were iterated upon, for a set (determinism across platforms where possible)
- [3.1.7.5] Fixed issue #3 and removed unreliable statistic on root node relaxation (kept relaxation and cutloop lower bounds on custom cutloop)
- Added option to add fractional callbacks to complete (TL and VE) models (aswell as custom cutloop)
- [3.1.6.1] Patch applied to candidate callback: sometimes CPLEX takes too much to realize that a posted solution is the optimal one... if we figure it out before it, we terminate the execution
- [3.1.6.2] Patch applied to vertex elimination model: warm start posted was infeasible (unchecked, so still accepted) due to a wrong construction of vertex elimination graph variables
- Updated defaults for new best model
- lmcC_flmcG_lmcC_hadd with vs without cutloop (3.1.5.1):
- Solved: 2646 -> 2646
- Nodes: +19,-34,-38,-44%
- Time: -5,-10,-0,+4%
- lmcC_lmcC_hadd vs lmcC_flmcG_lmcC_hadd with no cutloop (3.1.5.1):
- Solved: 2619 -> 2648
- Nodes: -33,-72,-80,-97%
- Time: -0,-1,-10,-40%
- New best model is lmcC_flmcG_lmcC_hadd with no cutloop (default values have been updated)
- [3.1.5.1] Missing epsilon in fractional landmark violation check
- [3.1.5.1] Using CPX_USECUT_FILTER in relaxation callback
- [3.1.5.2] Wrong imports in cutloop functions
- [3.1.5.2] Missing error checks in cutloop functions
- Updated greedy implementation
- 3.1.4.1 vs 3.1.5 on compC_lmcutC_hadd:
- Heuristic Time: -39,-27,-21,-28%
- Solved: 2566 -> 2566
- Nodes: -0, -0, -0, -0%
- Time: -2,-4,-5,-2%
- [3.1.4.1] Timelimit implementation slowed down fast instances
- Optimized parsing implementation
- Optimized preprocessing implementation
- 3.1.3 vs 3.1.4.1 on compC_lmcutC_hadd:
- File Parsing Time: -18,-20,-18,-24%
- Preprocessing Time: -33,-28,-17,-11%
- Solved: 2566 -> 2566
- Nodes: -0, -0, -0, -0%
- Time: -17,-16,-4,-0%
- Updated greedy implementation
- Updated hmax/hadd greedy choice implementation
- Execution on MacOS is (sometimes) non-deterministic (this is a CPLEX bug for ARM MacOS)
- Wrong time measurements mess up results for fastest runs
- Execution on MacOS is (sometimes) non-deterministic
- When int separator based on LMcut didn't find any solution, the callback didn't fallback to exact method
- Logger in async mode doesn't print error or success messages being too close to code termination
- Un-handled CPLEX solution status (CPXMIP_FEASIBLE)
- Updated version of logger for bugfixes
- Minor bug fixes and dead/no-op code removed
- Using watch-preconditions (inspired from watch literals in sat solvers) for reachability analysis in landmark minimalization
- Added TODOs on possible future improvements
- Implementation improvements on landmark minimalization algorithm
- Old LMC (just LMcut on integer solutions with minimalization (both greedy and extensive)) vs with new minimalization
- Solved: 2624 -> 2625
- Nodes: -0, -0, -0, -0%
- Time: -4,-0,-5,-4%
- Removed suboptimal use of BinarySet
- Updated BinarySet, Logger implementations
- Using StatsRegistry for timing and statistics
- Landmark minimization in LMcut
- BinarySet pre and eff from actions
- Landmark minimization in LMcut (compared with test run):
- Solved: 2564 -> 2594
- Nodes: -11,-50,-57,-38%
- Time: +57,-30,-40,-24%
- Implementation adjustments (compared with LM min):
- Solved: 2594 -> 2600
- Nodes: -3,-0,-5,-12%
- Time: -31,-21,-33,-14%
- Old baselines are now outdated... need to run new benchmarks to find the best model
- Fixed precision errors for close-to-0 values in fractional LMcut separator
- Smarter landmark selection in LMcut
- Additional init() removed 0ing of used actions in lmcut int separator
- Updated LMcut implementation
- Precise time measuring for LMcut in preprocessing
- Unchanged performances
- Option to use LMcut to separate violated landmark constraints from integer solutions
- Violated landmark constraints can now be separated using the LMcut algorithm, by setting the reduced costs of used actions to 0 (note that this separation procedure is not complete when there are 0-cost actions, so it will be complemented by the complementary landmark separation procedure)
- Old LMC (just comp) vs new LMC (comp + lmc, no separation on fractional solutions):
- Solved: 2520 -> 2582
- Nodes: -58,-3,-56,-17%
- Time: -36,+15,-41,-28%
- Best (FLM with minimalization) vs new LMC (comp + lmc, no separation on fractional solutions):
- Solved: 2559 -> 2582
- Nodes: -32,+45,+5,+75%
- Time: -20,-7,-26,-32%
- Our Best method now uses both "comp" and "lmc" separation procedures on integer solutions, and doesn't separate landmarks on fractional solutions
- Couldn't properly set the build type
- Lower Bound after cutloop didn't get updated correctly when reaching time limit
- Wrong vector sizes in basic model construction
- Updated list of best known solutions (both structure and added new values)
- Minimalization of (violated) landmark found in relax callback
- Cutoff CLI parameter to be passed to CPLEX as upper cutoff
- Statistic about lower bound before starting the cutloop
- Statistics about LM size in fractional
- Compile time in executable output
- Violated landmarks from fractional solutions are now improved through a local search strategy (minimalization of the landmark)
- Old vs new FLM (Fractional LandMark):
- Solved: 2524 -> 2559
- Nodes: -36,-27,-36,-14%
- Time: -6,-11,-13,-23%
- Best vs new FLM:
- Solved: 2520 -> 2559
- Nodes: -45,-35,-49,-65%
- Time: -2,+2,-16,-10%
- Our Best method now uses FLM with minimalization
- Bug in fractional SEC where we didn't select the smallest-weight edge in the graph construction
- Minor aestetic changes in output
- LM-cut CLI parameter is now a string, so that it's possible to choose how many times to repeat LM-cut and with which pcf each time
- Added missing warnings in CLI parsing
- Removed unused cutval calculation in landmark fract separation
- Little bug with cutloop pruning of non-tight constraints
- Minor code aestetics changes
- Fractional Landmark Separator is now an heuristic: choice of a PCF (thus, an heuristic) and max-flow algorithm to detect violated landmark
- Added random seed choice for reproducibility
- Added LM-cut flag to toggle the use of LM-cut in preprocessing phase
- Fractional Landmarks Separator is now an heuristic with a 95+% accuracy (before it was an exact algorithm, looking for the maximal violated landmark)
- Old vs new FLS:
- Solved: 2516 -> 2522
- Nodes: +26,+27,+69,+50%
- Time: -16,-7,-7,-20%
- Best vs new FLS:
- Solved: 2518 -> 2522
- Nodes: -13,-12,-25,-51%
- Time: +9,+9,+1,+16%
- Removed frontier landmarks from default option (candidate callback)
- Issue with SEC cuts of fractional solution... it was generating cuts that weren't violated (a missing -1 basically T^T)
- Testing sorting of neighbor list for better cycle detection
- Optimizations and other options in candidate callback for SEC cycle detection
- Optimizations in candidate callback for complementary landmarks
- Bug with choice of fractional cuts to use, both in the cutloop or in CPLEX callbacks
- Option to remove fractional cuts at nodes
- Relaxation callback now executes at most once per node, except for nodes with depth 0 (root nodes, either at the start or after a restart)
- Fixed issue with landmark generated from the relaxed solutions
- Bug where lower bound for the cutloop didn't get updated for timelimit termination
- Added insightful comments throughout the codebase
- Fixed bug with LMCUT in version 2.2.6:4 [:5] (25/08/21)
- LM-CUT disjunctive action landmarks for preprocessing (25/08/17)
- Testing random LMCUT preprocessing [:1] (25/08/20)
- Reverting random LMCUT preprocessing to arbitrary [:2] (25/08/20)
- Testing combination of multiple tie breaking in LMCUT [:3] (25/08/21)
- Randomization as second level tie-breaking for VDM in LMCUT [:4] (25/08/21)
- Testing another combination of tie-breaking in LMCUT [:6] (25/08/22)
This is the Master Thesis version (results of this version shown in my Master's Thesis)
- Added parameters for cutloop (25/07/17)
- Added test script for testing on small sets of instances (25/07/17)
- Added test scripts for results analysis
- Missing cutloop time in batch test results script
- Improved Readme
- Improved help output
- Changed cutloop termination policies priorities
- First implementation of custom cutloop -> only landmarks and basic termination condition (25/07/09)
- Added questions for Salvagnin and TODOs (25/07/09)
- Added S.E.C. detection for custom cutloop (25/07/14)
- Added In-Out strategy (25/07/14)
- Parametrized Cutloop and In-Out parameters
- Bug with the closing of flmdet model (25/06/28)
- Removed some magic numbers for better code clarity
- Now compiling with a specific version of CPLEX just needs the root directory of CPLEX
- Fixed bug where if memory limit is reached inside CPLEX, an error is thrown
- Fixed bug where if memory limit is reached and no error is thrown (^), the lower bound is not properly updated
- Fixed bug where in some cases, even with optimal solutions the lowerbound and the incumbent, didn't match
- Fixed bug with memory limit in jobs for cluster
- Fixed bug with showing statistics
- Fixed bug with userhandle in callbacks
- Complete code refactoring
- MIP model inside relaxation callback is now set on single thread
- Bug where an infinite loop might occur in the relaxation callback
- Using justification graph to separate SEC in candidate callback
- Separating SEC in fractionary solution
- Using random dominant S.E.C. if multiple (equivalent) cycles are found
- Minor visual bugs
- Bug in CMake file where if a CPLEX path is specified, it is ignored in favour of the defaul ones
- Bug where number of landmarks and SEC where not shown if the relaxation callback wasn't used
- Bug where if no integer solution is found, the lower bound isn't retrieved
- Logger is now thread safe
- Created a copy of the callback data for each thread CPLEX might use
- More meaningful callback statistics (time and cuts added)
- Flag to decide number of threads to use
- Trying different CPLEX parameters
- Added thread safety in relaxation callback
- Stronger landmark filtering in relaxation callback
- Trying violated landmark detection through MIP formulation
- Improved violated landmark detection of fractionary solution
- Added SEC cuts on fractionary solution
- Trying ways of producing cuts off the fractionary solution
- Preparing for ufficial testing and open-sourcing
- Removed Inverse Actions Constraints
- Changed algorithm to find cycles
- Removed probably unnecessary constraint in dynamic model
- Handling CPXMIP_MEM_LIM_FEAS status code
- Added inverse actions constraints in dynamic model
- Added sec cuts in dynamic model
- Fixed CMakeLists with Release build type
- Added complete landmark cuts to dynamic model
- Dynamic model might find wrong optimal solutions
- Slightly better callback in dynamic model
- Added info executable to see info of an instance
- Imai's model finds wrong optimal solutions
- Added dynamic model
- Added references
- Minor changes
- Better results reading script
- Added status, costs, basic info and other cplex execution info to statistics
- Removed well tested integrity checks
- "Optimal" solution provided by the model with tb might not be optimal if problem optimization is being used
- Small changes to the CLI parser
- Smaller number of variables in cplex models
- Added back tighter bounds in Rankooh's model
- Temporarly removed Rankooh's dynamic model
- Changed code organization
- Better CMakeLists.txt file
- "Optimal" solution provided by the model with tb might not be optimal if problem optimization is being used (max_steps might be smaller than the number of fixed actions (0 cost actions))
- Saving cplex logs after tests on cluster
- Handling out of memory CPLEX error
- Storing cplex incumbents update in run results
- Added option to write the lp file
- Removed tighter bounds in Rankooh's and Dynamic models
- Infeasible warm start in Imai's model (sometimes)
- Infeasible warm start in Rankooh's model (sometimes)
- Infeasible warm start in dynamic model (sometimes)
- Hadd heuristic is now the default one
- Changed flag for tighter bounds option
- Tight bounds on every model
- Faster problem simplification
- Imai's model won't validate warm starts for some instances
- Stricter integrity checks in computing heuristic solutions
- Faster greedy-based heuristics
- better candidate actions lookup in greedy-based heuristics
- Trail to restore values after action simulation in hadd-based lookahead heuristic
- Incremental candidate actions in greedy-based heuristics for faster feasible action lookup
- CPLEX log showing every new incumbent
- Removed relax heuristic
- Minor changes to the binary_set related classes
- Changed output logs folder name
- Removing radundant constraints from Rankooh's and Dynamic model
- Showing number of fixed variables in high verbosity settings
- Executable name changed from main to hplus
- Using pq.hxx insthead of std::priority_queue to build the vertex elimination graph
- Added dynamic time model
- Results reading script mis-labeling jobs halted on time limit even if a solution was found
- Results reading script doesn't read final solution if it's not optimal
- mypause method exiting on 0 instead of 1
- Better CMake file
- Using google style as clang-format configuration
- Input file, Run name and Log name prints in show_info() were poorly formatted
- Include errors for Linux
- Started using clang-tidy as static code analyzer
- Imai's model crashes if instance optimization is active
- Posting warm start to Imai's model might not find a feasible solution
- Posting warm start to Rankooh's model finds wrong objective
- Hmaxv1 and haddv1 heur find infeasible solutions even if they aren't
- Faster immediate action application with bs_searcher
- Better access to first adders in model building
- Using immutable objects whenever it's possible
- Added integrity checks to find errors faster
- Heuristics now take into account fixed actions and fixed actions timestamps
- Imai's model crashes if instance optimization is active
- Posting warm start to Imai's model might not find a feasible solution
- Posting warm start to Rankooh's model finds wrong objective
- Script for reading results from logs only read the first heuristic solution found (in randr, we need to read the last one)
- Removed unused imports
- List of remaining variables and actions are calculated on each request, even if after optimization the return is always the same
- Better isint() function
- Instance optimization now removes deleted facts from all effects and precondition
- Changed hmax and hadd function
- New version of hmax and hadd
- Code readability adjustments
- Logger formatting function didn't work properly
- Using std::stringstream to build string representations of pq and bs and formatting assertion error message for logger
- hadd, hmax and relax heuristics
- Little bit of code refactoring
- Errors not showing in log file
- Logs with errors appear in results json file with an empty string as name
- Test scripts modify files or folders before the user confirmed correctness of all paths
- Update best solution didn't perform check on the solution if integrity checks are off (integrity of the solution should always be checked)
- Log output line is now monocromatic
- Modernized logger, binary_set and bs_searcher
- Instances with errors in results json file now show last 5 lines of logs file (for better error understanding)
- Better readability in nested if and for loops
- Errors in paths int cluster jobs scripts
- Using return value of std::set::insert to check if element is actually added to a set
- Documentation for binary_set, bs_searcher and logger classes for future reuse
- Unused private function in logger
- Automatic code formatting with clang-format (cpp) and black-formatter (python)
- Start using attributes ([[nodiscard]], [[likely]], [[unlikely]])
- Help function in test scripts is now resistant to scripts name changing
- Added time-limit control inside heuristic algorithms
- Versioning
- Script to check correctness of a batch run of instances
- Help option to the results reading script
- Added detection of instances with constant cost actions
- ~/code/src/hplus_instance.cpp
- other minor changes