Topic
  • 4 replies
  • Latest Post - ‏2013-08-22T22:01:52Z by PaulRubin
SGrogan
SGrogan
3 Posts

Pinned topic Understanding Special Ordered Sets a little better

‏2013-08-21T17:04:03Z |

Hello All;

After a bit of searching, I am still a bit unsure if I am using SOS1 Correctly.  I have a C++ code which will develop a MIP:

 X{D,T} // Decicion D in time T

ObjFn
Max:
100 X{0,0} + 90 X{0,1} + 80 X{0,2} + 70 X{0,3} //... etc

Subject to:

//Calling this the "Standard Way"

C0: X{0,0} + X{0,1} + X{0,2} + X{0,3} <= 1
C1: X{1,0} + X{1,1} + X{1,2} + X{1,3} <= 1
C2: X{2,0} + X{2,1} + X{2,2} + X{2,3} <= 1
C3: X{3,0} + X{3,1} + X{3,2} + X{3,3} <= 1

// there are also constraints that make sure that X{0,t} >= X{1,t}, X{1,t} >= X{2,t}, etc...

C4: X{0,0} + X{0,1} + X{0,2} + X{0,3} >= X{1,3}

C5: X{0,0} + X{0,1} + X{0,2} >= X{1,2}

C6: X{0,0} + X{0,1} >= X{1,1}

C7: X{0,0} >= X{1,0}

 

 

//etc...

Binaries:
 All X{i,j}

 C's 0 through 3 tell the MIP that I can only do decision D in one time period.  I was having some problems closing the gap when I stumbled across the SOS in the User Guide.  It seems to be tailored made for this kind of constraint.  However, when I use them I get a worse gap and it is much slower in closing the gap. 

 I added code to create SOS to replace the above constraints and it looks like the following (this replaces C 0-3):


id176067: S1 ::  X{0,3} : 1  X{0,2} : 2  X{0,1} : 3  X{0,0} : 4 
id176068: S1 ::  X{1,3} : 1  X{1,2} : 2  X{1,1} : 3  X{1,0} : 4 
id176069: S1 ::  X{2,3} : 1  X{2,2} : 2  X{2,1} : 3  X{2,0} : 4

Some Things I don't completely understand:

  • Is my understanding of SOS correct?  i.e. will C 0 through 3 be replaced by id17606 7 - 9 and interpreted the same way

  • I know using SOS makes X binary, rather than continuous (if it was established that way).  should I make X binary when creating the variables?  or is it OK if it is linear?

  • What do the "weightings" mean (or do)? I think if i better understand that I can have CPLEX make more intellegent decsisons

  • Will CPLEX interpret the decision variables the same way in other constraints regardless of wether I set up SOS or the more "standard" way

  • Are there any paramertes I could look at to try to speed the solving process?

Thanks in advance

Updated on 2013-08-21T18:19:29Z at 2013-08-21T18:19:29Z by SGrogan
  • PaulRubin
    PaulRubin
    55 Posts
    ACCEPTED ANSWER

    Re: Understanding Special Ordered Sets a little better

    ‏2013-08-22T22:01:52Z  
    • SGrogan
    • ‏2013-08-22T14:09:07Z

    I am still trying to get a handle on the weightings.  Unless I can assign meaningful weights to X{D,T} then using SOS can actually be worse?  Am I supposed to make a best guess on when the decision X is supposed to make (Higher values are more likely)

     

    In addition, if X{DT} is binary, is my "standard form" the same as SOS

    Your C0 to C3 constraints are mathematically equivalent to SOS1 constraints. Tactically, there are two differences I can think of. The first is that C0 to C3 do not convey weighting information. Second, they add rows to constraint matrix (and thus increase the computational burden per pivot). For some solvers (and I'm not positive CPLEX is one), an SOS1 constraint does not add rows, but instead is handled in the branching logic. The flip side of that is that with your approach, CPLEX may be able to do some tightening of variable bounds, generation of cuts or other wizardry using the explicit constraints. I'm not positive it can do the same with an SOS1 constraint.

    As to the weights, I think what you are looking for is a way to order the variables in each group so that "bisection search" (force either the first half or second half of the variables to all be zero, then repeat on the survivors) is likely to work. If, for instance, some of the x variables look to be more expensive, or more productive, than others, you might sort them that way. For what it's worth, there is a discussion of SOS1 with binary variables on OR-Exchange.

    Paul

  • SGrogan
    SGrogan
    3 Posts

    Re: Understanding Special Ordered Sets a little better

    ‏2013-08-21T18:21:47Z  

    I'd like to add that some experimentation has shown me that X being binary vs. Linear does have an effect and I should be using the Binary vars

  • DanielJunglas
    DanielJunglas
    144 Posts

    Re: Understanding Special Ordered Sets a little better

    ‏2013-08-22T08:26:23Z  
    • SGrogan
    • ‏2013-08-21T18:21:47Z

    I'd like to add that some experimentation has shown me that X being binary vs. Linear does have an effect and I should be using the Binary vars

    Did you take a look at this chapter in the user manual? It should explain how SOS constraints work.

    Adding your variables X{D,T} to an SOS does not automatically make them binary. An SOS constraint simply models the constraint "at most one of the variables in this set can be non-zero". CPLEX can explicitly exploit this information during branching, which may or may not improve performance.

    If your variables X{D,T} are supposed to take only values 0 and 1 then you should always declare them binary. If any values in [0,1] are allowed then you should keep them continuous.

  • SGrogan
    SGrogan
    3 Posts

    Re: Understanding Special Ordered Sets a little better

    ‏2013-08-22T14:09:07Z  

    Did you take a look at this chapter in the user manual? It should explain how SOS constraints work.

    Adding your variables X{D,T} to an SOS does not automatically make them binary. An SOS constraint simply models the constraint "at most one of the variables in this set can be non-zero". CPLEX can explicitly exploit this information during branching, which may or may not improve performance.

    If your variables X{D,T} are supposed to take only values 0 and 1 then you should always declare them binary. If any values in [0,1] are allowed then you should keep them continuous.

    I am still trying to get a handle on the weightings.  Unless I can assign meaningful weights to X{D,T} then using SOS can actually be worse?  Am I supposed to make a best guess on when the decision X is supposed to make (Higher values are more likely)

     

    In addition, if X{DT} is binary, is my "standard form" the same as SOS

  • PaulRubin
    PaulRubin
    55 Posts

    Re: Understanding Special Ordered Sets a little better

    ‏2013-08-22T22:01:52Z  
    • SGrogan
    • ‏2013-08-22T14:09:07Z

    I am still trying to get a handle on the weightings.  Unless I can assign meaningful weights to X{D,T} then using SOS can actually be worse?  Am I supposed to make a best guess on when the decision X is supposed to make (Higher values are more likely)

     

    In addition, if X{DT} is binary, is my "standard form" the same as SOS

    Your C0 to C3 constraints are mathematically equivalent to SOS1 constraints. Tactically, there are two differences I can think of. The first is that C0 to C3 do not convey weighting information. Second, they add rows to constraint matrix (and thus increase the computational burden per pivot). For some solvers (and I'm not positive CPLEX is one), an SOS1 constraint does not add rows, but instead is handled in the branching logic. The flip side of that is that with your approach, CPLEX may be able to do some tightening of variable bounds, generation of cuts or other wizardry using the explicit constraints. I'm not positive it can do the same with an SOS1 constraint.

    As to the weights, I think what you are looking for is a way to order the variables in each group so that "bisection search" (force either the first half or second half of the variables to all be zero, then repeat on the survivors) is likely to work. If, for instance, some of the x variables look to be more expensive, or more productive, than others, you might sort them that way. For what it's worth, there is a discussion of SOS1 with binary variables on OR-Exchange.

    Paul