Project  Abstract

Linear programming is a powerful optimization technique and an important field in the areas of science, engineering, and business. Large-scale linear programming problems arise in many practical applications, and solving these problems requires an integration of data- analysis and data-manipulation capabilities. Database technology has become a central component of today’s information systems. Almost every type of organization is now using database systems to store, manipulate, and retrieve data. Nevertheless, little attempt has been made to facilitate general linear programming solvers for database environments. Dozens of sophisticated tools and software libraries that implement linear programming models can be found. But, there is no database-embedded linear programming tool seamlessly and transparently utilized for database processing. The focus of the study chapter is to fill this technical gap between data analysis and data manipulation, by solving large-scale linear programming problems with applications built on the database environment. Specifically, this chapter studies the representation of the linear programming model in relational structures, as well as the computational method to solve the linear programming problems. We have developed a set of ready to use stored procedures to solve general linear programming problems. A stored procedure is a group of SQL statements, precompiled and physically stored within a database, thereby having complex logic run inside the database. We show versions of procedures in the open-source MySQL database and commercial Oracle database system. The experiments are performed with several benchmark problems extracted from the Netlib library. Foundations for and preliminary experimental results of this study are presented.*

                                                     General Introduction

Linear programming is a powerful technique for dealing with the problem of allocating limited resources among competing activities, as well as other problems having a similar mathematical formulation (Winston, 1994, Richard, 1991, Walsh, 1985). It has become an important field of optimization in the areas of science and engineering and has become a standard tool of great importance for numerous business and industrial organizations. In particular, large-scale linear programming problems arise in practical applications such as logistics for large spare-parts inventory, revenue management and dynamic pricing, finance, transportation and routing, network design, and chip design (Hillier and Lieberman, 2001).

While these problems inevitably involve the analysis of a large amount of data, there has been relatively little work addressing this in the database context. Little serious attempt has been made to facilitate data-driven analysis with data-oriented techniques. In today’s marketplace, dozens of sophisticated tools and software libraries that implement linear programming models can be found. Nevertheless, these products do not work with database systems seamlessly. They rather require additional software layers built on top of databases to extract and transfer data in the databases. The focus of our study gathered here is to fill this technical gap between data analysis and data manipulation by solving large- scale linear programming problems with applications built on the database environment.

In mathematics, linear programming problems are optimization problems in which the objective function to characterize optimality of a problem and the constraints to express specific conditions for that problem are all linear (Hillier and Lieberman, 2001, Thomas H. Cormen and Stein, 2001). Two families of solution methods, so-called simplex methods (Dantzig, 1963) and interior-point methods (Karmarkar, 1984), are in wide use and available as computer programs today. Both methods progressively improve series of trial solutions by visiting edges of the feasible boundary or the points within the interior of the feasible region, until a solution is reached that satisfies the constraints and cannot be improved. In fact, it is known that large problem instances render even the best of codes nearly unusable (Winston, 1994). Furthermore, the program libraries available today are found outside the standard database environment, thus mandating the use of a special interface to interact with these tools for linear programming computations.

This chapter gives a detailed account of the methodology and technical issues related to general linear programming in the relational (or object-relational) database environment. Our goal is to find a suitable software platform for solving optimization problems on the extension of a large amount of information organized and structured in the relational databases. In principle, whenever data is available in a database, solving such problems should be done in a database way, that is, computations should be closed in the world of the database. There is a standard database language, ANSI SQL, for the manipulation of data in the database, which has grown to a level comparable to most ordinary programming or scripting languages. Eliminating reliance on a commercial linear programming package, thus eliminating the overhead of data transfer between database and package is what we hope to achieve.

There are also the issues of trade-off. A basic nature of linear programming is a collection of matrices defining a problem and a sequence of algebraic operations repeatedly applied to

these matrices, hence giving a perfect match for array-based programming in scientific computations. In general, the relational database is not designed for matrix operations like solving linear programming problems. Indeed, realizing matrix operations on top of the standard relational (or object-relational) structure is non-trivial. On the other hand, at the heart of the database system is the ability to effectively manage resources coupled with an efficient data access mechanism. The response to user is made by the best available sequence of operations, or so-called optimized queries, on the actual data. When handling extremely large matrices, the system probably gives a performance advantage over the unplanned or ad hoc execution of the program causing an insatiable use of virtual memory (thus causing thrashing) for the disposition of arrays.

In this chapter, implementation techniques and key issues for this development are studied extensively. A model suitable to capture the dynamics of linear programming computations is incorporated into the aimed development, by way of realizing a set of procedural interfaces that enables a standard database language to define problems within a database and to derive optimal solutions for those problems without requiring users to write detailed program statements. Specifically, we develop two sets of ready to use stored procedures to solve general linear programming problems. A stored procedure is a group of SQL statements, precompiled and physically stored within a database (Gulutzan and Pelzer, 1999, Gulutzan, 2007). It forms a logical unit to encapsulate a set of database operations, defined with an application program interface to perform a particular task, thereby having complex logic run inside the database. The exact implementation of a stored procedure varies from one database to another, but is supported by most major database vendors. To this end, we will show implementations using MySQL open-source database system and freely available Oracle Express Edition selected from the commercial domain. Our choice of these popular database environments is to justify the feasibility of concepts and to draw comparisons of their usability.

The rest of this chapter is organized as follows: Section 2 defines the linear programming model and introduces our approach to express the model in the relational database. Section 3 presents details of developed simulation system and experimental performance studies. Section 4 discusses related work, and Section 5 concludes our work gathered in this chapter.

1. Fundamentals

A linear programming problem consists of a collection of linear inequalities on a number of real variables and a fixed linear function to maximize or minimize. In this section, we summarize the principle technical issues in formulating the problem and some solution method in the relational database environment.

2.1 Linear Programming Principles

Consider the matrix notation expressed in the set of equations (1) below. The standard form of the linear programming problem is to maximize an objective function Z = cT x, subject to the functional constraints of Ax ≤ b and non-negativity constraints of x ≥ 0, with 0 in this case being the n-dimensional zero column vector. A coefficient matrix A and column vectors c, b, and x are defined in the obvious manner such that each component of the column

vector Ax is less than or equal to the corresponding component of the column vector b. But all forms of linear programming problems arise in practice, not just ones in the standard form, and we must deal with issues such as minimization objectives, constraints of the form Ax ≥ b or Ax = b, variables ranging in negative values, and so on. Adjustments can be made to transform every non-standard problem into the standard form. So, we limit our discussion to the standard form of the problem.

The goal is to find an optimal solution, that is, the most favorable values of the objective function among feasible ones for which all the constraints are satisfied. The simplex method (Dantzig, 1963) is an algebraic iterative procedure where each round of computation involves solving a system of equations to obtain a new trial solution for the optimality test. The simplex method relies on the mathematical property that the objective function’s maximum must occur on a corner of the space bounded by the constraints of the feasible region.

To apply the simplex method, linear programming problems must be converted into a so- called augmented form, by introducing non-negative slack variables to replace non-equalities with equalities in the constraints. The problem can then be rewritten in the following form

Related Project Topics :