Operations Research topics: SAS/OR,
SAS Optimization, and SAS Simulation Studio

Properly add binary variable (to examples like 5.18)

Accepted Solution Solved
Reply
Super Contributor
Posts: 334
Accepted Solution

Properly add binary variable (to examples like 5.18)

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


Accepted Solutions
Solution
‎08-17-2015 11:12 AM
SAS Employee
Posts: 416

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

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

View solution in original post


All Replies
Solution
‎08-17-2015 11:12 AM
SAS Employee
Posts: 416

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

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

☑ This topic is SOLVED.

Need further help from the community? Please ask a new question.

Discussion stats
  • 1 reply
  • 257 views
  • 1 like
  • 2 in conversation