Implementation of the Simplex Method
All algorithms formulated in this book, such as the simplex algorithm and the dual simplex algorithm, are theoretical or conceptional, and can not be put to practical use via programming directly. Softwares, resulting by following the algorithms, step by
- PDF / 235,896 Bytes
- 19 Pages / 439.36 x 666.15 pts Page_size
- 51 Downloads / 253 Views
Implementation of the Simplex Method
All algorithms formulated in this book, such as the simplex algorithm and the dual simplex algorithm, are theoretical or conceptional, and can not be put to practical use via programming directly. Softwares, resulting by following the algorithms, step by step naively, would only solve textbook instances, involving only few variables and constraints, not real-world problems, especially large-scale sparse problems. Experiences indicate that implementation details are crucial to algorithms’ success (Orchard-Hays 1954; Tomlin 1974; Todd 1982, 1983; Bixby 1994). This chapter will highlight effective implementation techniques, without which the simplex algorithm will become useless. The issue is mainly two-fold: one is to improve numerical stability and the other to reduce involved computational efforts. Only limited sparse techniques will be touched, as a full treatment of sparsity is beyond the scope of this book. In view of the complexity disadvantage of the tableau version (Sect. 3.8), this chapter will handle the topic based on the (revised) simplex algorithm. We stress that materials presented here are of general value, as also fit other simplex variants, perhaps with some relevant modifications. Based on the simplex algorithm, implementation techniques may lead to different codes. In particular, MINOS is the main reference in writing this chapter (see Notation).
5.1 Miscellaneous As rounding errors affect computational procedures and results (see Sect. 1.4), restricting such effects to improve the numerical stability is important to implementation of the simplex algorithm. Firstly, theoretical 0 or 1 involved in the algorithm should be treated properly by giving tolerances, in accordance with the computer precision used. Based on
P.-Q. PAN, Linear Programming Computation, DOI 10.1007/978-3-642-40754-3__5, © Springer-Verlag Berlin Heidelberg 2014
123
124
5 Implementation of the Simplex Method
MINOS, for instance, main parameters are list below, where the computer precision is assumed to be D 252 2:22 1016 Introduce notation 0 D 0:8 3:00 1013 ; 1 D 0:67 3:25 1011 ; featol D 106 ; plinfy D 1020 ; where • Quantities in solution process, whose absolute values are no more than 0 , are treated as machine 0. • Quantities, whose absolute values are more than plinfy, are treated as 1. • tolpiv D 1 is used to avoid a too small pivot; e.g., the minimum-ratio test (3.10) is actually replaced by ˛ D bNp =aN p q D minfbNi =aN i q j aN i q > tolpiv; i D 1; ; mg 0:
(5.1)
Thereby, any pivot chosen satisfies aN p q > tolpiv. The problem is regarded as unbounded if no such a pivot is found. The magnitude of a pivot seriously affects the numerical stability of the algorithm. Determination of a numerical nonzero pivot should not only depend on the computer precision, but also the problem to be solved. It is difficult to give a “best” tolpiv. Some value between 1 and 107 seems to be feasible, though still far from satisfactory. This topic will be discuss
Data Loading...
