Summary
In HighsPathSeparator::separateLpSolution(), a path-mixing cut is assembled from several base
rows, each transformed by its own HighsTransformedLp::transform() call, and mapped back by a
single untransform() at the end. The chosen substitution per column lives in the shared
boundTypes array, and untransform() reads whatever is in there when it runs.
A base row that is transformed and then discarded leaves its changes behind. If it flipped the
complementation chosen for a binary, untransform() resubstitutes a different variable than the
coefficients were computed against, and the resulting cut is not globally valid. Such a cut can
remove the optimum, after which the search closes and reports the incumbent as Optimal at a zero
gap.
Reproducing
3171-1.mps.txt (85 rows, 99 columns, 49 binaries, 300 nonzeros) is solved incorrectly under default
options, with no option pinning:
$ highs 3171-1.mps
Status Optimal
Primal bound 42332.2356068
Dual bound 42332.2356068
Gap 0% (tolerance: 0.01%)
Nodes 0
The optimum is 42215.5250005, so this is suboptimal by 116.71 — a relative error of 0.276%,
about 28x the default relative gap tolerance. Not a tolerance artefact, and decided at the root
in zero nodes.
The optimum is confirmed by HiGHS itself, without trusting a patched build: fixing all 49 integer
columns to the values of the better point and solving the remaining LP returns
Optimal 42215.5250005. So a feasible integral point 116.71 better than the reported optimum
demonstrably exists. --presolve off returns 42215.5250005 too, so the contradiction is visible
within one unmodified binary.
The failure is seed-dependent — it occurs on seeds 0 and 5 of the first 8 — so a regression test
needs random_seed pinned to 0 (which is the default).
Cause
The bound type for a binary depends on the sign of its coefficient in the row being transformed
(highs/mip/HighsTransformedLp.cpp):
} else if (vals[i] > 0) {
boundTypes[col] = BoundType::kSimpleLb; // y = x - lb
} else {
boundTypes[col] = BoundType::kSimpleUb; // y = ub - x (complemented)
}so a column occurring with opposite signs in two rows gets two different substitutions.
In highs/mip/HighsPathSeparator.cpp the loop transforms base row k before testing whether
its right-hand side keeps the required monotonicity, and drops the row only afterwards:
if (!transLp.transform(aggregatedPath[k].second, tmpUpper, tmpSolval,
aggregatedPath[k].first, rhs[k], integralPositive)) {
pathLen = k; // row dropped - but boundTypes already mutated
break;
}
...
} else if (rhs[k] >= rhs[k - 1] - mip.mipdata_->feastol) {
pathLen = k; // row dropped - but boundTypes already mutated
break;
}The mutation survives the row being discarded, and nothing ties the substitutions in force at
untransform() to the ones used to build the coefficients.
The existing consistency assertions in that loop cannot catch it: solval is lbDist[col] for
both kSimpleLb and kVariableLb and ubDist[col] for both kSimpleUb and kVariableUb, while
upper is ub - lb in every case — so neither value changes when the substitution flips.
Also on a production model
On a 10404 x 18899 MIP this fires once and costs 2978.48 on the objective. Instrumenting the
separator to compare the substitution used when each coefficient was computed against the one in
force at untransform() gives exactly one mismatched column:
col 14096 substitution at untransform() = kSimpleLb
y used when the coefficient was computed = 1 (complemented, y = 1 - x)
y implied by the substitution used = 0 (y = x - 0)
coefficient -1 -> error exactly +1
That cut evaluates to violation 0 in the transformed space at the known optimum and 1 after
untransform() — the entire error is the one flipped complementation. The invalid cut (53
nonzeros, all ±1, rhs -1) then seeds further invalid cuts and a bogus clique via
extractCliquesFromCut().
The model still returns the wrong answer with the fixes for #3170 and #3173 both applied, so the
three defects are independent:
| build |
objective, presolve=on |
|
latest |
-12370583.0955 |
wrong |
latest + #3170 + #3173 |
-12370583.0955 |
wrong |
latest + #3170 + #3173 + this |
-12373561.5756 |
correct |
presolve=off returns the correct -12373561.5756 throughout. I can attach the model, or the
instrumentation patch that makes the mismatch observable in a single solve.
The same pattern affects the variable bounds too
bestVub / bestVlb are shared mutable state as well, and transform() may tighten them in
place via cleanupVub() / cleanupVlb(), so a coefficient computed from an earlier base row can
be untransformed against a tightened bound. I have no reproducer for that case, but it is the same
failure mode: the cut is untransformed by reading state back out of a shared, still-mutating
HighsTransformedLp, rather than carrying the transformation it was built with.
Related
#3170 — an independent unsoundness in the same subsystem, where a redundant variable bound is
substituted as if it were tight. Different root cause, same end effect, same call path; neither fix
subsumes the other.
#3173 — a third defect found on the same class of model, but in presolve rather than cut
generation, so it is decided before branch-and-bound runs and is unaffected by either fix here.
Summary
In
HighsPathSeparator::separateLpSolution(), a path-mixing cut is assembled from several baserows, each transformed by its own
HighsTransformedLp::transform()call, and mapped back by asingle
untransform()at the end. The chosen substitution per column lives in the sharedboundTypesarray, anduntransform()reads whatever is in there when it runs.A base row that is transformed and then discarded leaves its changes behind. If it flipped the
complementation chosen for a binary,
untransform()resubstitutes a different variable than thecoefficients were computed against, and the resulting cut is not globally valid. Such a cut can
remove the optimum, after which the search closes and reports the incumbent as
Optimalat a zerogap.
Reproducing
3171-1.mps.txt (85 rows, 99 columns, 49 binaries, 300 nonzeros) is solved incorrectly under default
options, with no option pinning:
The optimum is
42215.5250005, so this is suboptimal by 116.71 — a relative error of 0.276%,about 28x the default relative gap tolerance. Not a tolerance artefact, and decided at the root
in zero nodes.
The optimum is confirmed by HiGHS itself, without trusting a patched build: fixing all 49 integer
columns to the values of the better point and solving the remaining LP returns
Optimal 42215.5250005. So a feasible integral point 116.71 better than the reported optimumdemonstrably exists.
--presolve offreturns42215.5250005too, so the contradiction is visiblewithin one unmodified binary.
The failure is seed-dependent — it occurs on seeds 0 and 5 of the first 8 — so a regression test
needs
random_seedpinned to 0 (which is the default).Cause
The bound type for a binary depends on the sign of its coefficient in the row being transformed
(
highs/mip/HighsTransformedLp.cpp):so a column occurring with opposite signs in two rows gets two different substitutions.
In
highs/mip/HighsPathSeparator.cppthe loop transforms base rowkbefore testing whetherits right-hand side keeps the required monotonicity, and drops the row only afterwards:
The mutation survives the row being discarded, and nothing ties the substitutions in force at
untransform()to the ones used to build the coefficients.The existing consistency assertions in that loop cannot catch it:
solvalislbDist[col]forboth
kSimpleLbandkVariableLbandubDist[col]for bothkSimpleUbandkVariableUb, whileupperisub - lbin every case — so neither value changes when the substitution flips.Also on a production model
On a 10404 x 18899 MIP this fires once and costs 2978.48 on the objective. Instrumenting the
separator to compare the substitution used when each coefficient was computed against the one in
force at
untransform()gives exactly one mismatched column:That cut evaluates to violation
0in the transformed space at the known optimum and1afteruntransform()— the entire error is the one flipped complementation. The invalid cut (53nonzeros, all
±1, rhs-1) then seeds further invalid cuts and a bogus clique viaextractCliquesFromCut().The model still returns the wrong answer with the fixes for #3170 and #3173 both applied, so the
three defects are independent:
presolve=onlatest-12370583.0955latest+ #3170 + #3173-12370583.0955latest+ #3170 + #3173 + this-12373561.5756presolve=offreturns the correct-12373561.5756throughout. I can attach the model, or theinstrumentation patch that makes the mismatch observable in a single solve.
The same pattern affects the variable bounds too
bestVub/bestVlbare shared mutable state as well, andtransform()may tighten them inplace via
cleanupVub()/cleanupVlb(), so a coefficient computed from an earlier base row canbe untransformed against a tightened bound. I have no reproducer for that case, but it is the same
failure mode: the cut is untransformed by reading state back out of a shared, still-mutating
HighsTransformedLp, rather than carrying the transformation it was built with.Related
#3170 — an independent unsoundness in the same subsystem, where a redundant variable bound is
substituted as if it were tight. Different root cause, same end effect, same call path; neither fix
subsumes the other.
#3173 — a third defect found on the same class of model, but in presolve rather than cut
generation, so it is decided before branch-and-bound runs and is unaffected by either fix here.