Difference: ColumnwiseFormulationsInAMPL (4 vs. 5)

Revision 52009-08-07 - CameronWalker

Line: 1 to 1
 
META TOPICPARENT name="AMPLGuide"

Columnwise Formulations in AMPL

Line: 13 to 13
 How many workers do Workhard and Co. need to staff their production plant?

We can define the set of shifts and the number of workers required for each shift:

Changed:
<
<
set SHIFTS;  # The shifts # The number of workers needed per shift param Required {SHIFTS}; 
>
>
set SHIFTS;  # The shifts
 # The number of workers needed per shift 
param Required {SHIFTS}; 
  We can also define the number of work schedules and the list of shifts each schedule covers:
Changed:
<
<
param Nsched; # The number of work schedules # The set of work schedules set SCHEDS := 1..Nsched; # The shifts covered by each schedule set SHIFT_LIST {SCHEDS} within SHIFTS; 
>
>
param Nsched; # The number of work schedules 
# The set of work schedules 
set SCHEDS := 1..Nsched; 
# The shifts covered by each schedule 
set SHIFT_LIST {SCHEDS} within SHIFTS; 
  We can define a set covering problem in the usual way:
Changed:
<
<
var Work {SCHEDS} >= 0, integer;  minimize TotalWorkers :   sum {j in SCHEDS} Work[j];  subject to ShiftNeeds {i in SHIFTS} :   sum {j in SCHEDS : i in SHIFT_LIST[j]}     Work[j] >= Required[i]; 
>
>
var Work {SCHEDS} >= 0, integer;  
minimize TotalWorkers :   sum {j in SCHEDS} Work[j];  
subject to ShiftNeeds {i in SHIFTS} :   
  sum {j in SCHEDS : i in SHIFT_LIST[j]} Work[j] >= Required[i]; 
  Note that each constraint requires us to search all our variables to find the coefficients. If our data is defined in terms of the variables, we can express our mathematical programme using a columnwise formulation.

First, we define the objective function and constraints, but we don't specify any coefficients (note that to_come tells AMPL that the (non-zero) left-hand side coefficients for the constraints will be defined at the same time as the associated variable):

Changed:
<
<
minimize TotalWorkers;  subject to ShiftNeeds {i in SHIFTS} :   to_come >= Required[i]; 
>
>
minimize TotalWorkers;  
subject to ShiftNeeds {i in SHIFTS} :  
  to_come >= Required[i]; 
  Then, we define our variables along with their objective and constraint coefficients, using the reserved words obj (for the associated non-zero objective coefficient) and coeff (for the associated non-zero left-hand side coefficients - one for each such constraint):
Changed:
<
<
var Work {j in SCHEDS} >= 0, integer,   obj TotalWorkers 1,   coeff {i in SHIFT_LIST[j]} ShiftNeeds[i] 1; 
>
>
var Work {j in SCHEDS} >= 0, integer,   
  obj TotalWorkers 1,   
  coeff {i in SHIFT_LIST[j]} ShiftNeeds[i] 1; 
  Thus, each Work variable has a coefficient of 1 in the TotalWorkers objective function and a coefficient of 1 in all the ShiftNeeds constraints for shifts in the schedule. In this way we can build up the objective function and the constraint left-hand sides with each variable definition. Furthermore, if a variable has a coefficient equal to 0 in the objective function (or the left-hand side of a constraint) we do not define that coefficient (thus reducing the necessary memory required to store the model).
 
This site is powered by the TWiki collaboration platform Powered by PerlCopyright © 2008-2021 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback