Repository navigation
MIP: wrong Optimal at default settings: HighsLpAggregator drops small values without relaxing the RHS #3478
Description
What version of HiGHS and what language are you using?
Version: latest (5f241ea); also 1.15.1 (04024d7)
Language: C++ (the highs executable)
Which solver are you using (e.g. LP, MIP, QP)
MIP
What operating system (Linux, Windows, ...) and version?
Windows 11, clang 23, release build
What did you do?
highs tolls.lp with default options (model attached). It has 27 rows and 77 columns (6 binary), and HiGHS prints no scaling warning (bounds <= 1e6, costs >= 1e-4).
What did you expect to see
Optimal -6254.734457. The attached optimum.sol (x3 = 1) has that objective, and
highs --read_solution_file optimum.sol tolls.lp reports it feasible (max row violation 1e-10).
What did you see instead?
Optimal, primal = dual = -6016.354106 (1 node). The same with random_seed 0-4 and with threads = 1.
Anything else we should know about your project / environment
Cause, traced with a DEBUGSOL build of 5f241ea and optimum.sol as the debug solution: the first
failed assertion is checkRowAggregation (HighsTableauSeparator.cpp:227) at the root, where the
aggregated tableau row is off by 0.0033 at the solution. HighsLpAggregator::getCurrentAggregation dropped
31 column values with |a| <= small_matrix_value (3.6e-10 to 8e-10: flow coefficients of 8e-4 times the
tableau weights) without changing the right-hand side. These columns are flows of up to 1e6, so the dropped
terms sum to 0.0033 at the solution. The next failed assertion is checkCut after untransform in
HighsCutGeneration::generateCut (line 1170): the 3-term cut from such a row is violated by 0.43 at the
solution.
This is the third place I have found where a value at or below small_matrix_value is dropped without
relaxing the row: HighsTransformedLp::untransform() (#3434, fixed by #3223) and HPresolve::scaleMIP (my
comment on #3468).
Suggested change (the rule #3223 uses in HighsTransformedLp):
--- a/highs/mip/HighsLpAggregator.cpp
+++ b/highs/mip/HighsLpAggregator.cpp
@@ -9,6 +9,7 @@
#include "mip/HighsLpAggregator.h"
#include "mip/HighsLpRelaxation.h"
+#include "mip/HighsMipSolverData.h"
HighsLpAggregator::HighsLpAggregator(const HighsLpRelaxation& lprelaxation)
: lprelaxation(lprelaxation) {
@@ -30,17 +31,19 @@ void HighsLpAggregator::addRow(HighsInt row, double weight) {
void HighsLpAggregator::getCurrentAggregation(std::vector<HighsInt>& inds,
std::vector<double>& vals,
bool negate) {
- const double droptol =
- lprelaxation.getMipSolver().options_mip_->small_matrix_value;
+ const HighsMipSolverData& mipdata = *lprelaxation.getMipSolver().mipdata_;
+ const HighsDomain& domain = mipdata.getDomain();
const HighsInt numCol = lprelaxation.numCols();
- vectorsum.cleanup([droptol, numCol](HighsInt col, double val) {
+ vectorsum.cleanup([&](HighsInt col, double val) {
// only drop values for columns and not for slack variables of rows as the
// former are the only ones which might be subject to numerical error. The
// values for row slack variables are exact copies of the weights used
// (assuming that separators only add each row once). Also all the
// separators will only allow rows that do have meaningful coefficient
// contributions with the used weight
- return col < numCol && std::fabs(val) <= droptol;
+ return col < numCol &&
+ HighsDomain::termIsZero(val, domain.col_lower_[col],
+ domain.col_upper_[col], mipdata.epsilon);
});
inds = vectorsum.getNonzeros();With it, 5f241ea returns -6254.734457 on the file; ctest with ALL_TESTS=ON gives the same result as
unpatched (166 of 168; the two *-pdlp-no-presolve tests fail either way).
I used an AI assistant (Claude) to help trace this, and I checked the results.
Activity
DoumarCharles commentedon Oct 28, 2026
In case the coefficient range of
tolls.lp(8e-4 to 1e6) is a concern, here is a second reproducer with asmall range: matrix [0.6, 2000], costs [1e-4, 600], bounds and right-hand sides <= 1e6, no big-M (the 1e6 is
built by three rows with coefficients 1 and 100).
highs bills.lp(50 rows, 79 columns, 8 binary; default options, no warnings) reportsOptimal-1958.50219;the attached
optimum.solhas -2085.42369217 and--read_solution_filereports it feasible. Wrong atrandom_seed0-4 (seed 2 gives -2050.89035883) and withthreads = 1, on 5f241ea and 1.15.1.Same cause: after presolve the tableau row of a binary has 0.6 / (800 * 1e6) = 7.5e-10 on each flow column;
getCurrentAggregationdrops 14 of them (flows of up to 1e6), the row is off by 0.00237 at the solution(
checkRowAggregation,HighsTableauSeparator.cpp:227), and the 3-term cut from it is violated by 0.0012 atthe solution (
checkCut,HighsCutGeneration.cpp:1170). With the suggested change, 5f241ea returns-2085.42369217.
aggregator-issue-v3.zip
Opt-Mucca commentedon Oct 29, 2026
@DoumarCharles I'll start looking into this now. I expect your fix to be correct as it was always the intention to slowly extend the usage of
termIsZero.Edit: Fix looks good! I'll test this overnight before opening a PR though, so don't expect movement until tomorrow afternoon. Interested in how many instances this affects.
DoumarCharles commentedon Oct 29, 2026
@Opt-Mucca Thanks for looking into this, and good to know that extending the use of
termIsZerowas already planned.From what I can see, small coefficients removed during cut postprocessing are generally accounted for by relaxing the RHS using the column bounds.
termIsZeroprovides another safeguard by dropping coefficients only when their possible contribution over the column bounds is negligible. The cleanup inHighsLpAggregator::getCurrentAggregationdoes neither.I also briefly reviewed
HighsTransformedLp::transformanduntransform, along withHighsCutGeneration::postprocessCut, but haven't confirmed another failure in those paths.Please let me know if any additional information or test cases would be helpful.
fwesselm commentedon Nov 4, 2026
Fixed by #3507.