Properly add binary variable (to examples like 5.18)

user24feb — Mon, 17 Aug 2015 14:34:43 GMT

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

Re: Properly add binary variable (to examples like 5.18)

RobPratt — Mon, 17 Aug 2015 15:12:10 GMT

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

topic Properly add binary variable (to examples like 5.18) in Mathematical Optimization, Discrete-Event Simulation, and OR

Properly add binary variable (to examples like 5.18)

Re: Properly add binary variable (to examples like 5.18)