Ordered alternatives

Suppose you have N possible investments of which at most one can be selected. The capital cost is CAP_i and the expected return is RET_i.

• Often use binary variables to choose between alternatives. However, SOS1 are more efficient to choose between a set of graded (ordered) alternatives.
• Define a variable d_i to represent the decision, d_i = 1 if investment i is picked
• Binary variable (standard) formulation
  
  d_i : binary variables

  Maximize: ret = ∑i RETidi

  ∑i di ≤ 1

  ∑i CAPidi ≤ MAXCAP

• SOS1 formulation
  
  {d_i; ordering value CAP_i} : SOS1

  Maximize: ret = ∑i RETidi

  ∑i di ≤ 1

  ∑i CAPidi ≤ MAXCAP

• Special ordered sets in Mosel
  • special ordered sets are a special type of linear constraint
  • the set includes all variables in the constraint
  • the coefficient of a variable is used as the ordering value (i.e., each value must be unique)

  declarations
    I=1..4
    d: array(I) of mpvar
    CAP: array(I) of real
    My_Set, Ref_row: linctr
  end-declarations
  
  My_Set:= sum(i in I) CAP(i)*d(i) is_sos1

  or alternatively (must be used if a coefficient is 0):

  Ref_row:= sum(i in I) CAP(i)*d(i)
  makesos1(My_Set, union(i in I) {d(i)}, Ref_row)

• Special ordered sets in BCL
  • a special ordered set is an object of type XPRBsos
  • the set includes all variables from the specified linear expression or constraint that have a coefficient different from 0
  • the coefficient of a variable is used as the ordering value (i.e., each value must be unique)

  XPRBprob prob("testsos");
  XPRBvar d[I];
  XPRBexpr le;
  XPRBsos My_Set;
  double CAP[I];
  int i;
  
  for(i=0; i<I; i++) d[i] = prob.newVar("d");
  
  for(i=0; i<I; i++) le += CAP[i]*d[i];
  My_Set = prob.newSos("My_Set", XPRB_S1, le);