Blom, M., Stuckey, P. J., & Teague, V. (2019). RAIRE: Risk-limiting audits for IRV elections. https://arxiv.org/abs/1903.08804arXiv:1903.08804
@unpublished{Blom2019-dq,
title = {{{RAIRE}}: Risk-limiting audits for {IRV} elections},
author = {Blom, Michelle and Stuckey, Peter J and Teague, Vanessa},
url = {https://arxiv.org/abs/1903.08804arXiv:1903.08804},
year = {2019},
keywords = {Authored;VOTING}
}
Risk-limiting post election audits guarantee a high probability of correcting incorrect election results, independent of why the result was incorrect. Ballot-polling audits select ballots at random and interpret those ballots as evidence for and against the reported result, continuing this process until either they support the recorded result, or they fall back to a full manual recount. For elections with digitised scanning and counting of ballots, a comparison audit compares randomly selected digital ballots with their paper versions. Discrepancies are referred to as errors, and are used to build evidence against or in support of the recorded result. Risk-limiting audits for first-past-the-post elections are well understood, and used in some US elections. We define a number of approaches to ballot-polling and comparison risk-limiting audits for Instant Runoff Voting (IRV) elections. We show that for almost all real elections we found, we can perform a risk-limiting audit by looking at only a small fraction of the total ballots (assuming no errors were made in the tallying and distribution of votes).
Refereed conference proceedings
Everest, F., Blom, M., Stark, P. B., Stuckey, P. J., Teague, V., & Vukcevic, D. (2022). Ballot-Polling Audits of Instant-Runoff Voting Elections
with a Dirichlet-Tree Model. 1st International Workshop on Election Infrastructure
Security (EIS 2022).
@inproceedings{Everest2022-gu,
title = {{Ballot-Polling} Audits of {Instant-Runoff} Voting Elections
with a {Dirichlet-Tree} Model},
author = {Everest, Floyd and Blom, Michelle and Stark, Philip B and Stuckey, Peter J and Teague, Vanessa and Vukcevic, Damjan},
booktitle = {1st International Workshop on Election Infrastructure
Security (EIS 2022)},
year = {2022}
}
Instant-runoff voting (IRV) is used in several countries
around the world. It requires voters to rank candidates in
order of preference, and uses a counting algorithm that is
more complex than systems such as first-past-the-post or
scoring rules. An even more complex system, the single
transferable vote (STV), is used when multiple candidates
need to be elected. The complexity of these systems has made
it difficult to audit the election outcomes. There is
currently no known risk-limiting audit (RLA) method for STV,
other than a full manual count of the ballots. A new
approach to auditing these systems was recently proposed,
based on a Dirichlet-tree model. We present a detailed
analysis of this approach for ballot-polling Bayesian audits
of IRV elections. We compared several choices for the prior
distribution, including some approaches using a Bayesian
bootstrap (equivalent to an improper prior). Our findings
include that the bootstrap-based approaches can be adapted
to perform similarly to a full Bayesian model in practice,
and that an overly informative prior can give
counter-intuitive results. Via carefully chosen examples, we
show why creating an RLA with this model is challenging, but
we also suggest ways to overcome this. As well as providing
a practical and computationally feasible implementation of a
Bayesian IRV audit, our work is important in laying the
foundation for an RLA for STV elections.
Everest, F., Blom, M., Stark, P. B., Stuckey, P. J., Teague, V., & Vukcevic, D. (2022). Auditing Ranked Voting Elections with Dirichlet-Tree
Models: First Steps. Proceedings of the 7th International Joint Conference on Electronic Voting (EVOTE-ID).
@inproceedings{Everest2022-uo,
title = {Auditing Ranked Voting Elections with {Dirichlet-Tree}
Models: First Steps},
author = {Everest, Floyd and Blom, Michelle and Stark, Philip B and Stuckey, Peter J and Teague, Vanessa and Vukcevic, Damjan},
booktitle = {Proceedings of the 7th International Joint Conference on Electronic Voting ({EVOTE-ID})},
year = {2022}
}
Ranked voting systems, such as instant-runoff voting (IRV)
and single transferable vote (STV), are used in many places
around the world. They are more complex than plurality and
scoring rules, presenting a challenge for auditing their
outcomes: there is no known risk-limiting audit (RLA) method
for STV other than a full hand count. We present a new
approach to auditing ranked systems that uses a statistical
model, a Dirichlet-tree, that can cope with high-dimensional
parameters in a computationally efficient manner. We
demonstrate this approach with a ballot-polling Bayesian
audit for IRV elections. Although the technique is not known
to be risk-limiting, we suggest some strategies that might
allow it to be calibrated to limit risk.
Blom, M., Stuckey, P. J., Teague, V., & Vukcevic, D. (2022). A First Approach to Risk-Limiting Audits for Single
Transferable Vote Elections. Proceedings of the 7th Workshop on Advances in Secure
Electronic Voting (VOTING).
@inproceedings{Blom2022-jf,
title = {A First Approach to {Risk-Limiting} Audits for Single
Transferable Vote Elections},
author = {Blom, Michelle and Stuckey, Peter J and Teague, Vanessa and Vukcevic, Damjan},
booktitle = {Proceedings of the 7th Workshop on Advances in Secure
Electronic Voting (VOTING)},
year = {2022}
}
Risk-limiting audits (RLAs) are an increasingly important
method for checking that the reported outcome of an election
is, in fact, correct. Indeed, their use is increasingly
being legislated. While effective methods for RLAs have been
developed for many forms of election – for example:
first-past-the-post, instant-runoff voting, and D’Hondt
elections – auditing methods for single transferable vote
(STV) elections have yet to be developed. STV elections are
notoriously hard to reason about since there is a complex
interaction of votes that change their value throughout the
process. In this paper we present the first approach to
risk-limiting audits for STV elections, restricted to the
case of 2-seat STV elections.
Blom, M., Budurushi, J., Rivest, R. L., Stark, P. B., Stuckey, P. J., Teague, V., & Vukcevic, D. (2021). Assertion-Based Approaches to Auditing Complex Elections, with
Application to Party-List Proportional Elections. Proceedings of the 6th International Joint Conference on Electronic Voting (EVOTE-ID), 12900, 47–62.
@inproceedings{Blom2021-vf,
title = {{Assertion-Based} Approaches to Auditing Complex Elections, with
Application to {Party-List} Proportional Elections},
booktitle = {Proceedings of the 6th International Joint Conference on Electronic Voting ({EVOTE-ID})},
author = {Blom, Michelle and Budurushi, Jurlind and Rivest, Ronald L and Stark, Philip B and Stuckey, Peter J and Teague, Vanessa and Vukcevic, Damjan},
publisher = {Springer},
volume = {12900},
pages = {47--62},
series = {Lecture Notes in Computer Science},
month = sep,
year = {2021},
address = {Cham},
keywords = {Authored;VOTING}
}
Risk-limiting audits (RLAs), an ingredient in evidence-based elections, are increasingly common. They are a rigorous statistical means of ensuring that electoral results are correct, usually without having to perform an expensive full recount – at the cost of some controlled probability of error. A recently developed approach for conducting RLAs, SHANGRLA, provides a flexible framework that can encompass a wide variety of social choice functions and audit strategies. Its flexibility comes from reducing sufficient conditions for outcomes to be correct to canonical ‘assertions’ that have a simple mathematical form.
Assertions have been developed for auditing various social choice functions including plurality, multi-winner plurality, super-majority, Hamiltonian methods, and instant runoff voting. However, there is no systematic approach to building assertions. Here, we show that assertions with linear dependence on transformations of the votes can easily be transformed to canonical form for SHANGRLA. We illustrate the approach by constructing assertions for party-list elections such as Hamiltonian free list elections and elections using the D’Hondt method, expanding the set of social choice functions to which SHANGRLA applies directly.
Blom, M. L., Stark, P. B., Stuckey, P. J., Teague, V. J., & Vukcevic, D. (2021). Auditing Hamiltonian Elections. Proceedings of the 6th Workshop on Advances in Secure Electronic
Voting (VOTING), 235–250.
@inproceedings{Blom2021-jf,
title = {Auditing Hamiltonian Elections},
booktitle = {Proceedings of the 6th Workshop on Advances in Secure Electronic
Voting ({VOTING})},
author = {Blom, Michelle L and Stark, Philip B and Stuckey, Peter J and Teague, Vanessa J and Vukcevic, Damjan},
pages = {235--250},
year = {2021},
keywords = {Authored;VOTING}
}
Presidential primaries are a critical part of the United States Presidential electoral process, since they are used to select the candidates in the Presidential election. While methods differ by state and party, many primaries involve proportional delegate allocation using the so-called Hamilton method. In this paper we show how to conduct risk-limiting audits for delegate allocation elections using variants of the Hamilton method where the viability of candidates is determined either by a plurality vote or using instant runoff voting. Experiments on real-world elections show that we can audit primary elections to high confidence (small risk limits) usually at low cost.
Blom, M. L., Conway, A., Stuckey, P. J., & Teague, V. J. (2020). Did that lost ballot box cost me a seat? Computing manipulations
of STV elections. Proceedings of the Thirty-Second Annual Conference On
Innovative Applications of Artificial Intelligence (IAAI), 34, 13235–13240.
@inproceedings{Blom2020-nv,
title = {Did that lost ballot box cost me a seat? Computing manipulations
of {STV} elections},
booktitle = {Proceedings of the {Thirty-Second} Annual Conference on
Innovative Applications of Artificial Intelligence ({IAAI})},
author = {Blom, Michelle L and Conway, Andrew and Stuckey, Peter J and Teague, Vanessa J},
volume = {34},
pages = {13235--13240},
year = {2020},
keywords = {Authored;VOTING}
}
Mistakes made by humans, or machines, commonly arise when managing ballots cast in an election. In the 2013 Australian Federal Election, for example, 1,370 West Australian Senate ballots were lost, eventually leading to a costly re-run of the election. Other mistakes include ballots that are misrecorded by electronic voting systems, voters that cast invalid ballots, or vote multiple times at different polling locations. We present a method for assessing whether such problems could have made a difference to the outcome of a Single Transferable Vote (STV) election – a complex system of preferential voting for multi-seat elections. It is used widely in Australia, in Ireland, and in a range of local government elections in the United Kingdom and United States.
Blom, M. L., Conway, A., King, D., Sandrolini, L., Stark, P. B., Stuckey, P. J., & Teague, V. J. (2020). You can do RLAs for IRV. Proceedings of the 5th International Joint Conference On
Electronic Voting (EVOTE-ID) [Best Paper Award].
@inproceedings{Blom2020-ig,
title = {You can do {RLAs} for {IRV}},
booktitle = {Proceedings of the 5th International Joint Conference on
Electronic Voting ({EVOTE-ID}) [Best Paper Award]},
author = {Blom, Michelle L and Conway, Andrew and King, Dan and Sandrolini, Laurent and Stark, Philip B and Stuckey, Peter J and Teague, Vanessa J},
year = {2020},
keywords = {Authored;VOTING}
}
The City and County of San Francisco, CA, has used Instant Runoff Voting (IRV) for some elections since 2004. This report describes the first ever process pilot of Risk Limiting Audits for IRV, for the San Francisco District Attorney’s race in November, 2019. We found that the vote-by-mail outcome could be efficiently audited to well under the 0.05 risk limit given a sample of only 200 ballots. All the software we developed for the pilot is open source.
Blom, M. L., Conway, A., Stuckey, P. J., Teague, V. J., & Vukcevic, D. (2020). Random errors are not necessarily politically neutral. Proceedings of the 5th International Joint Conference On
Electronic Voting (EVOTE-ID), 19–35.
@inproceedings{Blom2020-ny,
title = {Random errors are not necessarily politically neutral},
booktitle = {Proceedings of the 5th International Joint Conference on
Electronic Voting ({EVOTE-ID})},
author = {Blom, Michelle L and Conway, Andrew and Stuckey, Peter J and Teague, Vanessa J and Vukcevic, Damjan},
pages = {19--35},
institution = {Springer},
year = {2020},
keywords = {Authored;VOTING}
}
Errors are inevitable in the implementation of any complex process. Here we examine the effect of random errors on Single Transferable Vote (STV) elections, a common approach to deciding multi-seat elections. It is usually expected that random errors should have nearly equal effects on all candidates, and thus be fair. We find to the contrary that random errors can introduce systematic bias into election results. This is because, even if the errors are random, votes for different candidates occur in different patterns that are affected differently by random errors. In the STV context, the most important effect of random errors is to invalidate the ballot. This removes far more votes for those candidates whose supporters tend to list a lot of preferences, because their ballots are much more likely to be invalidated by random error. Different validity rules for different voting styles mean that errors are much more likely to penalise some types of votes than others. For close elections this systematic bias can change the result of the election.
Blom, M. L., Conway, A., Stuckey, P. J., & Teague, V. J. (2020). Shifting the Balance-of-Power in STV Elections. Proceedings of the 5th International Joint Conference On
Electronic Voting (EVOTE-ID), 1–18.
@inproceedings{Blom2020-iv,
title = {Shifting the {Balance-of-Power} in {STV} Elections},
booktitle = {Proceedings of the 5th International Joint Conference on
Electronic Voting ({EVOTE-ID})},
author = {Blom, Michelle L and Conway, Andrew and Stuckey, Peter J and Teague, Vanessa J},
pages = {1--18},
institution = {Springer},
year = {2020},
keywords = {Authored;VOTING}
}
In the context of increasing automation of Australian electoral processes, and accusations of deliberate interference in elections in Europe and the USA, it is worthwhile understanding how little a change in the recorded ballots could change an election result. In this paper we construct manipulations of the ballots in order to change the overall balance of power in an Australian Federal Senate election – the upper house of Parliament. This gives, hopefully tight, over-estimations of the Margin of Victory (MOV) for the party or coalition winning the Senate. This is critical information for determining how well we can trust the reported results, and how much auditing should be applied to the election process to be certain that it reports the true result. The challenge arising in Australian Federal Senate elections is that they use a complicated Single Transferable Vote (STV) method for which it is intractable to compute the true MOV, hence we must rely on greedy methods to find small manipulations.
Blom, M. L., Stuckey, P. J., & Teague, V. J. (2019). Election Manipulation 100. Proceedings of the 4th Workshop on Advances in Secure Electronic
Voting (VOTING), 211–225.
@inproceedings{Blom2019-co,
title = {Election Manipulation 100},
booktitle = {Proceedings of the 4th Workshop on Advances in Secure Electronic
Voting ({VOTING})},
author = {Blom, Michelle L and Stuckey, Peter J and Teague, Vanessa J},
pages = {211--225},
year = {2019},
keywords = {Authored;VOTING}
}
The true election margin for an Instant Runoff Voting (IRV) election can be hard to compute, because a small modification early in the elimination sequence can alter the outcome and result in a candidate winning the last round by a large margin. It is often assumed that the true margin is the last-round margin, that is half the difference between the two candidates who remain when everyone else is eliminated, though it is well known that this need not be the case. Perceptions of confidence in the outcome, and even formal policies about recounts, often depend on the last-round margin. There is already some prior work on how to compute the true election margin efficiently for IRV, and hence how to find the minimal manipulation. In this work we show how to manipulate an election efficiently while also producing a large last-round margin. This would allow a succesful manipulation to evade detection against naive methods of assessing the confidence of the election result. This serves as further evidence for accurate computations of the exact margin, or for rigorous Risk Limiting Audits which would detect a close or wrong election result (respectively) regardless of the last-round margin.
Blom, M. L., Stuckey, P. J., & Teague, V. J. (2019). Election Manipulation with Partial Information. Proceedings of the 4th International Joint Conference On
Electronic Voting (EVOTE-ID), 32–49.
@inproceedings{Blom2019-bi,
title = {Election Manipulation with Partial Information},
booktitle = {Proceedings of the 4th International Joint Conference on
Electronic Voting ({EVOTE-ID})},
author = {Blom, Michelle L and Stuckey, Peter J and Teague, Vanessa J},
pages = {32--49},
institution = {Springer},
year = {2019},
keywords = {Authored;VOTING}
}
We consider the case of manipulating the results of Instant Runoff Voting (IRV) elections. Previous work in this area looked at posthoc manipulation with complete information, where the manipulator may alter ballots after reading the whole election profile. In this paper we examine the much more realistic, but challenging, problem of manipulating ballots during the election process, having observed only some ballots. The aim of the manipulator is to modify as few ballots as possible to ensure their candidate’s victory with high probability. We show that this it quite feasible in practice to generate efficient manipulations with a high probability of success. We also add some extra conditions on the manipulations so it is less likely they will be detected by naive methods.
Blom, M. L., Stuckey, P. J., & Teague, V. J. (2018). Ballot-polling risk limiting audits for IRV elections. Proceedings of the 3rd International Joint Conference On
Electronic Voting (EVOTE-ID), 17–34.
@inproceedings{Blom2018-yb,
title = {Ballot-polling risk limiting audits for {IRV} elections},
booktitle = {Proceedings of the 3rd International Joint Conference on
Electronic Voting ({EVOTE-ID})},
author = {Blom, Michelle L and Stuckey, Peter J and Teague, Vanessa J},
pages = {17--34},
institution = {Springer},
year = {2018},
keywords = {Authored;VOTING}
}
Risk-limiting post election audits guarantee a high probability of correcting incorrect election results, independent of why the result was incorrect. Ballot-polling audits select ballots at random and interpret those ballots as evidence for and against the actual recorded result, continuing this process until either they support the recorded result, or they fall back to a full manual recount. Ballot-polling for first-past-the-post elections is well understood, and used in some US elections. We define a number of approaches to ballot-polling risk-limiting audits for Instant Runoff Voting (IRV) elections. We show that for almost all real elections we found, we can perform a risk-limiting audit by looking at only a small fraction of the total ballots (assuming no errors).
Blom, M. L., Stuckey, P. J., & Teague, V. J. (2018). Computing the margin of victory in preferential parliamentary
elections. Proceedings of the 3rd International Joint Conference On
Electronic Voting (EVOTE-ID) [Best Paper Award], 1–16.
@inproceedings{Blom2018-mk,
title = {Computing the margin of victory in preferential parliamentary
elections},
booktitle = {Proceedings of the 3rd International Joint Conference on
Electronic Voting ({EVOTE-ID}) [Best Paper Award]},
author = {Blom, Michelle L and Stuckey, Peter J and Teague, Vanessa J},
pages = {1--16},
institution = {Springer},
year = {2018},
keywords = {Authored;VOTING}
}
We show how to use automated computation of election margins to assess the number of votes that would need to change in order to alter a parliamentary outcome for single-member preferential electorates. In the context of increasing automation of Australian electoral processes, and accusations of deliberate interference in elections in Europe and the USA, this work forms the basis of a rigorous statistical audit of the parliamentary election outcome. Our example is the New South Wales Legislative Council election of 2015, but the same process could be used for any similar parliament for which data was available, such as the Australian House of Representatives given the proposed automatic scanning of ballots.
Conway, A., Blom, M. L., Naish, L., & Teague, V. J. (2017). An analysis of New South Wales electronic vote counting. Proceedings of the Australasian Computer Science Week
Multiconference (ACSW), 1–5.
@inproceedings{Conway2017-hw,
title = {An analysis of New South Wales electronic vote counting},
booktitle = {Proceedings of the Australasian Computer Science Week
Multiconference ({ACSW})},
author = {Conway, Andrew and Blom, Michelle L and Naish, Lee and Teague, Vanessa J},
pages = {1--5},
year = {2017},
keywords = {Authored;VOTING}
}
We re-examine the 2012 local government elections in New South Wales, Australia. The count was conducted electronically using a randomised form of the Single Transferable Vote (STV). It was already well known that randomness does make a difference to outcomes in some seats. We describe how the process could be amended to include a demonstration that the randomness was chosen fairly.
Second, and more significantly, we found an error in the official counting
software, which caused a mistake in the count in the council of Griffith, where
candidate Rina Mercuri narrowly missed out on a seat. We believe the software
error incorrectly decreased Mercuri’s winning probability to about
10%—according to our count she should have won with 91% probability.
The NSW Electoral Commission (NSWEC) corrected their code when we pointed out the error, and made their own announcement.
We have since investigated the 2016 local government election (held after correcting the error above) and found two new errors. We notified the NSWEC about these errors a few days after they posted the results.
Blom, M. L., Teague, V. J., Stuckey, P. J., & Tidhar, R. (2016). Efficient Computation of Exact IRV Margins. ECAI 2016, 480–488.
@inproceedings{Blom2016-we,
title = {Efficient Computation of Exact {IRV} Margins},
booktitle = {{ECAI} 2016},
author = {Blom, Michelle L and Teague, Vanessa J and Stuckey, Peter J and Tidhar, Ron},
publisher = {IOS Press},
pages = {480--488},
year = {2016},
keywords = {Authored;VOTING}
}
The margin of victory is easy to compute for many election schemes but difficult for Instant Runoff Voting (IRV). This is important because arguments about the correctness of an election outcome usually rely on the size of the electoral margin. For example, risk-limiting audits require a knowledge of the margin of victory in order to determine how much auditing is necessary. This paper presents a practical branch-and-bound algorithm for exact IRV margin computation that substantially improves on the current best-known approach. Although exponential in the worst case, our algorithm runs efficiently in practice on all the real examples we could find. We can efficiently discover exact margins on election instances that cannot be solved by the current state-of-the-art.
Blom, M. L., & Pearce, A. R. (2010). Relaxing Regression for a Heuristic GOLOG. Proceedings of the 2010 Conference on STAIRS 2010: Proceedings
of the Fifth Starting AI Researchers’ Symposium, 37–49.
@inproceedings{Blom2010-zj,
title = {Relaxing Regression for a Heuristic {GOLOG}},
booktitle = {Proceedings of the 2010 Conference on {STAIRS} 2010: Proceedings
of the Fifth Starting {AI} Researchers' Symposium},
author = {Blom, Michelle L and Pearce, Adrian R},
publisher = {IOS Press},
pages = {37--49},
year = {2010},
address = {NLD},
keywords = {Authored}
}
GOLOG is an agent programming language designed to represent
complex actions and procedures in the situation calculus. In
this paper we apply relaxation-based heuristics –often used in
classical planning –to find (near) optimal executions of a
GOLOG program. In doing so we present and utilise a theory of
relaxed regression for the approximate interpretation of a GOLOG
program. This relaxed interpreter is used to heuristically
evaluate the available choices in the search for a program
execution. We compare the performance of our heuristic
interpreter (in terms of the quality of executions found) with a
traditional depth-first search interpreter and one guided by a
greedy heuristic without a look-ahead on three domains:
spacecraft control, mine operations planning, and task
scheduling.
Blom, M. L., & Pearce, A. R. (2009). An argumentation-based interpreter for Golog programs. Proceedings of the Twenty-First International Joint Conference
on Artificial Intelligence (IJCAI).
@inproceedings{Blom2009-by,
title = {An argumentation-based interpreter for Golog programs},
booktitle = {Proceedings of the {Twenty-First} International Joint Conference
on Artificial Intelligence ({IJCAI})},
author = {Blom, Michelle L and Pearce, Adrian R},
year = {2009},
keywords = {Authored}
}
This paper presents an argumentation-based interpreter for Golog programs. Traditional Golog interpreters are not designed to find the most preferred executions of a program from the perspective of an agent. Existing techniques developed to discover these executions are limited in terms of how the preferences of an agent can be expressed, and the variety of preference types that can be used to guide search for a solution. The presented work combines the use of argumentation to compare executions relative to a set of general comparison principles, and the theory behind best first search to reduce the cost of the search process. To the best of our knowledge this is the first work to integrate argumentation and the interpretation of Golog programs, and to use ar- gumentation as a tool for best first search.
Blom, M. (2008). Optimising the Interpretation of Golog Programs with
Argumentation. EUMAS, 597–611.
@inproceedings{Blom_undated-uq,
title = {Optimising the Interpretation of Golog Programs with
Argumentation},
booktitle = {{EUMAS}},
author = {Blom, Michelle},
pages = {597--611},
keywords = {Authored},
conference = {EUMAS},
location = {Bath, UK},
year = {2008}
}
This paper presents some preliminary work toward the development of an argumentative interpreter for Golog programs. Traditional Golog interpreters are not designed to find the most preferred executions of a program from the perspective of an agent. Existing techniques that optimise the interpretation of Golog programs suffer from either a lack of flexibility in how preference may be expressed or require the consideration of all program executions. The presented work combines the use of argumentation to compare executions relative to a set of general comparison criteria, and the theory behind informed search techniques to reduce the cost of the search process. The use of this argumentative informed search in the interpretation of ConGolog programs (with true concurrency), and its potential to find a program execution that is the most preferred by a collection of agents, is also discussed.
Refereed journal articles
Blom, M. L., Shekh, S., Gossink, D., Miller, T., & Pearce, A. R. (2020). Inventory routing for defense: Moving supplies in adversarial
and partially observable environments. The Journal of Defense Modeling and Simulation, 17(1), 55–81.
@article{Blom2020-xm,
title = {Inventory routing for defense: Moving supplies in adversarial
and partially observable environments},
author = {Blom, Michelle L and Shekh, Slava and Gossink, Don and Miller, Tim and Pearce, Adrian R},
journal = {The Journal of Defense Modeling and Simulation},
publisher = {SAGE Publications Sage UK: London, England},
volume = {17},
number = {1},
pages = {55--81},
year = {2020},
keywords = {Authored}
}
Future defense logistics will be heavily reliant on autonomous
vehicles for the transportation of supplies. We consider a dynamic logistics
problem in which: multiple supply item types are transported between suppliers
and consuming (sink) locations; and autonomous vehicles (road-, sea-, and
air-based) make decisions on where to collect and deliver supplies in a
decentralized manner. Sink nodes consume dynamically varying demands (whose
timing and size are not known a priori). Network arcs, and vehicles, experience
failures at times, and for durations, that are not known a priori. These dynamic
events are caused by an adversary, seeking to disrupt the network. We design
domain-dependent planning algorithms for these vehicles whose primary objective
is to minimize the likelihood of stockout events (where insufficient resource is
present at a sink to meet demand). Cost minimization is a secondary objective.
The performance of these algorithms, across varying scenarios, with and without
restrictions on communication between vehicles and network locations, is
evaluated using agent-based simulation. We show that stockpiling-based
strategies, where quantities of resource are amassed at strategic locations, are
most effective on large land-based networks with multiple supply item types,
with simpler “shuttling”-based approaches being sufficient otherwise.
Blom, M. L., Stuckey, P. J., & Teague, V. J. (2019). Toward computing the margin of victory in single transferable
vote elections. INFORMS J. Comput., 31(4), 636–653.
@article{Blom2019-tg,
title = {Toward computing the margin of victory in single transferable
vote elections},
author = {Blom, Michelle L and Stuckey, Peter J and Teague, Vanessa J},
journal = {INFORMS J. Comput.},
publisher = {INFORMS},
volume = {31},
number = {4},
pages = {636--653},
year = {2019},
keywords = {Authored;VOTING}
}
The single transferable vote (STV) is a system of preferential voting for multiseat elections. Each ballot cast by a voter is a (potentially partial) ranking over a set of candidates. No techniques currently exist for computing the margin of victory (MOV) in STV elections. The MOV is the smallest number of ballot manipulations (changes, additions, and deletions) required to bring about a change in the set of elected candidates. Knowing the MOV gives insight into how much time and money should be spent on auditing the election, and whether uncovered mistakes (such as ballot box losses) throw the election result into doubt—requiring a costly repeat election—or can be safely ignored. We present algorithms for computing lower and upper bounds on the MOV in STV elections. In small instances, these algorithms are able to compute exact margins.
Blom, M. L., Pearce, A. R., & Stuckey, P. J. (2019). Short-term planning for open pit mines: a review. Int. J. Min. Reclam. Environ., 33(5), 318–339.
@article{Blom2019-sw,
title = {Short-term planning for open pit mines: a review},
author = {Blom, Michelle L and Pearce, Adrian R and Stuckey, Peter J},
journal = {Int. J. Min. Reclam. Environ.},
publisher = {Taylor \& Francis},
volume = {33},
number = {5},
pages = {318--339},
year = {2019},
keywords = {Authored}
}
This review examines the current state-of-the-art in short-term planning for open-pit mines, with a granularity that spans days, weeks or months, and a horizon of less than one to two years. In the academic literature, the short-term planning problem for open-pit mines has not been as widely considered as that for the medium- and long-term horizons. We highlight the differences between short- and longer term planning in terms of both the level of detail to which a mine site is modelled, and the objectives that are optimised when making decisions. We summarise the range of techniques that have been developed for generating short-term plans, capturing both mathematical programming-based methods and heuristic approaches using local-search and decomposition. We identify key challenges and future directions in which to advance the state-of-the-art in short-term planning for open-pit mines.
Blom, M. L., Pearce, A. R., & Stuckey, P. J. (2018). Multi-objective short-term production scheduling for open-pit
mines: a hierarchical decomposition-based algorithm. Eng. Optim., 50(12), 2143–2160.
@article{Blom2018-hb,
title = {Multi-objective short-term production scheduling for open-pit
mines: a hierarchical decomposition-based algorithm},
author = {Blom, Michelle L and Pearce, Adrian R and Stuckey, Peter J},
journal = {Eng. Optim.},
publisher = {Taylor \& Francis},
volume = {50},
number = {12},
pages = {2143--2160},
year = {2018},
keywords = {Authored}
}
This article presents a novel algorithm for solving a short-term open-pit production-scheduling problem in which several objectives, of varying priority, characterize the quality of each solution. A popular approach employs receding horizon control, dividing the horizon into N period-aggregates of increasing size (number of periods or span). An N-period mixed integer program (MIP) is solved for each period in the original horizon to incrementally construct a production schedule one period at a time. This article presents a new algorithm that, in contrast, decomposes the horizon into N period-aggregates of equal size. Given a schedule for these N periods, obtained by solving an N-period MIP, the first of these aggregates is itself decomposed into an N-period scheduling problem with guidance provided on what regions of the mine should be extracted. The performance of this hierarchical decomposition-based approach is compared with that of receding horizon control on a suite of data sets generated from an operating mine producing millions of tons of ore annually. As the number of objectives being optimized increases, the hierarchical decomposition-based algorithm outperforms receding horizon control, in a majority of instances.
Blom, M. L., Pearce, A. R., & Stuckey, P. J. (2017). Short-term scheduling of an open-pit mine with multiple
objectives. Eng. Optim., 49(5), 777–795.
@article{Blom2017-ss,
title = {Short-term scheduling of an open-pit mine with multiple
objectives},
author = {Blom, Michelle L and Pearce, Adrian R and Stuckey, Peter J},
journal = {Eng. Optim.},
publisher = {Taylor \& Francis},
volume = {49},
number = {5},
pages = {777--795},
year = {2017},
keywords = {Authored}
}
This article presents a novel algorithm for the generation of multiple short-term production schedules for an open-pit mine, in which several objectives, of varying priority, characterize the quality of each solution. A short-term schedule selects regions of a mine site, known as ‘blocks’, to be extracted in each week of a planning horizon (typically spanning 13 weeks). Existing tools for constructing these schedules use greedy heuristics, with little optimization. To construct a single schedule in which infrastructure is sufficiently utilized, with production grades consistently close to a desired target, a planner must often run these heuristics many times, adjusting parameters after each iteration. A planner’s intuition and experience can evaluate the relative quality and mineability of different schedules in a way that is difficult to automate. Of interest to a short-term planner is the generation of multiple schedules, extracting available ore and waste in varying sequences, which can then be manually compared. This article presents a tool in which multiple, diverse, short-term schedules are constructed, meeting a range of common objectives without the need for iterative parameter adjustment.
Blom, M. L., Pearce, A. R., & Stuckey, P. J. (2016). A decomposition-based algorithm for the scheduling of open-pit
networks over multiple time periods. Manage. Sci., 62(10), 3059–3084.
@article{Blom2016-sj,
title = {A decomposition-based algorithm for the scheduling of open-pit
networks over multiple time periods},
author = {Blom, Michelle L and Pearce, Adrian R and Stuckey, Peter J},
journal = {Manage. Sci.},
publisher = {INFORMS},
volume = {62},
number = {10},
pages = {3059--3084},
year = {2016},
keywords = {Authored}
}
We consider the multiple-time-period, short-term production scheduling problem for a network of multiple open-pit mines and ports. Ore produced at each mine, in each period, is transported by rail to a set of ports and blended into products for shipping. Each port forms these blends to a specification, as stipulated in contracts with downstream customers. This problem belongs to a class of multiple producer/consumer scheduling problems in which producers are able to generate a range of products, a combination of which are required by consumers to meet specified demands. In practice, short-term schedules are formed independently at each mine, tasked with achieving a grade and quality target outlined in a medium-term plan. Because of uncertainty in the data available to a medium-term planner and the dynamics of the mining environment, such targets may not be feasible in the short term. In this paper, we present an algorithm in which the grade and quality targets assigned to each mine are iteratively adapted, ensuring the satisfaction of blending constraints at each port while generating schedules for each mine that maximise resource utilisation.
Blom, M., Burt, C. N., Pearce, A. R., & Stuckey, P. J. (2014). A decomposition-based heuristic for collaborative scheduling in
a network of open-pit mines. INFORMS J. Comput., 26(4), 658–676.
@article{Blom2014-rx,
title = {A decomposition-based heuristic for collaborative scheduling in
a network of open-pit mines},
author = {Blom, Michelle and Burt, Christina N and Pearce, Adrian R and Stuckey, Peter J},
journal = {INFORMS J. Comput.},
publisher = {INFORMS},
volume = {26},
number = {4},
pages = {658--676},
year = {2014},
keywords = {Authored}
}
We consider the short-term production scheduling problem for a network of multiple open-pit mines and ports. Ore produced at each mine is transported by rail to a set of ports and blended into signature products for shipping. Consistency in the grade and quality of production over time is critical for customer satisfaction, whereas the maximal production of blended products is required to maximise profit. In practice, short-term schedules are formed independently at each mine, tasked with achieving the grade and quality targets outlined in a medium-term plan. However, because of uncertainty in the data available to a medium-term planner and the dynamics of the mining environment, such targets may not be feasible in the short term. We present a decomposition-based heuristic for this short-term scheduling problem in which the grade and quality goals assigned to each mine are collaboratively adapted—ensuring the satisfaction of blending constraints at each port and exploiting opportunities to maximise production in the network that would otherwise be missed.