Releases: scipopt/papilo
Releases · scipopt/papilo
v2.4.0
Interface changes
Changed parameters
presolve.abortfac= 0.00080000000000000004: abort factor of weighted number of reductions for exhaustive presolvingpresolve.lpabortfac= 0.01: abort factor of weighted number of reductions for exhaustive LP presolving
New parameters with default values
numerics.useabsfeas= 1: whether to use an absolute tolerance for feasibility checkspresolve.abortfacfast= 0.00080000000000000004: abort factor of weighted number of reductions for fast presolvingpresolve.abortfacmedium= 0.00080000000000000004: abort factor of weighted number of reductions for medium presolvingpresolve.lpabortfacfast= 0.01: abort factor of weighted number of reductions for fast LP presolvingpresolve.lpabortfacmedium= 0.01: abort factor of weighted number of reductions for medium LP presolving
Build system
- updated
FindTBB.cmake - revised the CMake configuration to export the PaPILO dependencies (
papilo-config.cmake)
Fixed bugs
- all fast presolvers: maintain changed activities of current and last round to avoid missing reductions
- FixContinuous: only fix column which contribution deviates by at most epsilon in every row
- Components: identify fixing a component to an optimal solution as strong dual reduction
v2.3.1
Fixed bugs
- DominatedCols: compress set of dominations topologically to avert memory exhaustions
- Input and Output: handle floating point numbers precisely in parsers and writers
- OPB-Parser: handle additional whitespaces
- ParallelColDetection: only merge integral parallel columns for integral column scale
- ParallelColDetection: reduce complexity of hole detection for integral parallel columns
- Probing: eliminate computational overhead in row propagation
- Propagation: handle constraint propagation more carefully by applying feasibility instead of epsilon tolerance
- SimpleSubstitution: correct feasibility tolerances on euclidean coprime substitutions
- SingletonCols: order effective side changes to avoid invalid infeasibility
- SingletonStuffing: normalize and order sides to avoid invalid infeasibility
- Statistics: avoid counting calls of symmetry extensions additionally
- Trivial: mark activity redundancy in trivial row presolving
Build system
- fixed build against HiGHS 1.7.2
- TBB is now no longer download automatically; to enable the download, set option TBB_DOWNLOAD to on
- added check whether linking of libatomic is necessary and possible to make std::atomic available
Known issues
- SingletonCols: normalize if substituting constraint in the objective (when dual-postsolve is active)
v2.3.0
Interface changes
New parameters with default values
- presolve.maxrounds = -1 : maximal number of rounds (-1: unlimited, 0: cleanup)
- introduced preprocessor variable PAPILO_API_VERSION to indicate API changes
Data structures
- statistics have an additional integer variable single_matrix_coefficient_changes to count the coefficient changes apart from variable substitutions and constraint deletions
- add PostsolveStatus to namespace papilo (PAPILO_API_VERSION 1)
Fixed bugs
- SingletonCols: normalize if substituting constraint in the objective (primal-postsolve only)
- Postsolve: round primal solution values close to zero when substituting
- VeriPB: encode INFINITY differently to prevent SIGSEGV if executed in Rational
- VeriPB: encode fixed variables in a separate array to avoid problems with casting infinity
- VeriPB: ensure that numbers are casted to integers when writing in the certificates
- VeriPB: when updating the rhs/lhs of parallel cols distinguish the case factor greater or less than 0
- VeriPB: fix bug leading to endless loop when reconstructing the fractional numbers during sparsify
Known issues
- SingletonCols: normalize if substituting constraint in the objective (when dual-postsolve is active)
- VeriPB: in Rational mode using infinity to encode fixed variables can lead to wrong calculations
v2.2.1
Build system
- header only works now as intended (Boost Serialization)
- add compile option -ffp-contract=off or /fp:precise to enhance reproducibility across different systems
- disable building convMPS and duplicates
Fixed bugs
- DualFix: lock rows if variables are dual-fixed to infinity to avoid conflict when dual-postsolving
- ParallelColDetection: avoid segfault by handling already fixed variables separately during sorting
- ParallelColDetection: mark deleted parallel columns as modified to avoid problems when scanning conflicts during the application of the transactions
- ParallelRowDetection: in dual-postsolving flip bound status of non-basic variable for negative factor
- Propagation: avoid numerical difficulties
- SimpleSubstitution: ensure coprime-ness of coefficients for infeasible detection for linear diphantine equations
- Stuffing: store row to allow correct dual-postsolving
Miscellaneous
- update version of fmt from 6.1.2 to 7.1.3 due to deprecation
- MPS-Parser parses files numerically exactly if rational arithmetic is used
v2.2.0
Performance improvements
- Symmetries: For binary problems ParallelCols adds symmetry-breaking constraints to avoid introducing non-binary integer variables via parameter
Interface changes
- CML: new options dual-reduced-solution/costs-reduced-solution/basis-reduced-solution to pass the dual/reduced costs/basis information of the reduced solution via command-line to PaPILO in the postsolve call
- Boost: program_options is no longer required but needed to use PaPILO via command-line.
New API functions
Changed parameters
New parameters with default values
- verification_with_VeriPB = 0 : should PaPILO print a VeriPB log (only for PseudoBoolean problems)?
- veripb.verify_propagation = 0 : how to log the proof of verification? 0: reverse unit propagation, 1: Addition in polish notation
- parallelcols.symmetries_enabled = 0 : should ParallelCols add symmetry-breaking constraints instead of introducing new variables?
Data structures
Fixed bugs
- SimpleProbing: avoid unstable replacements of columns with small ranges
- if PaPILO solves the problem a backend solver is no longer called
- DualInfer: add percentage of bound change as stop criterium for dual-propagation
- CMake: Libs are available when installing with CMake
Miscellaneous
- Ortools: PaPILO parses the dual solution and the reduced costs from ortools
- HiGHS: PaPILO supports HiGHS version 1.3+
- VeriPB: prints VeriPB 2.0 parseable certificate for pseudo-Boolean problems in the log
- OPB-Format: PaPILO can now parse files in linear opb format
- RoundingSat https://gitlab.com/MIAOresearch/software/roundingsat is available as PseudoBoolean solver
- make testcluster script extended by SKIP_PRESOLVE and SOLVE_EXECUTABLE to solve the reduced/original problem
- make testcluster script extended to verify PaPILO certificates (experimental only)
v2.1.4
Fixed bugs
- DomCol: exclude parallel columns if dual reductions are disabled
- DoubleToNEq: prefer variables with integral scalar over fractional scalar
- DualInfer: check if propagating dual variables leads to infeasibility to return Unbounded or Infeasible
- DualInfer: ensure the primal problem is bounded before changing constraints to equalities
- Substitutions: if applying substitutions lead to small or huge coefficients leading to numerical troubles in the process
v2.1.3
New parameters with default values
- max_consecutive_rounds_of_only_bound_changes = 500: PaPILO resumes with the next higher complexity class if the last n rounds only consisted of bound changes
Fixed bugs
- fixing vector bound checks which failed if compiled with -D_GLIBCXX_ASSERTIONS (Fedora/ArchLinux)
- SingletonRow: consider case if remaining coefficient is close to zero -> could lead to false variable fixings
- increase Priority of FixContinuous to detect numerical difficulties earlier
- ParallelRows: use correct lhs_inf/rhs_inf with negative scale factor under certain circumstances
Miscellaneous
- Boost: minimal 1.81 requirement for Mac since compiler complained about deprecated declarations in Boost
v2.1.2
v2.1.1
v2.1.0
Performance improvements
- ParallelCol: reducing the amount of redundant transactions in case of multiple parallel integer columns
- Probing: checks the time limit condition before propagating a variable
- Probing: introduce new parameter to cap the badgesize
- SequentialMode: execute functions like trivialPresolve only once per round and not after every presolver
Interface changes
- Wrapper in Julia for PaPILO: https://github.com/scipopt/PaPILO.jl
- ProblemBuilder - setColImplInt(int,boolean): (un)sets the Flag Implied Integer for a variable
New parameters with default values
- probing.maxbadgesize = -1 : maximal number of probing candidates probed in a single badge of candidates (-1 deactivated)
- ortools.solver_id = PDLP : LP solver of or-tools
- dualfix.is_fix_to_infinity_allowed = true : should unbounded variables with objective value zero be fixed to infinity?
Data structures
Fixed bugs
- ParallelRowDetection: lhs is updated correctly
- fix fmt error: use correct amount of arguments for print statement
- copy extended_euclidean.hpp during installation
- fix bug in FindTBB module
- ranged rows in MPS Files can now be parsed if they are specified as 'E'
- postsolving FixInfinityCol works also in primal case
- store data for FixInfinityCol correct if bounds are both infinity
- PaPILO shows some behavior on different OS
Miscellaneous
- Providing a way to build PaPILO without TBB (warning parallel design can not be used anymore)
- Providing an interface to gurobi
- Providing an interface to ortools (GLOP/PDLP)
- Install all files (also externals) to the include/papilo folder
- Presolving is aborted if presolvers are activated that do not support dual postsolve