Skip to main content

Research Repository

Advanced Search

Improved linear programming methods for checking avoiding sure loss

Nakharutai, Nawapon; Troffaes, Matthias C.M.; Caiado, Camila C.S.

Improved linear programming methods for checking avoiding sure loss Thumbnail


Authors

Nawapon Nakharutai



Abstract

We review the simplex method and two interior-point methods (the affine scaling and the primal-dual) for solving linear programming problems for checking avoiding sure loss, and propose novel improvements. We exploit the structure of these problems to reduce their size. We also present an extra stopping criterion, and direct ways to calculate feasible starting points in almost all cases. For benchmarking, we present algorithms for generating random sets of desirable gambles that either avoid or do not avoid sure loss. We test our improvements on these linear programming methods by measuring the computational time on these generated sets. We assess the relative performance of the three methods as a function of the number of desirable gambles and the number of outcomes. Overall, the affine scaling and primal-dual methods benefit from the improvements, and they both outperform the simplex method in most scenarios. We conclude that the simplex method is not a good choice for checking avoiding sure loss. If problems are small, then there is no tangible difference in performance between all methods. For large problems, our improved primal-dual method performs at least three times faster than any of the other methods.

Journal Article Type Article
Acceptance Date Jul 28, 2018
Online Publication Date Aug 1, 2018
Publication Date Oct 31, 2018
Deposit Date Jun 15, 2018
Publicly Available Date Aug 1, 2019
Journal International Journal of Approximate Reasoning
Print ISSN 0888-613X
Publisher Elsevier
Peer Reviewed Peer Reviewed
Volume 101
Pages 293-310
DOI https://doi.org/10.1016/j.ijar.2018.07.013
Public URL https://durham-repository.worktribe.com/output/1324148
Related Public URLs https://arxiv.org/abs/1808.03076

Files





You might also like



Downloadable Citations