Branch-and-bound sub-MIPs pass near-zero (~1e-18) coefficients to Papilo
维护者通常 1 天内回复
还没有人认领这个 Issue。
评估
- 难度
- 4/5
- 预计耗时
- 1-2 天
- 新手友好度
- 53/100
- Issue 类型
- 缺陷
- 描述清晰度
- 基本清楚
- 活跃度
- 活跃
调研方向
Start with branch_and_bound_t::solve_submip and trace convert_lp_to_user_problem and third_party_presolve_t::apply_to_subproblem to see how coefficients reach Papilo. The issue points to cut row construction or sub-MIP conversion as possible places to drop tiny coefficients; compare against the stated tolerance context and verify that the pk1.mps sub-MIP no longer carries the near-zero values.
由索引模型根据 Issue 内容生成。
描述
Branch-and-bound passes sub-MIPs to Papilo with coefficients around 1e-18.
Where
branch_and_bound_t::solve_submip builds the sub-MIP from worker->leaf_problem (structural rows, slacks and cuts) with convert_lp_to_user_problem, then calls third_party_presolve_t::apply_to_subproblem. Nothing drops tiny coefficients on the way.
Example
A sub-MIP of pk1.mps, captured at 3d71290b while running mip_solve.initial_solution_survives_papilo_crush. It has 54 rows; pk1 has 45, so the extra rows are most likely cuts. The last row, R53, has two coefficients on free columns:
- C32: -1.734723475976807e-18 (exactly -2^-59)
- C33: -1.894851796836205e-18
The other coefficients in that row are at least 0.015. A coefficient of exactly -2^-59 looks like leftover from floating-point cancellation rather than a real coefficient. Papilo's numerics.epsilon is 1e-9 and its presolve.minabscoeff is 1e-10.
Impact
Papilo's sparsify cancels C33 with a scale of -1.9e-18. That leaves every other coefficient in the row unchanged and triggers the Papilo assertion in scipopt/papilo#103, which #2267 patches. With the patch it no longer aborts, but the sub-MIP still carries values that are numerically zero.
Expected
Drop coefficients below a small tolerance when the cut rows are built, or when the sub-MIP is converted.
- 主要语言
- Cuda
- 星标
- 1.1k
- 派生
- 255
- 平均合并
- 1 天 22 小时
- 30 天内合并 PR
- 102
环境准备
- 没有 Dockerfile 或 Docker Compose 文件
- 有 Pull Request 模板
- 阅读贡献指南
从这里开始
- 先读完整个 Issue，再读项目的贡献指南。
- 在 Issue 下留言说明你要接手 —— 这能避免两个人做同样的事。
- Fork 仓库，在一个分支上完成修改。
- 提交 Pull Request，并在描述里引用这个 Issue 编号。
NVIDIA/cuopt 的其他 Issue
-
[BUG] Constraint validation reports CSR offset count as the number of rows可能已有人在做 @0z5a 于 2 天前认领。 未关闭
难度 2/5 1-3 小时 新手友好度 78/100
维护者通常 1 天内回复
-
ci: pr-test-summary job shows red when the GitHub API returns persistent 5xx errors可能已有人在做 @0z5a 于 2 天前认领。 未关闭
难度 2/5 1-3 小时 新手友好度 72/100
维护者通常 1 天内回复
-
难度 1/5 1 小时以内 新手友好度 82/100
维护者通常 1 天内回复
-
[BUG] Dataset downloader reports success and replaces data after a failed download可能已有人在做 @0z5a 于 2 天前认领。 未关闭
难度 3/5 1-2 天 新手友好度 75/100
维护者通常 1 天内回复
-
难度 4/5 3-5 天 新手友好度 48/100
维护者通常 1 天内回复