Line: 1 to 1 | ||||||||
---|---|---|---|---|---|---|---|---|

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

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

> > | Union rules require that employees work 5 shifts a week, but only 1 shift in 24 hrs.
How many workers do 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 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 var Work {j in SCHEDS} >= 0, integer, obj TotalWorkers 1, coeff {i in SHIFT_LIST[j]} ShiftNeeds[i] 1;
Thus, each 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 |

Line: 1 to 1 | ||||||||
---|---|---|---|---|---|---|---|---|

Added: | ||||||||

> > |
## Columnwise Formulations in AMPL
Consider the following problem (Adapted from Section 16.2, AMPL: A Modeling Language for Mathematical Programming):
param Nsched; # The number of work schedules
\begin{verbatim}
\begin{verbatim}
\begin{verbatim}
-- MichaelOSullivan - 06 May 2008 |

View topic | History: r5 < r4 < r3 < r2 | More topic actions...

Copyright © 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

Ideas, requests, problems regarding TWiki? Send feedback