Linear programming assignment problems

Example 2.—A well-known special case of the linear programming problem is the transportation problem requiring an assignment of shipments of materials from sources to destinations according to total availability and total demand, that minimizes the tot l shipping cost. If we denote the sources by St (i = 1, , m) and the destinations by... 

Note that if we relax the t binary variables by the inequalities 0 < y < 1, then (3-110) becomes a linear program with a (global) solution that is a lower bound to the MILP (3-110). There are specific MILP classes where the LP relaxation of (3-110) has the same solution as the MILP. Among these problems is the well-known assignment problem. Other MILPs that can be solved with efficient special-purpose methods are the knapsack problem, the set covering and set partitioning problems, and the traveling salesperson problem. See Nemhauser and Wolsey (1988) for a detailed treatment of these problems. 

In a sense the assignment problem in linear programming based algorithms belong to this second class of algorithms. 

Kobayashi, S., Umeda, T. and Ichikawa, A., "Synthesis of Optimal Heat Exchange Systems—An Approach by the Optimal Assignment Problem in Linear Programming," Chemical Engineering Science, Vol. 26, pp 1367-1380, 1971. 

To solve the above problem practically, we have introduced a few ideas and integrated them into the framework of our conventional method. The first one is how to choose the available PSs and their production methods and to decide the paths from PSs to REs via CCs. Here, every path from each CC to REs determines the client REs for each CC. This is equivalently to solve a customer assignment problem. For the pure cost problem, it is described below by a linear programming problem (LP). 

---