Properly add binary variable (to examples like 5.18)

[user24feb]

Hello,

I am playing around with the optmodel-network-examples a bit, and would like to add a binary variable. This is, you have to ship a fixed minimum amount from the sources to the sinks (or ship nothing).

The example below works in principle, but I am worried about the "conditionally optimal" message. The critical restrictions are "balance" (the "<" sign) and "Lower_Upper_Flow". Is the syntax I am using all right? (The rationale I think is.)

Let Fixed_Const=1e6;

data garcs;
   input _from_ $ _to_ $ _cost_ FIXED_QTY FIXED_COST Lower Upper;
datalines;
s1 d1 1 20 10 0 150
s1 d2 8 20 70 0 150
s2 d1 4 20 50 0 150
s2 d2 2 20 20 0 150
s2 d3 1 20 10 0 150
s3 d2 5 20 50 0 150
s3 d3 4 20 40 0 150
;

data gnodes;
   input _node_ $ _sd_ ;
datalines;
s1  53
s2  21
s3  73
d1  -52
d2  -16
d3  -23
;

proc optmodel;
   set <str> NODES;
   num _sd_ {NODES} init 0;
   read data gnodes into NODES=[_node_] _sd_;

   set <str,str> ARCS;
   num Lower {ARCS} init 0;
   num Upper {ARCS};
   num _capac_ {ARCS} init .;
   num _cost_ {ARCS};
   num FIXED_QTY {ARCS}, FIXED_COST {ARCS};
   read data garcs nomiss into ARCS=[_from_ _to_] _cost_ FIXED_QTY FIXED_COST Lower Upper;
   Print FIXED_QTY;
   NODES = NODES union (union {<i,j> in ARCS} {i,j});

   var Flow {<i,j> in ARCS}>=0;
   var Flow_Fixed {<i,j> in ARCS} Binary;

   min obj = sum {<i,j> in ARCS} (_cost_[i,j] * Flow[i,j] + FIXED_COST[i,j]*FIXED_QTY[i,j]*Flow_Fixed[i,j]);
   con balance {i in NODES}: sum {<(i),j> in ARCS} (Flow[i,j] + FIXED_QTY[i,j]*Flow_Fixed[i,j])
      - sum {<j,(i)> in ARCS} (Flow[j,i] + FIXED_QTY[j,i]*Flow_Fixed[j,i]) <= _sd_; * don't need to take all supply;

   con Lower_Upper_Flow {<i,j> in ARCS}:Lower[i,j]<=Flow[i,j]+Flow_Fixed[i,j]*FIXED_QTY[i,j]<=Upper[i,j]; * is this ok?;

   * or would something like this be better? and why?;
   * -----------------------------------------------------------------;
   * num excess = sum {i in NODES} _sd_;
   *if (excess > 0) then do;
      * change equality constraint to le constraint for supply nodes;
     * for {i in NODES: _sd_ > 0} balance.lb = -infinity;
   *end;
   *else if (excess < 0) then do;
    * change equality constraint to ge constraint for demand nodes;
      *for {i in NODES: _sd_ < 0} balance.ub = infinity;
   *end;

   Con Con_Binary {<i,j> in ARCS}:Flow[i,j]<=&Fixed_Const.*Flow_Fixed[i,j]; * Flow has to be at least Fixed_Const (or nothing);

   solve;
   Print obj;
   Print Flow Flow_Fixed;
quit;

Thanks&kind regards

[RobPratt · Accepted solution]

Arbitrarily large numbers like 1e6 often introduce numerical instability, and that is why you are seeing conditionally optimal.  But your formulation also does not quite match your problem description.  If I understand correctly, the following does what you want:

   var Flow {<i,j> in ARCS} >= 0 <= Upper[i,j];

   var Flow_Fixed {ARCS} Binary;

   min obj = sum {<i,j> in ARCS} (_cost_[i,j] * Flow[i,j] + FIXED_COST[i,j]*Flow_Fixed[i,j]);

   con balance {i in NODES}: sum {<(i),j> in ARCS} Flow[i,j]

      - sum {<j,(i)> in ARCS} Flow[j,i] <= _sd_; * don't need to take all supply;

   con Upper_Flow {<i,j> in ARCS}: Flow[i,j] <= Flow[i,j].ub * Flow_Fixed[i,j];

   Con Con_Binary {<i,j> in ARCS}: Flow[i,j] >= FIXED_QTY[i,j] * Flow_Fixed[i,j]; * Flow has to be at least FIXED_QTY[i,j] (or nothing);

The resulting optimal solution has Flow[s1,d1] = 52, Flow[s2,d2] = 20, and Flow[s3,d3] = 23, for a total cost of 254.

Note that you do not need Lower or _capac_ because you don't use them anywhere.

See also this related doc example that models fixed charges in a similar way:

SAS/OR(R) 14.1 User's Guide: Mathematical Programming

Finally, you might also be interested in this book of examples, especially Depot Location (Distribution 2) and Car Rental 2:

SAS/OR(R) 14.1 User's Guide: Mathematical Programming Examples