How can I represent null or dashes in a cost matrix or incidence matrix in CPLEX?

Question

In the image below, the cost matrix of customers and supplier has several dashes which indicates the impossibility of certain suppliers with certain customers. How can I represent these dashes in CPLEX?

Answer 1

This looks like problem 19 in HP Williams Model Building.

As you can see below, the "-" are not in the tuple set for costs

.mod

{string} factories=...;
{string} depots=...;
{string} customers=...;

int monthlyCapacity[factories]=...;
int monthlyMaxThroughput[depots]=...;
int monthlyRequirement[customers]=...;

tuple cost
{
key string origin;
key string destination;
float price;
}

tuple preference
{

string origin;
string destination;
}

{cost} costFactoryToDepot with origin in factories,destination in depots=...;
{cost} costDepotToCustomer with origin in depots,destination in customers=...;
{cost} costFactoryToCustomer with origin in factories,destination in customers=...;

{string} origins=factories union depots;

{preference} preferences with origin in origins=...;

{string} customersWithPreferences={p.destination | p in preferences};

dvar float+ x[factories][depots];
dvar float+ y[factories][customers];
dvar float+ z[depots][customers];

dvar float totalCost;
dvar float unmetPreferences;

minimize totalCost;
subject to
{




totalCost==
sum(c in costFactoryToDepot) c.price*x[c.origin][c.destination]
+sum(c in costDepotToCustomer) c.price*z[c.origin][c.destination]
+sum(c in costFactoryToCustomer) c.price*y[c.origin][c.destination]
;

// Links with no cost do not exist
forall(o in factories,d in depots:0== (<o,d>  in costFactoryToDepot)) x[o][d]==0;
forall(o in factories,d in customers: 0 == (<o,d> in costFactoryToCustomer)) y[o][d]==0;
forall(o in depots,d in customers: (0==<o,d>  in costDepotToCustomer)) z[o][d]==0;

forall(i in factories)
    ctFactoryCapacity:
        sum(j in depots) x[i][j]+sum(k in customers) y[i][k]<=monthlyCapacity[i];

forall(j in depots)
    ctInDepots:
        sum(i in factories) x[i][j]<=monthlyMaxThroughput[j];

forall(j in depots)
    ctOutDepots:
        sum(i in factories) x[i][j]==sum(k in customers) z[j][k];

forall(k in customers)
      ctCustomerRequirement:
          sum(i in factories) y[i][k] + sum(j in depots) z[j][k] == monthlyRequirement[k];

ctUnMetPrefs:unmetPreferences==sum(k in customersWithPreferences)

    (monthlyRequirement[k]
        -sum(p in preferences:p.destination==k && p.origin in factories)    y[p.origin][k]    -
        sum(p in preferences:p.destination==k && p.origin in depots)    z[p.origin][k])    ;



}

execute
{
writeln("total cost = ",totalCost);

for(var f in factories) for(var d in depots) if (x[f][d]>0) writeln(f," --> ",d," : ",x[f][d]);
for(var f in factories) for(var c in customers) if (y[f][c]>0) writeln(f," --> ",c," : ",y[f][c]);
for(var d in depots) for(var c in customers) if (z[d][c]>0) writeln(d," --> ",c," : ",z[d][c]);
}

main
{
thisOplModel.generate();
cplex.solve();
thisOplModel.postProcess();

writeln();
writeln("And now with taking into account preferences as much as possible");
writeln();

cplex.setObjCoef(thisOplModel.unmetPreferences,1000000);
cplex.solve();
thisOplModel.postProcess();
}

.dat

factories= {Liverpool,Brighton};
depots = {Newcastle, Birmingham, London, Exeter};
customers = {c1, c2, c3, c4, c5, c6};

monthlyCapacity=[150000,200000];
monthlyMaxThroughput= [70000,50000,100000,40000];
monthlyRequirement=[50000,10000,40000,35000,60000,20000];

costFactoryToDepot={
<Liverpool, Newcastle,   0.5,>
<Liverpool, Birmingham,  0.5,>
<Liverpool, London,      1.0,>
<Liverpool, Exeter ,     0.2,>
<Brighton,  Birmingham,  0.3,>
<Brighton,  London ,     0.5,>
<Brighton,  Exeter ,     0.2>
};

costDepotToCustomer=
{
<Newcastle , c2 ,1.5>,
<Newcastle , c3, 0.5>,
<Newcastle , c4 ,1.5>,
<Newcastle , c6, 1.0>,
<Birmingham ,c1, 1.0>,
<Birmingham, c2 ,0.5>,
<Birmingham, c3 ,0.5>,
<Birmingham, c4, 1.0>,
<Birmingham ,c5, 0.5>,
<London ,    c2, 1.5>,
<London,     c3 ,2.0>,
<London ,    c5, 0.5>,
<London ,    c6 ,1.5>,
<Exeter,     c3 ,0.2>,
<Exeter,     c4 ,1.5>,
<Exeter,     c5 ,0.5>,
<Exeter,     c6 ,1.5>
};

costFactoryToCustomer=
{
<Liverpool c1 1.0>,
<Liverpool c3 1.5>,
<Liverpool c4 2.0>,
<Liverpool c6 1.0>,
<Brighton  c1 2.0>
};

preferences=
{
<Liverpool, c1>,
<Newcastle, c2>,
<Birmingham,c5>,
<Exeter,c6>,
<London,c6>
};

which gives

total cost = 198500
Liverpool --> Exeter : 40000
Brighton --> Birmingham : 50000
Brighton --> London : 55000
Liverpool --> c1 : 50000
Liverpool --> c6 : 20000
Birmingham --> c2 : 10000
Birmingham --> c4 : 35000
Birmingham --> c5 : 5000
London --> c5 : 55000
Exeter --> c3 : 40000

And now with taking into account preferences as much as possible:

total cost = 246000
Liverpool --> Newcastle : 10000
Liverpool --> Exeter : 40000
Brighton --> Birmingham : 50000
Brighton --> London : 30000
Liverpool --> c1 : 50000
Liverpool --> c4 : 35000
Newcastle --> c2 : 10000
Birmingham --> c5 : 50000
London --> c5 : 10000
London --> c6 : 20000
Exeter --> c3 : 40000

Answer 2

The dashes are just a visual representation of the fact that certain suppliers cannot serve certain customers. So you are not really "representing" these dashes in CPLEX, but rather you are representing the idea behind those dashes.

In a mathematical optimization model (whether it's in CPLEX or elsewhere), you have two choices: (1) set the costs to something very large (so the solution will not use those pairs), or (2) explicitly prohibit those suppliers from serving those customers.

I prefer (2) because setting some large costs in (1) might lead to scaling issues, and because you are allowing non-zero decision variables but the solver will have to "figure out" that it should not use those variables. Modern solvers (like CPLEX) are probably smart enough to do this without much trouble, but I still feel (2) is safer.

So, I'd add a new parameter like $a_{ij}$ that equals 1 if supplier $i$ is allowed to serve customer $j$ and 0 otherwise, and then use this parameter in your model to prohibit disallowed assignments.

Answer 3

Adding to @LarrySnyder610's answer, I prefer option (3): you do not define the "non-existing" options in the first place. When there are $x_{ij}\in\{0,1\}$ variables to be defined for the assignment (or integer variables for quantities...), you can define them "from everywhere to everywhere", and then use options (1) or (2); or you modify option (2) to define a set $E$ of allowed pairs and only define the variables for pairs in this set $E$. Why define something wrong and correct it later, when you can define it right in the first place? This is certainly a matter of taste.