User Tools

Site Tools


Special MIP features

Some special features have been added to GAMS to help in simplifying the modeling of MIP problems

1. Using Special Order Sets in GAMS

Special Ordered Sets (SOS) exploit special structures in MIP models during the solution phase. The precise definition of SOSs differs from one solver to another and the development of these features has been driven more by internal algorithmic consideration than by broader modelling concepts. GAMS offers a compromise SOS1 and SOS2 feature which incorporates common characteristics.

  1. SOS1: At most one variable within a set can have a non-zero value. For example, only one out of N options can be selected.
  2. SOS2: At most two variables within a set can have non-zero values. The two non-zero values have to be adjacent. For example, a non-convex separable function can be linearized using SOS2.

To use special ordered sets the GAMS model must be a Mixed Integer model since the SOS conditions are handled by the branch and bound algorithm in the same way as binary and general integer variables are handled. Variables arranged in special ordered sets are defined by a GAMS construct similar to the following examples:

   SOS1 Variable S1(I), T1(K,J)
   SOS2 Variable S2(I), T2(K,J)

The members of the innermost (the right-most) index belong to the same set. For example,

   SOS1 variables x(i,j)     defines i sets with j elements each.
   SOS1 variable  y(j)       defines one SOS1 set
   SOS2 variable  w(i,j,k)   defines (i,j) SOS2 sets with k elements each

The model PRODSCHX in the GAMS model library (SEQ=109) shows SOS type formulations with binary, SOS1 and SOS2 sets.The default bounds for SOS variables are 0 to +INF. As with any other variable, the user may set these bounds to whatever is required. The user must explicitly provide whatever convexity row that the problem needs (e.g. an equation that requires the members of the SOS set to add to one). Any such convexity row would implicitly define bounds on each of the variables.The use of special ordered sets may not always improve the performance of the branch and bound algorithm. If there is no natural 'order' the use of binary variables may be a better choice. A good example of this is the assignment problem.

WARNING: The precise definition of SOS variables can be different for various MIP solvers that allow their use, so models may not be transferable between algorithms. And not all MIP solvers allow SOS variables.

Setting Priorities for Branching

The user can specify an order for picking variables to branch on during a branch and bound search for MIP models through the use of priorities. Without priorities, the MIP algorithm will determine which variable is the most suitable to branch on. The GAMS statement to use priorities for branching during the branch and bound search is:

   modelname.PRIOROPT = 1 ;

where modelname is the name of the model specified in the model statement. The default value is 0 in which case priorities will not be used.

The priorities of the individual variables are set by using the .PRIOR suffix like in the following example:

   Z.PRIOR(I,'small')   = 3 ;
   Z.PRIOR(I,'medium')  = 2 ;
   Z.PRIOR(I,'large')   = 1 ;

Priorities can be set to any real value. The default value is 1.0. The lower the value given, the higher the priority. In the above example, Z(I,'large') variables are branched on before Z(I.'small') variables. As a general rule of thumb, the most important variables should be given the highest priority. All members of any SOS1 or SOS2 set should be given the same priority value since it is the set itself which is branched upon rather than the individual members of the set.

IMPRESSUM / LEGAL NOTICEPRIVACY POLICY gams/special_mip_features.txt · Last modified: 2007/05/24 23:16 (external edit)