Scaling Techniques

Nikolaos Ploskas and Nikolaos Samaras
Additional contact information
Nikolaos Ploskas: University of Macedonia
Nikolaos Samaras: University of Macedonia

Chapter Chapter 5 in Linear Programming Using MATLAB®, 2017, pp 219-275 from Springer

Abstract: Abstract Preconditioning techniques are important in solving LPs, as they improve their computational properties. One of the most widely used preconditioning technique in LP solvers is scaling. Scaling is used prior to the application of an LP algorithm in order to: (i) produce a compact representation of the variable bounds, (ii) reduce the condition number of the constraint matrix, (iii) improve the numerical behavior of the algorithms, (iv) reduce the number of iterations required to solve LPs, and (v) simplify the setup of the tolerances. This chapter presents eleven scaling techniques used prior to the execution of an LP algorithm: (i) arithmetic mean, (ii) de Buchet for the case p = 1, (iii) de Buchet for the case p = 2, (iv) de Buchet for the case p = ∞, (v) entropy, (vi) equilibration, (vii) geometric mean, (viii) IBM MPSX, (ix) L p-norm for the case p = 1, (x) L p-norm for the case p = 2, and (xi) L p-norm for the case p = ∞. Each technique is presented with: (i) its mathematical formulation, (ii) a thorough illustrative numerical example, and (iii) its implementation in MATLAB. Finally, a computational study is performed. The aim of the computational study is twofold: (i) compare the execution time of the scaling techniques, and (ii) investigate the impact of scaling prior to the application of LP algorithms. The execution time and the number of iterations with and without scaling are presented.

Date: 2017
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:spochp:978-3-319-65919-0_5

Ordering information: This item can be ordered from
http://www.springer.com/9783319659190

DOI: 10.1007/978-3-319-65919-0_5

Access Statistics for this chapter

More chapters in Springer Optimization and Its Applications from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().