Recent Releases of highs.native
highs.native - v1.11.0
Build changes
Replace command line parsing library with Cpp11 #2211
CMake updates #2286, the root of the HiGHS source files is now highs/, rather than src/
Add missing include to zstr needed for gcc v15 and clang v19 #2313
Updates for intel llvm compiler on linux #2257
Build directory for Windows MSVC now Release/bin replacing bin/Release #2376
Code changes
Fixed incorrect assertion in HighsMipSolver::solutionFeasible() (fixing #2204)
As part of #2251 cuPDLP-C will start from the incumbent solution in HiGHS. For a model that has been changed, the user must supply a starting solution via a call to Highs::setSolution
getColIntegrality now returns HighsVarType::kContinuous when model_.lp_.integrality_ is empty (fixing #2261)
Now ensuring that when solving a scaled LP with useful but unvalidated basis, it does not lose its scaling after validation, since the scaling factors will be applied to the solution (fixing #2267)
By setting non-empty values of options read_solution_file, read_basis_file, write_model_file (with extension .lp or .mps), write_solution_file, solution_file, write_basis_file, these files will be read or written when calling Highs::run(). Hence options previously only available via the command line interface can be use (for example) by modelling languages that only call Highs::run() (fixing #2269).
Bug #2273 fixed
Added the feasibility jump heuristic as per #1423. This is on by default, but using the option mip_heuristic_run_feasibility_jump=false switches it off.
ZI rounding and shifting MIP primal heuristics have been added (see #2287). They are off by default, but can be activated by setting the options mip_heuristic_run_zi_round and mip_heuristic_run_shifting to be true. Options mip_heuristic_run_rins, mip_heuristic_run_rens and mip_heuristic_run_root_reduced_cost to run the RINS, RENS and rootReducedCost heuristics have been added. These are true by default, but setting them to be false can accelerate the MIP solver on easy problems.
Added Highs_changeRowsBoundsByRange to C API, fixing #2296
Corrected docstrings for Highs_getReducedRow, motivated by #2312
LP file reader no longer fails when there is no objective section. Fix is #2316, but this exposes code quality issue #2318
Added a max scale factor (+1024) when scaling up coefficients in preprocessBaseInequality and postprocessCut. Fix is #2337
Corrected the bounds used in when strengthening coefficients in HPresolve::rowPresolve, fixing #1517
Fixed numerical error in highs/mip/HighsCliqueTable.cpp, closing #2320
Fixed bug in highs/mip/HighsFeasibilityJump.cpp, closing #2331
Tightened CMIR cuts, leading to small performance gain, closing #2333
Scaling the tolerance in forcing row reduction to avoid use of rows with small coefficients and bounds, closing #2290
Fixed bug when calculating a coefficient in one of the cuts in separateImpliedBounds in highs/mip/HighsImplications.cpp
Added CSECTION to the exceptions for keywords that are followed by text, and thus cannot be used as names of columns, RHS, ranges, bounds etc.
Introduced the following KKT error measures to HighsInfo: num_relative_primal_infeasibilities; max_relative_primal_infeasibility; num_relative_dual_infeasibilities; max_relative_dual_infeasibility; num_primal_residual_errors; max_primal_residual_error; num_dual_residual_errors; max_dual_residual_error; num_relative_primal_residual_errors; max_relative_primal_residual_error; num_relative_dual_residual_errors; max_relative_dual_residual_error; num_complementarity_violations; max_complementarity_violation; primal_dual_objective_error. The relative values are used to assess whether a solution deemed to be optimal by the first order LP solver cuPDLP-C or interior point solver IPX (without crossover) is truly acceptable. They also enable users to determine whether a solution corresponding to HighsModelStatus::kUnknown is acceptable to them as optimal. Also introduced options complementarity_tolerance used to assess whether the (relative) primal-dual objective error is acceptable, and kkt_tolerance which, if set to a value other than kDefaultKktTolerance = 1e-7 is used as the tolerance for all the KKT error measures. The HiGHS documentation has been updated to reflect the new options and HighsInfo data, and logging messages indicate when KKT error measures are not satisfied, despite the solver considering the LP solution to be optimal.
Added a max scale factor (+1024) when scaling up coefficients in preprocessBaseInequality and postprocessCut. Fix is #2337.
Renamed HighsOptions::pdlp_d_gap_tol to HighsOptions::pdlp_optimality_tolerance for consistency with IPM
Renamed HighsOptions::complementarity_tolerance to HighsOptions::optimality_tolerance for consistency with IPM and PDLP
- C++
Published by galabovaa 12 months ago
highs.native - v1.10.0
Build changes
Added code coverage report
Replaced command line parsing library with CLI11. Removed C++17 reference with cxxopts, which is no longer in HiGHS
Code changes
Any LP offset is communicated to the IPM solver, and used in logging and primal/dual objective calculations.
If there is a valid basis when Highs::run() is called, presolve isn't skipped unless the solver option is "simplex" or "choose" (when simplex will always be chosen if there is an advanced basis).
Added basis solve methods to highspy
Added methods to get primal/dual ray and dual unboundedness direction to highspy
When a presolved LP has model status kUnknown, rather than returning this to the user, it performs postsolve and then uses the basis to solve the original LP
Fixed bug in presolve when pointers stored in HighsMatrixSlice get invalidated when the coefficient matrix is reallocated (e.g. when non-zeros are added in HPresolve::addToMatrix)
Primal and dual residual tolerances - applied following IPM or PDLP solution - now documented as options
Highs::getCols (Highs::getRows) now runs in linear time if the internal constraint matrix is stored column-wise (row-wise). Added ensureColwise/Rowwise to the Highs class, the C API and highspy so that users can set the internal constraint matrix storage orientation
When columns and rows are deleted from the incumbent LP after a basic solution has been found, HiGHS no longer invalidates the basis. Now it maintains the basic and nonbasic status of the remaining variables and constraints. When the model is re-solved, this information is used to construct a starting basis.
Fixed bugs in presolve
When running from the command line, changes to default option values are reported
Added callback to allow users to supply integer feasible solutions to the MIP solver during execution
Bug fix for primal heuristics in the MIP solver
Model status is set appropriately when a solver's claimed optimality doesn't satify the general HiGHS primal/dual feasibilily tolerances. Affects IPM without crossover and PDLP
Command line parsing now done with pure C++11 code
Added command line flags to read basis from and write basis to a file
Bug fixes in records of primal/dual rays
MPS read utility improved. Error logging is now less verbose; inability to handle USERCUTS section is properly logged
Implemented lifting for probing as described by Achterberg et al in Presolve Reductions in Mixed Integer Programming. INFORMS Journal on Computing 32(2):473-506 (2019). Not used by default, but option mipliftingfor_probing allows it to be used with two levels of modification
Propagated updates from cuPDLP-C
Added GPU support for cuPDLP-C
- C++
Published by galabovaa about 1 year ago
highs.native - v1.9.0
Build changes
Python: Source Distribution update, added to PyPI
Code changes
HiGHS now handles multiple linear objectives by either blending using weights, or performing lexicographic optimization: see https://ergo-code.github.io/HiGHS/stable/guide/further/#guide-multi-objective-optimization
Fixed minor bug in bound checking in presolve
Fixed bug in floor(HighsCDouble x) and ceil(HighsCDouble x) when argument is small
Added some sanity checks to Highs::writeLocalModel to prevent segfaults if called directly by a user
- C++
Published by galabovaa over 1 year ago
highs.native - v1.8.1
Build changes
Added wheels for Python 3.13
Updated command line options and moved them out of the library and into the executable
Code changes
When primal infeasiblity is detected in presolve, no dual ray is available so, previously, the has_dual_ray parameter of Highs::getDualRay returned false and that was it. Now, if a null pointer is not passed for dual_ray_value, Highs::getDualRay will compute a dual ray - at the cost of solving the feasiblility LP without presolve. The same is now true for Highs::getPrimalRay. Highs::getDualUnboundednessDirection has been introduced to determine the product between the constraint matrix and the dual ray, forcing the calculation of the latter if necessary. Once a dual ray is known for the incumbent model in HiGHS, subsequent calls to Highs::getDualRay and Highs::getDualUnboundednessDirection will be vastly cheaper
The method Highs::getDualObjectiveValue now exitsts to compute the dual objective value, returning HighsStatus::kError if it is not possible.
The method Highs::getStandardFormLp now exists to return the incumbent LP in standard form - overlooking any integrality or Hessian. To determine the sizes of the vectors of data, the method is called without specifying pointers to the data arrays.
Added documentation on the use of presolve when solving an incumbent model, and clarifying the use of the method Highs::presolve.
HiGHS will now read a MIPLIB solution file
Added time limit check to HPresolve::strengthenInequalities
Added getColIntegrality to highspy
Now computing the primal-dual integral, reporting it, and making it available as HighsInfo::primal_dual_integral
Trivial primal heuristics "all zero", "all lower bound", "all upper bound", and "lock point" added to the MIP solver
- C++
Published by galabovaa over 1 year ago
highs.native - v1.8.0
Code updates
We believe that the issue of HiGHS "hanging" when run on Windows with threads not equal to 1 has been fixed!
Added int64_t mip_total_lp_iterations to HighsCallbackDataOut and modified accessor function
Highs::writeSolution and Highs::writeBasis now being done via HighsIO logging, so can be redirected to logging callback.
Introduced const double kHighsUndefined as value of undefined values in a user solution. It's equal to kHighsInf
Added Highs::setSolution(const HighsInt num_entries, const HighsInt* index, const double* value); to allow a sparse primal solution to be defined. When a MIP is solved to do this, the value of (new) option mip_max_start_nodes is used for mip_max_nodes to avoid excessive cost
Added options write_presolved_model_to_file and write_presolved_model_file so that presolved model can be written via a command line option
Added Highs::feasibilityRelaxation to solve the problem of minimizing a (possibly weighted) sum of (allowable) infeasibilities in an LP/MIP.
Added Python utility examples/plot_highs_log.py (due to @Thell) to visualise progress of the MIP solver.
Added minimal documentation of solvers and how simplex variants can be run
Methods receiving matrix data where only small values are explicit zeros (so removed internally) are now silent and return HighsStatus::kOk (since internal matrix is exact)
Now multiplying by pre-computed reciprocals rather than performing divisions in loops in simplex solver: LP performance improvement ~2.5%
Primal and dual residuals after IPM and cuPDLP-C are checked, and corrections applied to row solution and column duals
Highs::passModelName added to allow name to be given to the incumbent model
Memory leaks in cuPDLP-C fixed
Bug fixed in MIP presolve
- C++
Published by galabovaa over 1 year ago
highs.native - v1.7.2
Build changes
The python wrapper highspy is now available for aarch64 on manylinux This allows highs to be run through Python on AWS arm64
Bug fix for fortran on macOS
Code changes
The accessor function HighsgetCallbackDataOutItem in the C API means
that `pdlpiteration_countcan be moved back to where it was inserted
into theHighsCallbackDataOut` struct in v1.7.0, which broke the C
API. This fixes #1812
Some duplicate code has been eliminated from the MIP solver, and modifications made to eliminate compiler warnings
Declaration of the (deprecated) method char* highsCompilationDate()
has been corrected
Fixed bug when describing integrality status during the human-readable solution write
- C++
Published by galabovaa almost 2 years ago
highs.native - v1.7.1
Version 1.7.1 of HiGHS contains several updates
Build changes
HiGHS on nixpkgs
HiGHS now has a flake.nix to build the binary, allowing nix users to try it out.
Python build update
On PyPI, highspy is now available as v1.7.1, bringing the Python and C++ versions of HiGHS into line.
Windows versions
Fixed version info of shared library Added version info to executable
Code changes
Inserting pdlp_iteration_count into the struct HighsCallbackDataOut (for v1.7.0) breaks the C API, so it has been moved to the end of the struct, and an accessor function Highs_getCallbackDataOutItem has been added.
References to the compilation date have been removed from the build and code of HiGHS, so that binaries for the same version compiled on different days are identical. Methods to print compilation dates are deprecated.
setBasis has been added to highspy.
writePresolvedModel has been added, allowing the presolved model to be exported as a file.
The saved MIP solution pool is now populated with the optimal solution when presolve reduces a MIP to empty.
There is now a logging message and error return when a user-supplied solution or basis is rejected due to the size of any vector being incompatible with the dimensions of the incumbent model.
Memory allocation errors in presolve are caught and Highs::run() returns HighsStatus::kError with model_status_ = HighsModelStatus::kMemoryLimit.
QP solver logging is now neater and quieter.
Any Hessian for the incumbent model is modified with zero entries when adding columns to the model, and rows/columns are removed when columns are deleted from the model.
The has been a minor bug fix in the MIP presolve
QP solver will now hot start given a basis and solution
- C++
Published by galabovaa almost 2 years ago
highs.native - v1.7.0
Version 1.7.0 of HiGHS contains several new developments.
HiGHS now offers the exciting new first order LP solver (cuPDLP-c). Ours is currently only a serial CPU implementation, so performance isn't spectacular, but we aim to offer the GPU implementation in due course. To run PDLP, choose the option solver=pdlp. Note that there is currently no time-out available for PDLP, and the termination criteria for cuPDLP-c may mean that the HiGHS optimality conditions are not satisfied. See README.md .
The HiGHS interior point solver now allows analytic centre calculations to be performed. This is done by setting the HiGHS option run_centring to be true. Other new options allow the centring calculations to be controlled.
When Highs::run() is called, ranges of the matrix, costs, bounds and RHS are reported, together with advice on setting the new HiGHS options usercostscale and usedboundscale if there are extreme values.
After solving an LP, the method Highs::getIllConditioning tries (in an approach similar to that used by Gurobi) to identify constraints or basic variables that contribute most to ill-conditioning of the basis matrix.
Logging from the interior point solver is now consistent with logging from the simplex and MIP solvers.
The Python interface has been updated, with several overlooked methods having been added
Considerable modifications and fixes have been added to the build system, in particular for Python. highspy is no longer built with meson, rather a combination of setuptools and cmake.
Bugs in the QP and MIP solvers have been fixed
Thanks are due to due to @fwesselm @feldmeier and @Coloquinte
- C++
Published by galabovaa about 2 years ago
highs.native - v1.6.0
Added logging, improving solution and interrupt callbacks to C++ and C for a single user-defined callback method. Specifically
- New logging callback consistent with new callback method. Old logging callback is deprecated
- Callback when MIP logging takes place
- Callback when MIP solver finds an improving integer feasible solution
- Interrupt callbacks for simplex, interior point and MIP solvers
Added the use of the objective_target option to terminate the MIP solver when an integer feasible solution at least as good as this value has been found.
Bug fixes
- C++
Published by galabovaa over 2 years ago
highs.native - v1.4.2
Removed print statement from HFactor.cpp
- C++
Published by jajhall over 3 years ago
highs.native - v1.4.1
Includes a fix to ensure that dependent equations timeout also works on a model of the time remaining, otherwise bdry2 never times out.
Otherwise, one very minor fix to avoid a compiler warning, a print statement deleted, and a typo in a comment.
- C++
Published by jajhall over 3 years ago
highs.native - v1.4.0
Modifications have been made to improve the reliability of the IPM solver when cross-over is not always run - carried out for benchmarking purposes. This has required the run_crossover option that was previously Boolean to become a string with possible values "on", "off" and "choose". The latter results in crossover being run if the result of IPM without crossover is imprecise.
HiGHS will now allow a solution to be read from a file when running HiGHS from the command line, and handle the case where a user has supplied a partial (discrete) solution to a MIP. If the supplied solution is not feasible, HiGHS will fix the discrete variables and attempt to find a feasible assignment of the continuous variables by solving an LP.
If the incumbent model has discrete variables, then the MIP is solved regardless of the setting of the solve option. Previously if solve were "simplex" or "ipm" then the relaxation would be solved. To force the relaxation to be solved, set the (new) solve_relaxation option (default "false") to be true.
Various bug fixes, notably time limit introduced into redundant equations rule for presolve.
- C++
Published by jajhall over 3 years ago
highs.native - v1.3.0
Contains various bug fixes, notably in the .lp file reader/writer, plus a fix for #917 and enhancements to the MIP solver.
- C++
Published by jajhall over 3 years ago
highs.native - v1.2.2
HiGHS can read compressed files by using zstr MPS file reader now parses further sections Bug fixes in presolve
- C++
Published by jajhall about 4 years ago
highs.native - v1.2.1
Some bug fixes from v1.2.0, notably when handling QP maximization, but also mip_gap and objective sign logging correct for MIP maximization. highs_c_api.h and Highs.h have had parameter naming cleaned up, with constants corresponding to C++ enums and documentation added to highs_c_api.h.
- C++
Published by jajhall over 4 years ago
highs.native - v1.2.0
Lots of changes. Main performance improvement is in MIP solver.
- C++
Published by jajhall over 4 years ago
highs.native - v1.1.1
First tagged release of HiGHS. Created 27/09/21, and used for the Mittelmann benchmark results from then until date
- C++
Published by jajhall over 4 years ago