google / google/or-tools

GLOP LinearProgram's GetTransposeSparseMatrix fails if not cleaned up

Open
#5,276 1 comment 0 reactions 0 assignees View on GitHub
Solver: Linear Solver
Dominant language
C++
Stars
14.1k
Forks
2.5k
Avg merge
8h 39m
Merged PRs (30d)
72

Description

**What version of OR-Tools and what language are you using?**
Version: main
Language: C++

**Which solver are you using (e.g. CP-SAT, Routing Solver, GLOP, BOP, Gurobi)**
GLOP

**What operating system (Linux, Windows, ...) and version?**
Linux

**What did you do?**
Steps to reproduce the behavior:
1. Create a glop::LinearProgram instance.
2. Call `SetCoefficient` on an existing nonzero, which makes the LP dirty, i.e., IsCleanedUp returns false.
3. Now a call to `GetTransposeSparseMatrix` fails.

**What did you expect to see**
Success of the `GetTransposeSparseMatrix`.

**What did you see instead?**
Failed debug checks

**There are three solutions I see:**
1. Add DCHECK() calls within `GetTransposeSparseMatrix` and document that it must be called on a cleaned-up version.
2. Clean up the matrix before.
3. Adapt the transposition method to explicitly take care of duplicates / zeros. This may lead to unnecessary memory allocation, but not much additional effort I think.

Contributor guide

Open the contributing guide

Research direction

Start with glop::LinearProgram and the GetTransposeSparseMatrix entry point, then reproduce the failure by changing an existing nonzero with SetCoefficient before calling it. Inspect the cleanup invariant and determine which of the three behaviors in the issue is intended. Done means the documented or implemented behavior no longer triggers failed debug checks for this sequence.

Written by the indexing model from the issue text.

Assessment

Tech stack
cpp
Domain
backend
Issue type
Bug
Difficulty
3/5
Estimated time
1-2 days
Activity status
Quiet
Clarity
Mostly clear
Newbie friendliness
55/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.