Difference: ColumnwiseFormulationsInAMPL (1 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).

Revision 42009-07-23 - CameronWalker

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

Columnwise Formulations in AMPL

Consider the following problem (Adapted from Section 16.2, AMPL: A Modeling Language for Mathematical Programming):

Changed:
<
<
WorkHard and Co are scheduling workers for their production shifts during the week. All workers are paid the same wage, so they want to minimise the number of workers needed.
>
>
Workhard and Co. are scheduling workers for their production shifts during the week. All workers are paid the same wage, so they want to minimise the number of workers needed.
  There are three shifts during the week (Mon-Fri) and two on Sat. The daily shifts require 100, 78 and 52 employees respectively.

Union rules require that employees work 5 shifts a week, but only 1 shift in 24 hrs.

Changed:
<
<
How many workers do WorkHard need to staff their production plant?
>
>
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).
Changed:
<
<
This is an elegant solution if the constraint coefficients are defined in terms of the variables rather than the constraints. One problem remains, how do we define our work schedules? We can use either a depth-first search or power sets.
>
>
This is an elegant solution if the constraint coefficients are defined in terms of the variables rather than the constraints. One problem remains: how do we define our work schedules? We can use either a depth-first search or power sets.
  -- MichaelOSullivan - 06 May 2008 \ No newline at end of file

Revision 32008-05-07 - MichaelOSullivan

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

Columnwise Formulations in AMPL

Revision 22008-05-06 - MichaelOSullivan

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

Columnwise Formulations in AMPL

Changed:
<
<
Consider the following problem (Adapted from Section 16.2, AMPL: A Modeling Language for Mathematical Programming):

=!WorkHard= and Co are scheduling workers for their production shifts during the week. All workers are paid the same wage, so they want to minimise the number of workers needed.

Their are three shifts during the week (Mon-Fri) and two on Sat. The daily shifts require 100, 78 and 52 employees respectively.

Union rules require that employees work 5 shifts a week, but only 1 shift in 24 hrs.

How many workers do !WorkHard need to staff their production plant?

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

set SHIFTS; # The shifts
# The number of workers needed per shift
param Required {SHIFTS};
>
>
Consider the following problem (Adapted from Section 16.2, AMPL: A Modeling Language for Mathematical Programming):
 
Changed:
<
<

We can also define the number of work schedules and the list of shifts each schedule covers:

>
>
WorkHard and Co are scheduling workers for their production shifts during the week. All workers are paid the same wage, so they want to minimise the number of workers needed.
 
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;
>
>
There are three shifts during the week (Mon-Fri) and two on Sat. The daily shifts require 100, 78 and 52 employees respectively.
 
Changed:
<
<

We can define a set covering problem in the usual way:

\begin{verbatim}
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];
\end{verbatim}


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 {\tt 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) :

\begin{verbatim}
minimize TotalWorkers;
subject to ShiftNeeds {i in SHIFTS} :
to_come >= Required[i];
\end{verbatim}



Then, we define our variables along with their objective and constraint coefficients, using the reserved words {\tt obj} (for the associated non-zero objective coefficient) and {\tt coeff} (for the associated non-zero left-hand side coefficients - one for each such constraint):

\begin{verbatim}
var Work {j in SCHEDS} >= 0, integer,
obj TotalWorkers 1,
coeff {i in SHIFT_LIST[j]} ShiftNeeds[i] 1;
\end{verbatim}


Thus, each {\tt Work} variables has a coefficient of 1 in the {\tt TotalWorkers} objective function and a coefficient of 1 in all the {\tt 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 is an elegant solution if the constraint coefficients are defined in terms of the variables rather than the constraints. One problem remains, how do we define our work schedules? We can use either a depth-first search or power sets.

>
>
Union rules require that employees work 5 shifts a week, but only 1 shift in 24 hrs.

How many workers do WorkHard need to staff their production plant?

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

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:

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:

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):

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):

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 is an elegant solution if the constraint coefficients are defined in terms of the variables rather than the constraints. One problem remains, how do we define our work schedules? We can use either a depth-first search or power sets.

  -- MichaelOSullivan - 06 May 2008 \ No newline at end of file

Revision 12008-05-06 - MichaelOSullivan

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

Columnwise Formulations in AMPL

Consider the following problem (Adapted from Section 16.2, AMPL: A Modeling Language for Mathematical Programming):

=!WorkHard= and Co are scheduling workers for their production shifts during the week. All workers are paid the same wage, so they want to minimise the number of workers needed.

Their are three shifts during the week (Mon-Fri) and two on Sat. The daily shifts require 100, 78 and 52 employees respectively.

Union rules require that employees work 5 shifts a week, but only 1 shift in 24 hrs.

How many workers do !WorkHard need to staff their production plant?

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


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:


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:

\begin{verbatim}
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];
\end{verbatim}


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 {\tt 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) :

\begin{verbatim}
minimize TotalWorkers;
subject to ShiftNeeds {i in SHIFTS} :
to_come >= Required[i];
\end{verbatim}



Then, we define our variables along with their objective and constraint coefficients, using the reserved words {\tt obj} (for the associated non-zero objective coefficient) and {\tt coeff} (for the associated non-zero left-hand side coefficients - one for each such constraint):

\begin{verbatim}
var Work {j in SCHEDS} >= 0, integer,
obj TotalWorkers 1,
coeff {i in SHIFT_LIST[j]} ShiftNeeds[i] 1;
\end{verbatim}


Thus, each {\tt Work} variables has a coefficient of 1 in the {\tt TotalWorkers} objective function and a coefficient of 1 in all the {\tt 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 is an elegant solution if the constraint coefficients are defined in terms of the variables rather than the constraints. One problem remains, how do we define our work schedules? We can use either a depth-first search or power sets.

-- MichaelOSullivan - 06 May 2008

 
This site is powered by the TWiki collaboration platform Powered by PerlCopyright © 2008-2020 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback