[BUG] Incorrect comparison inside BFRT in dual simplex
Nobody has claimed this yet.
- Dominant language
- Cuda
- Stars
- 1k
- Forks
- 233
- Avg merge
- 4d 4h
- Merged PRs (30d)
- 95
Description
In the BFRT single_pass, line 83:
candidate = indicies[k]; // candidate = nonbasic position (0..n-m-1)
// ...
const i_t j = nonbasic_list_[indicies[k]]; // j = variable index
if (std::abs(delta_z_[j]) > std::abs(delta_z_[candidate])) {
Note delta_z_ is a vector of size n indexed by variable index. But candidate is a nonbasic position (the index into nonbasic_list_, ranging from 0 to n-m-1). So delta_z_[candidate] reads delta_z at a nonbasic position index rather than the corresponding variable index.
The correct comparison should be:
if (std::abs(delta_z_[j]) > std::abs(delta_z_[nonbasic_list_[candidate]])) {
The impact: in the Harris tie-breaking case (ratios within zero_tol), the CPU compares the new candidate's |delta_z| against an arbitrary value in the delta_z array (whatever happens to be at index candidate, which is a small integer 0..n-m-1). This usually doesn't matter because:
1. Harris tie-breaking is rare (most iterations have a clear minimum)
2. When it triggers, the "wrong" comparison often still selects a reasonable pivot
3. The solver is robust to slightly suboptimal pivot choices
Contributor guide
First steps
- Read the whole issue, then the project's contributing guide.
- Comment on the issue to say you are picking it up — it saves two people doing the same work.
- Fork the repository and make your change on a branch.
- Open a pull request that references the issue number.
Assessment
This issue has not been assessed yet.