PD-01 - Linear Programming and GIS

Linear programming is a set of methods for finding optimal solutions to mathematical models composed of a set of linear functions. Many spatial location problems can be structured as linear programs. However, even modest-sized problem instances can be very difficult to solve due to the combinatorial complexity of the problems and the associated computational expense that they incur. Geographic Information Systems software does not typically incorporate formal linear programming functionality, and instead commonly uses heuristic solution procedures to generate near-optimal solutions quickly. There is growing interest in integrating the spatial analytic tools incorporated in Geographic Information Systems with the solution power of linear programming software to generate guaranteed optimal solutions to spatial location problems.
AM-42 - The Classic Transportation Problem
The classic transportation problem concerns minimizing the cost of transporting a product from sources/supplies to destinations/demands. It is a network-flow problem that arises in industrial logistics and is often solved by linear programming (LP). The three inputs of the model are total units produced at each source, total units needed at each destination, and the cost to transport one unit from each source to each destination. And the objective is to minimize the total cost of transporting all units produced at sources to meet the demands at destinations. The problem solution includes three basic steps: 1) finding an initial basic feasible solution, 2) checking if the current solution is optimal (with the lowest costs), and improving the current solution through iteration. Solving such a problem relies strongly on the network data models, least-cost path algorithms, other functionalities in GIS. And an integrated framework is often adopted to utilize both GIS and non-GIS linear programming solvers to search for the optimal solution.