Branch-and-bound sub-MIPs pass near-zero (~1e-18) coefficients to Papilo
Los mantenedores suelen responder en 1 día
Nadie ha tomado este issue todavía.
Evaluación
- Dificultad
- 4/5
- Tiempo estimado
- 1-2 días
- Aptitud para principiantes
- 53/100
- Tipo de issue
- Error
- Claridad
- Bastante claro
- Estado de actividad
- Activo
Línea de trabajo
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.
Escrito por el modelo de indexación a partir del texto del issue.
Descripción
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.
- Lenguaje dominante
- Cuda
- Estrellas
- 1.1k
- Forks
- 255
- Merge medio
- 1 d 22 h
- PR fusionados (30 d)
- 102
Preparar el entorno
- Sin Dockerfile ni archivo de Docker Compose
- Tiene una plantilla de pull request
- Leer la guía de contribución
Primeros pasos
- Lee el issue completo y luego la guía de contribución del proyecto.
- Comenta en el issue que vas a ocuparte — evita que dos personas hagan lo mismo.
- Haz un fork del repositorio y trabaja en una rama.
- Abre un pull request que haga referencia al número del issue.
Más de NVIDIA/cuopt
-
[BUG] Constraint validation reports CSR offset count as the number of rowsPosiblemente ocupada @0z5a la tomó hace 2 días. Abierto
Dificultad 2/5 1-3 horas Aptitud para principiantes 78/100
Los mantenedores suelen responder en 1 día
-
ci: pr-test-summary job shows red when the GitHub API returns persistent 5xx errorsPosiblemente ocupada @0z5a la tomó hace 2 días. Abierto
Dificultad 2/5 1-3 horas Aptitud para principiantes 72/100
Los mantenedores suelen responder en 1 día
-
Dificultad 1/5 Menos de una hora Aptitud para principiantes 82/100
Los mantenedores suelen responder en 1 día
-
[BUG] Dataset downloader reports success and replaces data after a failed downloadPosiblemente ocupada @0z5a la tomó hace 2 días. Abierto
Dificultad 3/5 1-2 días Aptitud para principiantes 75/100
Los mantenedores suelen responder en 1 día
-
Dificultad 4/5 3-5 días Aptitud para principiantes 48/100
Los mantenedores suelen responder en 1 día