Exploiting sparsity

Discusses how to exploit the sparsity of large-scale problems, beyond the classical transportation problem exposed in the transp1.mod sample.

The following example, transp3.mod, depicts the model of the transportation problem, known as a multicommodity flow problem on a bipartite graph. The instance data is available in this file:

<Install_dir>\opl\examples\opl\transp\transp3.dat

which is too long to be shown here.

{string} Cities =...;
{string} Products = ...;
float Capacity = ...;
tuple connection { string o; string d; }
tuple route { 
  string p; 
  connection e; 
}
{route} Routes = ...;
{connection} Connections = { c | <p,c> in Routes };
tuple supply { 
  string p; 
  string o; 
}
{supply} Supplies = { <p,c.o> | <p,c> in Routes };
float Supply[Supplies] = ...;
tuple customer { 
  string p; 
  string d; 
}
{customer} Customers = { <p,c.d> | <p,c> in Routes };
float Demand[Customers] = ...;
float Cost[Routes] = ...;
{string} Orig[p in Products] = { c.o | <p,c> in Routes };
{string} Dest[p in Products] = { c.d | <p,c> in Routes };

{connection} CPs[p in Products] = { c | <p,c> in Routes };
assert forall(p in Products) 
   sum(o in Orig[p]) Supply[<p,o>] == sum(d in Dest[p]) Demand[<p,d>];

dvar float+ Trans[Routes];   

constraint ctSupply[Products][Cities];
constraint ctDemand[Products][Cities];

minimize
  sum(l in Routes) 
    Cost[l] * Trans[l];
subject to {
  forall( p in Products , o in Orig[p] ) 
    ctSupply[p][o]: 
      sum( <o,d> in CPs[p] ) 
        Trans[< p,<o,d> >] == Supply[<p,o>];
  forall( p in Products , d in Dest[p] ) 
    ctDemand[p][d]:  
      sum( <o,d> in CPs[p] ) 
        Trans[< p,<o,d> >] == Demand[<p,d>];
  forall(c in Connections)
    ctCapacity:             
      sum( <p,c> in Routes ) 
        Trans[<p,c>] <= Capacity;
} 

This is a classic transportation problem with the addition of a capacity constraint on the inter-cities connections. The model is, of course, not appropriate for large-scale transportation problems, where only a fraction of the cities are connected and a fraction of the products are sent along the connections. This section discusses how to exploit the sparsity of large-scale problems. OPL offers more support than other modeling languages in this respect, because it can use tuples and arrays indexed by arbitrary finite sets. The methodology for exploiting sparsity in OPL consists of mirroring, in the model, the structure of the application. This structure can be inferred from the objective function and the constraints of the application. For instance, the capacity constraint for the transportation application can be phrased as

“The products sent along any given connection may not exceed the given capacity.”

This constraint helps identify two main concepts in the application. The first is the connection between two cities, which can be represented explicitly by a data type

tuple connection { string o; string d; }

to manipulate connections as first-class objects. The second fundamental concept is the transportation of a product along a connection, called a route in this section. Once again, this concept can be represented explicitly by a data type

tuple route { 
  string p; 
  connection e; 
}

to manipulate routes directly. The supply and demand constraints exhibit two other fundamental concepts: product suppliers (i.e., the association of a product and a city supplying it) and product consumers (i.e., the association of a product and a city consuming it). The data types

tuple Supply { string p; string o; }; 
tuple Customer { string p; string d; }; 

may be used to represent them.

Once the concepts are identified, an appropriate data representation can be chosen so that the model can generate constraints efficiently. Of course, the user data is not necessarily expressed in this representation, but it is usually easy in OPL to transform the user data into an appropriate representation.

A good representation for this application consists of a set of connections, a set of routes, the cost of the routes, and the demand and supply information. For example:

{route} Routes = ...;
{connection} Connections = { c | <p,c> in Routes };
tuple supply { 
  string p; 
  string o; 
}
{supply} Supplies = { <p,c.o> | <p,c> in Routes };
float Supply[Supplies] = ...;
tuple customer { 
  string p; 
  string d; 
}
{customer} Customers = { <p,c.d> | <p,c> in Routes };
float Demand[Customers] = ...;
float Cost[Routes] = ...;

Note that the connections, suppliers, and customers are derived automatically from the routes. It is also useful to derive the following data to simplify the constraint statement:

{string} Orig[p in Products] = { c.o | <p,c> in Routes };
{string} Dest[p in Products] = { c.d | <p,c> in Routes };

{connection} CPs[p in Products] = { c | <p,c> in Routes };

The objective function and the constraints can now be stated naturally. The objective function

“minimize the transportation costs along all routes”

is expressed elegantly as

minimize
  sum(l in Routes) 
    Cost[l] * Trans[l];

The supply constraint, which can be phrased as

“for every product and every city shipping the product, the summation of all transportations from that city to a city where the product is in demand is equal to the supply of the product at the supplying city”

is formalized by

  forall( p in Products , o in Orig[p] ) 
    ctSupply[p][o]: 
      sum( <o,d> in CP[p] ) 
        Trans[< p,<o,d> >] == Supply[<p,o>];

The demand constraints are stated in a similar way. The capacity constraints are stated elegantly as

  forall(c in Connections)
    ctCapacity:             
      sum( <p,c> in Routes ) 
        Trans[<p,c>] <= Capacity;

This statement is efficient, since OPL retrieves the product from the routes in an efficient way when the connection is known. The complete model is shown in A sparse multi-product transportation model (transp3.mod).

Assume now that part of the user data is given by a relational table that contains tuples of the form <o,d,p,c> indicating that a connection between cities o and d transports product p at cost c. This data can be transformed into the representation used in A sparse multi-product transportation model (transp3.mod). The routes can be obtained as

{Route} Routes = { < <o,d>,p> | <p,o,d,c> in TableRoutes }; 

and the costs as

float Cost[Routes] = [ <t.p,<t.o,t.d>>:t.cost | t in TableRoutes ];

Both preprocessing instructions are linear in the size of the table.