NVIDIA / NVIDIA/cuopt

[BUG] Incorrect comparison inside BFRT in dual simplex

Open
#1,440 0 comments 0 reactions 1 assignee View on GitHub

Nobody has claimed this yet.

bug
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

Open the contributing guide

First steps

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. Open a pull request that references the issue number.

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.