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

Description Usage Arguments Details Author(s) References See Also Examples

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.

	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"))

`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.

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.

Mike Higgins, Hua Yang

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.