We use cookies to ensure that we give you the best experience on our website. By continuing to browse this repository, you give consent for essential cookies to be used. You can read more about our Privacy and Cookie Policy.

Durham Research Online
You are in:

Improved linear programming methods for checking avoiding sure loss.

Nakharutai, Nawapon and Troffaes, Matthias C. M. and Caiado, Camila C. S. (2018) 'Improved linear programming methods for checking avoiding sure loss.', International journal of approximate reasoning., 101 . pp. 293-310.

This is the latest version of this eprint.


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.

Item Type:Article
Full text:(AM) Accepted Manuscript
Available under License - Creative Commons Attribution Non-commercial No Derivatives.
Download PDF
Publisher Web site:
Publisher statement:© 2018 This manuscript version is made available under the CC-BY-NC-ND 4.0 license
Date accepted:28 July 2018
Date deposited:07 August 2018
Date of first online publication:01 August 2018
Date first made open access:01 August 2019

Save or Share this output

Look up in GoogleScholar

Available Versions of this Item