Recalling the staff scheduling example for the Pluto hot dog stand, you will remember the solution told us how many employees to start on any given day of the week. You may also remember the optimal solution had us starting whole numbers of employees on each of the days, even though we weren't using integer variables. It turns out this was just a happy coincidence. Let's return to the staffing model to demonstrate this.

In the original staffing model, we required the following number of people on duty for the seven days of the week: 20, 16, 13, 16, 19, 14, and 12. Let's change the second day requirement from 16 to 12 and the third day's requirement from 13 to 18. Incorporating this change into the model, we have:

MODEL:

SETS:

  DAYS: REQUIRED, START;

ENDSETS

 

DATA:

  DAYS =     MON TUE WED THU FRI SAT SUN;

  REQUIRED =  20  12  18  16  19  14  12;

ENDDATA

 

MIN = @SUM( DAYS( I): START( I));

 

@FOR( DAYS( J):

  @SUM( DAYS( I) | I #LE# 5:

     START( @WRAP( J - I + 1, 7)))

        >= REQUIRED( J)

);

END

After making this modest change and re-solving, we no longer have a pure integer solution. In fact, all the START variables are now fractional as the following, abbreviated solution report shows:

Global optimal solution found.

Objective value:                              23.66667

Infeasibilities:                              0.000000

Total solver iterations:                             5

Elapsed runtime seconds:                          0.03

 

Model Class:                                        LP

 

   Variable           Value        Reduced Cost

START( MON)        9.666667            0.000000

START( TUE)        2.000000            0.000000

START( WED)        1.666667            0.000000

START( THU)        5.666667            0.000000

START( FRI)        0.000000            0.000000

START( SAT)        4.666667            0.000000

START( SUN)        0.000000           0.3333333

In this particular model, we can always round the solution up and remain feasible. (In most models, we won't tend to be as lucky. Rounding the continuous solution in one direction or the other can lead to an infeasible solution.) There may be some extra staff on some of the days, but, by rounding up, we will never have a day without enough staff. Rounding the continuous solution up gives an objective of 10+2+2+6+5=25 employees.

Now, let's apply integer programming to the revised staffing model. First, we will need to use the @GIN function to make the START variables general integers. We could do this by adding the following to our model:

@GIN( @START( MON));

@GIN( @START( TUE));

@GIN( @START( WED));

@GIN( @START( THU));

@GIN( @START( FRI));

@GIN( @START( SAT));

@GIN( @START( SUN));

However, an easier approach would be to embed the @GIN function in an @FOR function, so we can apply @GIN to each member of START using the single statement:

 @FOR( DAYS( I): @GIN( START( I)));

This new statement says, for each day of the week, make the variable corresponding to the number of people to start on that day a general integer variable.

After inserting this @FOR statement at the end of our model and reoptimizing, we get the pure integer solution:

Global optimal solution found.

Objective value:                              24.00000

Objective bound:                              24.00000

Infeasibilities:                              0.000000

Extended solver steps:                               0

Total solver iterations:                            11

Elapsed runtime seconds:                          0.03

 

Model Class:                                      PILP

 

  Variable           Value        Reduced Cost

START( MON)        10.00000            1.000000

START( TUE)        2.000000            1.000000

START( WED)        1.000000            1.000000

START( THU)        6.000000            1.000000

START( FRI)        0.000000            1.000000

START( SAT)        5.000000            1.000000

START( SUN)        0.000000            1.000000

Note that the objective of 24 beats the objective of 25 obtained by rounding. Thus, had we gone with the rounded solution, we would have hired one more employee than required.