A Decision Support System for Solving Linear Programming Problems

A Decision Support System for Solving Linear Programming Problems

Nikolaos Ploskas (Department of Applied Informatics, University of Macedonia, Thessaloniki, Greece), Nikolaos Samaras (Department of Applied Informatics, University of Macedonia, Thessaloniki, Greece) and Jason Papathanasiou (Department of Business Administration, University of Macedonia, Thessaloniki, Greece)
Copyright: © 2014 |Pages: 17
DOI: 10.4018/ijdsst.2014040103
OnDemand PDF Download:
$30.00
List Price: $37.50

Abstract

Linear programming algorithms have been widely used in Decision Support Systems. These systems have incorporated linear programming algorithms for the solution of the given problems. Yet, the special structure of each linear problem may take advantage of different linear programming algorithms or different techniques used in these algorithms. This paper proposes a web-based DSS that assists decision makers in the solution of linear programming problems with a variety of linear programming algorithms and techniques. Two linear programming algorithms have been included in the DSS: (i) revised simplex algorithm and (ii) exterior primal simplex algorithm. Furthermore, ten scaling techniques, five basis update methods and eight pivoting rules have been incorporated in the DSS. All linear programming algorithms and methods have been implemented using MATLAB and converted to Java classes using MATLAB Builder JA, while the web interface of the DSS has been designed using Java Server Pages.
Article Preview

1. Introduction

Web-based Decision Support Systems (DSS) are computerized information systems that provide decision support tools to managers or business analysts using only a thin-client Web Browser (Power & Kaparthi, 2002). Web-based DSS can assist a decision maker to: (i) retrieve, analyze and display data from large databases, (ii) provide access to a model, and (iii) establish communication and decision making in distributed teams (Power, 2000). In general, all types of DSS, communication-driven, knowledge-driven and document-driven (Bhargava et al., 2007), can be implemented as a web-based DSS (Power, 2000).

Linear programming algorithms have been widely used in DSS for supplier selection (Ghodsypour & O'Brien, 1998), forest management planning systems (Lappi et al., 1996), assignment of parking spaces (Venkataramanan & Bornstein, 1991), schedule of student attendants (Lauer et al., 1994), portfolio robustness evaluation (Lourenço et al., 2012), optimality in open air reservoir strategies (Van Vuuren & Grundlingh, 2002), energy planning (Mavrotas, 2000) and water resource management (Faye et al., 1998) among others. However, the special structure of each linear problem should be taken into consideration in order to take advantage of different linear programming algorithms and methods.

This paper presents a web-based DSS that provides decision support tools to decision makers that want to solve their linear programming problems. The paper builds on the work of Ploskas et al. (2013). Ploskas et al. (2013) have implemented a web-based DSS that assists decision makers in the selection of the linear programming algorithm and basis update method for solving their linear programming problems. In this paper, we do not only take into consideration the basis update step, but go further to explore all different steps of the linear programming algorithms. The main difference from our previous paper (Ploskas et al., 2013) is that here we include ten scaling techniques, five basis update methods and eight pivoting rules; the user can select any combination of these methods to be included in the execution of the linear programming algorithm or let the DSS select the best combination for the selected linear programming problem.

Two linear programming algorithms are incorporated in the DSS: (i) Revised Simplex Algorithm (Dantzig, 1953) and (ii) Exterior Primal Simplex Algorithm (Paparrizos et al., 2003). The DSS also includes a variety of different methods for the different steps of these algorithms. More specifically, ten scaling techniques, five basis update methods and eight pivoting rules have been implemented in the DSS. The decision maker can either select the algorithm and the appropriate methods to solve a linear programming problem or perform a thorough computational study with all combinations of algorithms and methods in order to gain an insight on its linear programming problem.

There are already linear programming solvers in the market that efficiently solve linear programming problems (LPs), but either they do not include so many scaling techniques, basis update methods and pivoting rules, either they do not allow the user to choose some of them. To the best of our knowledge, this is the first paper that implements a DSS for solving linear programming problems that include all these different methods for scaling, basis update and pivoting, and lets the user select the different combinations of the methods to be included in the execution of the linear programming algorithm.

The rest of this paper is organized as follows. Section 2 presents the background of our work. In Section 3, ten widely-used scaling techniques that incorporated in the DSS are presented. Section 4 includes the presentation of the five basis update methods implemented in the DSS, while in Section 5 eight well-known pivoting rules that incorporated in the DSS are presented. Section 6 includes the analysis and design of the DSS, while in Section 7 the DSS is presented. Finally, the conclusions of this paper are outlined in Section 8.

Complete Article List

Search this Journal:
Reset
Open Access Articles: Forthcoming
Volume 10: 4 Issues (2018): 1 Released, 3 Forthcoming
Volume 9: 4 Issues (2017)
Volume 8: 4 Issues (2016)
Volume 7: 4 Issues (2015)
Volume 6: 4 Issues (2014)
Volume 5: 4 Issues (2013)
Volume 4: 4 Issues (2012)
Volume 3: 4 Issues (2011)
Volume 2: 4 Issues (2010)
Volume 1: 4 Issues (2009)
View Complete Journal Contents Listing