converting a non binary matrix into a binary matrix

[carenman]

I have a 4x3 matrix with numbers from 0 to 10 and I want to convert it to a 4x3 matrix with binary numbers, so any number >=1 in the original matrix becomes a 1, and all 0's stay as 0 in the new matrix.

I have managed to make it work in Excel by two different ways: a simple way using the IF function (I had to change the Solver method) and more complex way calculating the Lane pairs combinations and doing some arithmetics with them, something logically and unfortunately only valid for this specific example (so kind of useless).

In SAS, with a 4x1 matrix I was able to do it by using a linking constraint. Quick example:

proc optmodel;
set DC={1..4};
set Customer={1..3};
number demand{Customer}=[20 30 40];
number varcost{DC, Customer} = [
200 100 300
100 200 300
300 200 100
200 300 100];
number fixcost{DC} = [200 100 300 400];
number Pmax = 2;

var open{DC} binary;
var flow{DC, Customer} >= 0;
min totalcost= sum{i in DC, j in Customer}flow[i,j]*varcost[i,j] + sum{i in DC}fixcost[i]*open[i];
con demandcon{j in Customer}: sum{i in DC}flow[i,j] = demand[j];
con linkingcon{i in DC, j in Customer}: flow[i,j] <= 99999*open[i];
con maxcon: sum{i in DC}open[i] <= Pmax;
solve; print flow totalcost open;  

Those numbers where the sum{i in DC}flow[i,j] >0 will be forced to become 1, and for those <=0 the optimization will choose to make them become 0 in the OPEN 4x1 binary matrix since I am minimising and each 1 in the OPEN variable would add a fixcost to the totalcost function. This method allow me also to specify the maximum number of DC to use thanks to the Pmax (or the minimum with an additional constraint).

However, now I am dealing with a 4x3 matrix and my linking constraint doesn't seem to work since the model can now assign the 0's to any other column of the matrix when I specify a Pmax or a Pmin.

More complex example:

proc optmodel printlevel=0;

set Carrier={'I','II','III'};
set Lane={'A','B','C','D'};
set Pack={1..15};

number Bids{Carrier,Pack}=[
489 433 464 467 846 712 748 741 758 823 1112    1199    1056    1672    1872
427 446 494 452 708 758 748 712 734 714 1039    1199    1112    1693    1873
407 495 414 472 829 832 752 803 771 736 1041    1166    1073    1560    1780];

number PackBin{Lane,Pack}=[
1   0   0   0   1   1   1   0   0   0   1   1   1   0   1
0   1   0   0   1   0   0   1   1   0   1   1   0   1   1
0   0   1   0   0   1   0   1   0   1   1   0   1   1   1
0   0   0   1   0   0   1   0   1   1   0   1   1   1   1];

number DemandLane{Lane}=[12 10 14 11];
number TotalDemand = sum{j in Lane}DemandLane[j];

number MinCarrierPerLane = 2;
number MaxCarrierPerLane = 3;    

number uselinecost{Lane,Carrier}=[
99999 99999 99999
99999 99999 99999
99999 99999 99999
99999 99999 99999];

var Loads{Carrier,Pack} integer >=0 ;
var Usecarrier{Lane,Carrier} binary;

min Z=sum{i in Carrier, k in Pack}Bids[i,k]*Loads[i,k]+sum{j in Lane,i in Carrier}uselinecost[j,i]*usecarrier[j,i];

* The following constraint does not affect the result. I use it to print the Real Cost;
con Real_Cost: sum{i in Carrier, k in Pack}Bids[i,k]*Loads[i,k]>=0;

con DemandPerLaneCon{j in Lane}: sum{i in Carrier, k in Pack}PackBin[j,k]*Loads[i,k]=DemandLane[j];

con linkingcon{j in Lane, i in Carrier}: sum{k in Pack}PackBin[j,k]*Loads[i,k]<= TotalDemand*usecarrier[j,i];

* The following constraint does not affect the result. I use it to print the Lanes per Carrier;
con cons1{j in Lane, i in Carrier}: sum{k in Pack}PackBin[j,k]*Loads[i,k]>=0;

con MinCarrierPerLaneCon{j in Lane}: sum{i in Carrier}Usecarrier[j,i] >= MinCarrierPerLane;
con MaxCarrierPerLaneCon{j in Lane}: sum{i in Carrier}Usecarrier[j,i] <= MaxCarrierPerLane;

solve;
print  TotalDemand Z Real_Cost.body Usecarrier Loads cons1.body;
quit;

The MinCarrierPerLane is set to 2, and the linking constraint seems to fail to convert the 4x3 matrix (cons1.body) into a binary 4x3 matrix where 0's remain 0 and numbers >0 become 1:

result

Obviously it seems that my linking constraint is incomplete in some way, but I have not been able to find out where or why for 2 days. Any hints?

[RobPratt · Accepted solution]

Your linking constraint enforces the logical implication: if PackBin[j,k]*Loads[i,k] > 0 for some k then IsCarrier[j,i] = 1.  Without the MinCarriersPerLane constraint, the objective would naturally enforce the converse implication: if IsCarrier[j,i] = 1 then PackBin[j,k]*Loads[i,k] > 0 for some k.  But the MinCarriersPerLane constraint encourages the solver to "cheat" in the way you identified.  You can explicitly enforce the desired implication as follows:

con linkingcon2{j in Lane, i in Carrier}:
   Usecarrier[j,i] <= sum{k in Pack}PackBin[j,k]*Loads[i,k];

Also note that you don't need to declare the dummy constraints Real_Cost and cons1.  Instead, you can declare an implicit variable, which you can then reuse in the objective declaration:

impvar Real_Cost = sum{i in Carrier, k in Pack}Bids[i,k]*Loads[i,k];
min Z = Real_Cost + sum{j in Lane,i in Carrier}uselinecost[j,i]*usecarrier[j,i];

Similarly, you can reuse implicit variables in constraints:

impvar LanesPerCarrier {j in Lane, i in Carrier} = sum{k in Pack}PackBin[j,k]*Loads[i,k];
con DemandPerLaneCon{j in Lane}:
   sum{i in Carrier} LanesPerCarrier[j,i] = DemandLane[j];
con linkingcon{j in Lane, i in Carrier}:
   LanesPerCarrier[j,i] <= TotalDemand*usecarrier[j,i];
con linkingcon2{j in Lane, i in Carrier}:
   Usecarrier[j,i] <= LanesPerCarrier[j,i];

The final PRINT statement then becomes:

print  TotalDemand Z Real_Cost Usecarrier Loads LanesPerCarrier;

[carenman]

Thanks a lot for your quick, descriptive and useful reply RobPratt. 

I will make good use of the impvar and stop defining dummy constraints 😉

I see that the additional linkingcon2 is enforcing correctly the number of minimum Carriers per Lane to use and it is exactly what I needed.

I used the uselinecost in order to make the linkingcon constraints work (it wasn't a requirement of the exercise), and I had to change the values to 1's in order to obtain the real minimum cost:

number uselinecost{Lane,Carrier}=[
1 1 1 
1 1 1 
1 1 1 
1 1 1];

I knew that the minimum was lower than the one I obtained with your modifications because for having 2 or more Carriers per Lane I used a simple Capacity constraint where each Carrier could provide only the demand per Lane required minus 1:

proc optmodel printlevel=0;

set Carrier={'I','II','III'};
set Lane={'A','B','C','D'};
set Pack={1..15};

number Bids{Carrier,Pack}=[
489 433 464 467 846 712 748 741 758 823 1112    1199    1056    1672    1872
427 446 494 452 708 758 748 712 734 714 1039    1199    1112    1693    1873
407 495 414 472 829 832 752 803 771 736 1041    1166    1073    1560    1780];

number PackBin{Lane,Pack}=[
1   0   0   0   1   1   1   0   0   0   1   1   1   0   1
0   1   0   0   1   0   0   1   1   0   1   1   0   1   1
0   0   1   0   0   1   0   1   0   1   1   0   1   1   1
0   0   0   1   0   0   1   0   1   1   0   1   1   1   1];

number DemandLane{Lane}=[12 10 14 11];

number CapacityCarrier{Lane,Carrier}=[
11 11 11
9 9 9
13 13 13
10 10 10];

var Loads{Carrier,Pack} integer >=0 ;

min Z=sum{i in Carrier, k in Pack}Bids[i,k]*Loads[i,k];

con DemandPerLaneCon{j in Lane}: sum{i in Carrier, k in Pack}PackBin[j,k]*Loads[i,k]=DemandLane[j];
con CapacityCon{j in Lane, i in Carrier}: sum{k in Pack}PackBin[j,k]*Loads[i,k]<=CapacityCarrier[j,i];

solve;
print  Z Loads;
quit;

Thanks once again a have a great day.

Regards,

Carlos

[RobPratt]

Glad to help.  By the way, here's a simple way to populate CapacityCarrier without copying and pasting the values:

number CapacityCarrier{j in Lane, i in Carrier} = DemandLane[j] - 1;