# BaB: Finding the exact p-value. In elec.strat: Functions for election audits using stratified random samples

## Description

`BaB` finds an exact p-value by solving a 0-1 knapsack problem. The 0-1 knapsack problem is solved by a branch and bound algorithm. For more details, see Higgins, Rivest, Stark.

## Usage

 ```1 2 3 4``` ``` BaB(Z, t = NULL, asTaint = FALSE, asNumber = FALSE, M = NULL, takeOutZeroMMB=TRUE, give.strategy = FALSE, bound.col = "e.max", calc.e_p=calc.pairwise.e_p, w_p = weight.function("no.weight")) ```

## Arguments

 `Z` A `strat.elec.data` object. `t` Value of the observed maximum, either as the MRO, as taint, or as the overstatement of the margin in votes. `asTaint` Set `asTaint = TRUE` if `t` is the maximum observed taint. `asNumber` Set `asNumber` if `t` is the maximum observed overstatement of the margin in votes. `M` A priori margin. If NULL, `M` defaults to 1. `takeOutZeroMMB` Setting `takeOutZeroMMB = TRUE` will consider batches with a `maximumMarginBound` of zero as having no chance of being sampled. `give.strategy` If `give.strategy = TRUE`, output will include the solution to the 0-1 knapsack problem. `bound.col, calc.e_p, w_p` Arguments used to compute `t` from audit data, instead of passing `t` directly. These arguments are ignored if `t` is not NULL. See `compute.stark.t` for details.

## Details

`BaB` pre-processes the data to make the branch and bound algorithm more efficient, and obtains all information from `Z` necessary to perform the branch and bound algorithm. `BaB` then calls `runBaB`, which calls the branch and bound function.

When `give.strategy = TRUE`, the output of the solution will be a vector `strategy` of size `length(nrow(Z\$strat))`. The solution can be obtained by, for each stratum `i`, putting `e.max` amount of difference in the `strategy[i]` batches corresponding to the largest values of `u`. For more details, see Higgins, Rivest, Stark.

## Author(s)

Mike Higgins, Hua Yang

## References

M. Higgins, R. L. Rivest, P. B. Stark. Sharper p-Values for Stratified Election Audits

See `LKPBound` for finding a p-value through a continuous relaxation. See `eqValBound` and `withReplaceBound` for finding a p-value through other relaxations. See `runBaB` for running the branch and bound algorithm given a value vector `u`, a cost vector `q`, a margin `M`, and a `CIDnum` vector. See `compute.stark.t` for computing `t` through audit data.
 ```1 2``` ``` data(MN_Senate_2006) BaB(MN_Senate_2006.strat, takeOutZeroMMB = FALSE, give.strategy = TRUE) ```