CHANGELOG

@page RN24 Release notes for PAPILO 2.4

@section RN241 PaPILO 2.4.1

Fixed bugs
----------

Build system
------------

@section RN240 PaPILO 2.4.0

Interface changes
-----------------

### Changed parameters

- presolve.abortfac = 0.00080000000000000004: abort factor of weighted number of reductions for exhaustive presolving
- presolve.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 checks
- presolve.abortfacfast = 0.00080000000000000004: abort factor of weighted number of reductions for fast presolving
- presolve.abortfacmedium = 0.00080000000000000004: abort factor of weighted number of reductions for medium presolving
- presolve.lpabortfacfast = 0.01: abort factor of weighted number of reductions for fast LP presolving
- presolve.lpabortfacmedium = 0.01: abort factor of weighted number of reductions for medium LP presolving

Build system
------------

- updated FindTBB
- 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

@page RN23 Release notes for PAPILO 2.3

@section RN231 PaPILO 2.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)

@section RN230 PaPILO 2.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

@page RN22 Release notes for PAPILO 2.2

@section RN221 PaPILO 2.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


@section RN220 PaPILO 2.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)


@page RN21 Release notes for PAPILO 2.1

@section RN214 PaPILO 2.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


@section RN213 PaPILO 2.1.3
***************************

Interface changes
-----------------

### 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

### Data structures


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


@section RN212 PaPILO 2.1.2
***************************

Fixed bugs
----------

- SimpleSubstitution: fixing bug in the infeasibility detection of the extended euclidean


@section RN211 PaPILO 2.1.1
***************************

Fixed bugs
----------

- SimpleSubstitution: avoid abort because of calling extended_euclidean with negative coefficients


@section RN210 PaPILO 2.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


@page RN20 Release notes for PAPILO 2.0

@section RN200 PaPILO 2.0.0
***************************

Features
--------

- supporting dual postsolving for presolvers: DomCol, Dualfix, SingletonCol, ParallelCol, ParallelRow, Propagation, FixContinuous, SingletonCol, SingletonStuffing
    - dual postsolve is activated if original problem has no integer variable
    - note to turn off componentsmaxint = -1 and presolve.detectlindep = 0
    - if calculate_basis_for_dual is activated (default), tightening the bounds (f.e. in Propagation and Dualfix) are avoided due to computional overhead to postsolve the basis information
- applying the reductions of the presolver found immediately to the problem so that the next presolver can work with the reduced problem if PaPILO is used with one thread.
    This feature can be turned off by parameter (presolve.apply_results_immediately_if_run_sequentially).
- DualFix: setting the variable to infinity, if objective is zero and the bound unbounded
- ParallelRowDetection: adding new ReductionType RHS_LESS_RESTRICTIVE/LHS_LESS_RESTRICTIVE to reduce the number of conflicts to other presolvers
- SimpleSubstitution: adding detection for infeasibility
- ConstraintPropagation, DualFix, SimplifyInequality, CoefficientStrengthening, SimpleSubstitution, SimpleProbing, ImpliedInteger: parallelising presolver internally
- ParallelRowDetection, ParallelCol, DominatedCol: reordering the results to avoid internal conflicts
- Updated cmake system for dependency on TBB 2021. Older TBB versions might still work though.
- supporting backend solver HiGHS 1.0.0 (git hash: ca0c21da)

Performance improvements
------------------------

- reordering solvers to avoid conflicts and hence speed up the process

Interface changes
-----------------
### Deleted and changed API methods

- extracted postsolve storage from Postsolve to a new class PostsolveStorage to store the steps required for Postsolving
- Function undo in Postsolve requires now reducedSolution, originalSolution and PostsolveStorage
- moved class Postsolve.hpp to src/core/postsolve
- extracted class PostsolveType.hpp to src/core/postsolve
- extracted class ReductionType.hpp to src/core/postsolve
- extracted class PostsolveStatus.hpp to src/core/postsolve

### New API functions

- new ReductionType in Postsolve: kFixedInfCol
- new ReductionType in Postsolve for dual-postsolve: kSubstitutedColWithDual
- new ReductionType in Postsolve for dual-postsolve: kVarBoundChange
- new ReductionType in Postsolve for dual-postsolve: kRedundantRow
- new ReductionType in Postsolve for dual-postsolve: kRowBoundChange
- new ReductionType in Postsolve for dual-postsolve: kReasonForRowBoundChangeForcedByRow
- new ReductionType in Postsolve for dual-postsolve: kRowBoundChangeForcedByRow
- new ReductionType in Postsolve for dual-postsolve: kSaveRow
- new ReductionType in Postsolve for dual-postsolve: kReducedBoundsCost
- new ReductionType in Postsolve for dual-postsolve: kColumnDualValue
- new ReductionType in Postsolve for dual-postsolve: kRowDualValue
- new ReductionType in Postsolve for dual-postsolve: kCoefficientChange

### Changed parameters


### New parameters with default values

- calculate_basis_for_dual = 1: Should the basis be calculated if dual postsolve is possible (1: yes 0: no)
- bound_tightening_offset = 0.0001: What is the offset for variable bound tightening (only if dual-postsolving is enabled)?
- validation_after_every_postsolving_step = 0: Should the primal/dual solution be validated during after every postsolving step? (1:yes 0: no)
- presolve.apply_results_immediately_if_run_sequentially = 1: If only one thread is used, should the results be applied immediately after the presolver returned the reductions? (1: yes 0: no)
- coefftightening.parallel = 1: Should the presolver be run in parallel internally (1: yes 0: no)
- doubletoneq.parallel = 0: Should the presolver be run in parallel internally (1: yes 0: no)
- dualfix.parallel = 0: Should the presolver be run in parallel internally (1: yes 0: no)
- implint.parallel = 0: Should the presolver be run in parallel internally (1: yes 0: no)
- propagation.parallel = 1: Should the presolver be run in parallel internally (1: yes 0: no)
- simpleprobing.parallel = 0: Should the presolver be run in parallel internally (1: yes 0: no)
- simplifyineq.parallel = 1: Should the presolver be run in parallel internally (1: yes 0: no)

### Data structures


Unit tests
----------


Testing
-------

- while building with CMake PaPILO checks if a file solution.test exists in the build directory and
    scans every line of the file with the format PATH_TO_INSTANCE\,PATH_TO_SOL.
    Running make test checks for all instances in the specified file if the solution fits the reduced problem and
    further the original solution can be postsolved from the reduced solution

Build system
------------


Fixed bugs
----------

- DomCol: adding additional locks in DomCol to prevent applying false reductions
- SingletonCol: reordering bound changes in presolvers to avoid infeasibility when applying the changes to the data structure
- SingletonCol: using Numerics functions (including epsilon) for Less/greater-or-equal to avoid slightly false objective values
- SingletonStuffing: reordering bound changes in presolvers to avoid infeasibility when applying the changes to the data structure
- SimpleProbing: handling the case (coefficients <= 0) correctly
- recalculating the activities if the activity is huge to avoid numerical problems
- fixing bug in stated solutions of solver as infeasible due to numerical issues
- parsing instance files in rational mode with empty rows successfully
- SingletonRows: handling values close to zero does not lead to infeasibility anymore
- setting the time-limit via the parameter file is not clashing with the command time-limit any more
- ParallelRowDetection: using epsilon tolerance to avoid that the lhs is greater than the rhs
- DualInfer: consider case if reduced costs indicate an unbounded variable

Miscellaneous
-------------

- adding a new command line option -b to check if the solution still fits the presolved problem
- supporting parsing gzipped solution files
- printing information about reductions if message verbosity level 'detailed' is selected
- printing the objective value if the problem can be solved during presolving
- printing the header containing the version of the configured backend solver
- boost minimum is 1.72 on mac, 1.65 otherwise
- supporting boost version 1.78

Known bugs
----------

- parsing MPS Files where in the Bound section the rows doesn't start with an identifier (for example: "R") fail
- solution value for the instance etamarco differs slightly (-755.7152333749133350792583667773 vs -755.715233354415 )

@page RN10 Release notes for PAPILO 1.0

Features
--------
- providing presolve and (primal) postsolve methods for MIP and LP
- providing a transaction-based design allowing the presolvers to run in parallel within a round and also allowing internal parallelisation
- providing an header-only library to be integrate MIP/LP solvers
- providing an interface to wrap MIP/LP solvers to solve instances immediately after presolving
- CoefficientStrengthening: (fast) tightens the coefficients in a constraint in order to strengthen the LP relaxation
- ConstraintPropagation (fast) tightens the variable bounds
- DomCol: (exhaustive) detects and handles dominated variables
- DualFix (medium) counts up- and downlocks on variables and proceeds this information
- DualInfer: (exhaustive) exploits complementary slackness and derives bound changes or fixes on variables
- FixContinuous: (medium) tries to fix continuous variables whose bounds are very close
- ParallelColDetection: (medium) detects parallel columns and merges them into a new variable
- ParallelRowDetection: (medium) detects parallel rows in the matrix and merges them into one
- Probing: (exhaustive) tries to find implications by probing on binary variables
- SimpleProbing: (medium) detects implications for binary variables on equations with special requirements
- SimpleSubstitution: (medium) searches for equations with exactly two variables and substitutes one of these variables
- SimplifyInequalities: (medium) deletes variables in a constraint that will never contribute to the outcome of the constraint
- SingletonCols: (fast) removes variables appearing in only one constraint
- SingletonStuffing: (medium) removes variables appearing in only one constraint if SingletonCols fails to remove them
- Sparsify: (exhaustive) adds up constraint to reduce the amount of nonzeros
- Substitution: (exhaustive) substitutes equations while maintaining a sparse data structure


### Parameters with default values

- coefftightening.enabled = 1: is presolver coefftightening enabled  (1: yes 0: no)
- colsingleton.enabled = 1: is presolver colsingleton enabled  (1: yes 0: no)
- domcol.enabled = 1: is presolver domcol enabled  (1: yes 0: no)
- doubletoneq.enabled = 1: is presolver doubletoneq enabled  (1: yes 0: no)
- dualfix.enabled = 1: is presolver dualfix enabled  (1: yes 0: no)
- dualinfer.enabled = 1: is presolver dualinfer enabled  (1: yes 0: no)
- fixcontinuous.enabled = 1: is presolver fixcontinuous enabled  (1: yes 0: no)
- implint.enabled = 1: is presolver implint enabled  (1: yes 0: no)
- message.verbosity = 3: verbosity to be used. (0: quiet 1: errors 2: warnings 3: normal 4: detailed)
- numerics.epsilon = 1.0000000000000001e-09: epsilon tolerance to consider two values equal
- numerics.feastol = 9.9999999999999995e-07: the feasibility tolerance
- numerics.hugeval = 100000000: absolute bound value that is considered too huge for activitity based calculations
- parallelcols.enabled = 1: is presolver parallelcols enabled  (1: yes 0: no)
- parallelrows.enabled = 1: is presolver parallelrows enabled  (1: yes 0: no)
- presolve.abortfac = 0.00080000000000000004: abort factor of weighted number of reductions for presolving
- presolve.boundrelax = 0: relax bounds of implied free variables after presolving  (1: yes 0: no)
- presolve.componentsmaxint = 0: maximum number of integral variables for trying to solve disconnected components of the problem in presolving (-1: disabled)
- presolve.compressfac = 0.84999999999999998: compress the problem if fewer than compressfac times the number of rows or columns are active
- presolve.detectlindep = 1: detect and remove linearly dependent equations and free columns (0: off 1: for LPs 2: always)
- presolve.dualreds = 2: 0: disable dual reductions (0: diable dual reducions 1: allow dual reductions that never cut off optimal solutions, 2: allow all dual reductions)
- presolve.lpabortfac = 0.01: abort factor of weighted number of reductions for presolving LPs
- presolve.minabscoeff = 1e-10: minimum absolute coefficient value allowed in matrix, before it is set to zero
- presolve.randomseed = 0: random seed value
- presolve.removeslackvars = 1: remove slack variables in equations  (1: yes 0: no)
- presolve.threads = 0: maximal number of threads to use (0: automatic)
- presolve.tlim = 1.7976931348623157e+308: time limit for presolve
- presolve.weakenlpvarbounds = 0: weaken bounds obtained by constraint propagation by this factor of the feasibility tolerance if the problem is an LP
- probing.enabled = 1: is presolver probing enabled  (1: yes 0: no)
- probing.maxinitialbadgesize = 1000: maximum number of probing candidates probed in the first badge of candidates
- probing.minbadgesize = 10: minimum number of probing candidates probed in a single badge of candidates
- probing.mincontdomred = 0.29999999999999999: minimum fraction of domain that needs to be reduced for continuous variables to accept a bound change in probing  [Numerical: [0,1]]
- propagation.enabled = 1: is presolver propagation enabled  (1: yes 0: no)
- simpleprobing.enabled = 1: is presolver simpleprobing enabled  (1: yes 0: no)
- simplifyineq.enabled = 1: is presolver simplifyineq enabled  (1: yes 0: no)
- sparsify.enabled = 1: is presolver sparsify enabled  (1: yes 0: no)
- sparsify.maxscale = 1000: maximum absolute scale to use for cancelling nonzeros  [Numerical: [1,1.7976931348623157e+308]]
- stuffing.enabled = 1: is presolver stuffing enabled  (1: yes 0: no)
- substitution.binarieswithints = 1: should substitution of binary variables with general integers be allowed  (1: yes 0: no)
- substitution.enabled = 1: is presolver substitution enabled  (1: yes 0: no)
- substitution.markowitz_tolerance = 0.01: markowitz tolerance value for allowing a substitution  [Numerical: [0,1]]
- substitution.maxfillin = 10: maximum estimated fillin for variable substitutions  [Integer: [0,2147483647]]
- substitution.maxshiftperrow = 10: maximum amount of nonzeros being moved to make space for fillin from substitutions within a row  [Integer: [0,2147483647]]