Solving Binary Integer Programing Problems With Balas' Additive Algorithm Using Graphics Processing Units
Bibliographic record
Abstract
This thesis seeks to determine if Balas' additive algorithm for solving Binary Integer Programming (BIP) problems benefits from parallel processing. It establishes serial implementations of a subproblem form and bookkeeping form of Balas' algorithm that introduce new branching rules, memory compaction schemes, fathoming rules and a record keeping method. Parallel implementations of the subproblem and bookkeeping algorithms are developed that use Graphics Processing Units (GPUs) as the parallel platform. The parallel work proceeds in three stages. The first stage involves the parallelization of subproblems with batches of nodes from a branch-and-bound tree being solved simultaneously on a GPU. The second stage involves the parallel exploration of many subtrees from a single branch-and-bound tree using a bookkeeping scheme and a work stealing technique. The third stage involves deploying the subproblem and bookkeeping approaches in a multi-GPU environment to study how the techniques scale with additional hardware resources. The serial Balas' work revealed that ordering BIP variables by their coefficient values delivers benefits in the form of accelerated branching, memory compaction and efficient record keeping. The parallel subproblem form of Balas' was the best performing parallel algorithm and delivered speedups of up to 1670x through the application of the serial innovations and GPU techniques such as memory coalescing and streaming. Despite these performance gains the subproblem form is limited by memory issues on the CPU that prevent the algorithm from solving very large problems. The parallel bookkeeping form of Balas' demonstrated speedups up to 217x thanks to a work stealing technique that balances work load across parallel processors. However, the bookkeeping algorithm suffers from code divergence on the GPU that degrades its parallel performance. In the multi-GPU environment, the performance of the subproblem algorithm scales with additional resources while the bookkeeping form’s performance improves only marginally. Despite its memory issues, the parallel subproblem form of Balas’ delivers orders-of-magnitude improvements in execution times compared to its serial analogue and is the dominant technique in this thesis.
Fetched live from OpenAlex and de-inverted. Abstracts are not stored in this database: the inverted indexes are 8.6 GB of the frame’s 9.3 GB of text, and the host has 13 GB free.
How this classification was reachedexpand
Full frame machine prediction
Teacher imitationNot calibrated prevalence, not ground truth. Human validation pending. The Gemma side is a direct model label for every work in the frame, read from the title-only record. The Codex side is a classifier learned from the 10,348 direct Codex labels and calibrated to design-weighted sample rates; fields without enough sample support carry no Codex call. Candidate is the union of the two sides; consensus is their intersection. These outputs are machine_predicted_unvalidated and are not human labels.
Distilled classifier scores by category (both heads)
| Category | Codex | Gemma |
|---|---|---|
| Metaresearch | 0.001 | 0.002 |
| Meta-epidemiology (narrow) | 0.001 | 0.000 |
| Meta-epidemiology (broad) | 0.001 | 0.001 |
| Bibliometrics | 0.001 | 0.001 |
| Science and technology studies | 0.001 | 0.001 |
| Scholarly communication | 0.002 | 0.001 |
| Open science | 0.001 | 0.001 |
| Research integrity | 0.001 | 0.002 |
| Insufficient payload (model declined to judge) | 0.003 | 0.001 |
Machine scores (provisional)
The two teacher heads of the student model, read on this work. A score orders the frame for review; it never asserts a category, and the validation status ships verbatim with every row.
Baseline scores from an immature model (maturity gate not passed, 7 training rounds). Scores rank; they never assert a category.
score_only:v0-immature-baseline · verbatim from the scoring run: score_only means the number may rank works, and no category label ships from itClassification
machine, unvalidatedMachine predicted; a candidate call from one source (direct Gemma or distilled Codex), not a consensus.
How this classification was reached, model by model and score by score, is at the end of the page under "How this classification was reached".