p4 | Employee Transportation¶
See also
This problem is sourced from EquivaFormulation (instance id: 183).
Note
The source incorrectly encodes integer variables with
"shape": ["Integer"]; we correct this to"type": "integer".The cutting plane (source variation
183_e) is excluded because it is instance-specific.Implicit non-negativity assumptions are added for every parameter.
Description¶
Employees have the option of using Car or Bus for transportation. A Car can carry CarCapacity employees and produces CarPollution units of pollution, while a Bus can carry BusCapacity employees and produces BusPollution units of pollution. At least MinEmployeesToTransport employees must be transported, and no more than MaxBuses Buses can be used. The objective is to minimize the total pollution produced.
Formulations¶
Formulation a (valid)¶
See also
This formulation is sourced from EquivaFormulation (instance id: 183, variation id: original).
Note
Original formulation; no transformations.
Parameters¶
Name |
Description |
Type |
Shape |
|---|---|---|---|
|
The number of employees that a car can take |
integer |
scalar |
|
The pollution produced by a car |
continuous |
scalar |
|
The number of employees that a bus can take |
integer |
scalar |
|
The pollution produced by a bus |
continuous |
scalar |
|
The minimum number of employees that need to be transported |
continuous |
scalar |
|
The maximum number of buses that can be used |
continuous |
scalar |
Variables¶
Name |
Description |
Type |
Shape / Indices |
|---|---|---|---|
|
The number of cars used for transportation |
integer |
scalar |
|
The number of buses used for transportation |
integer |
scalar |
Assumptions¶
Description |
Formulation |
Implicit |
|---|---|---|
The number of employees that a car can take must be non-negative. |
\(CarCapacity \geq 0\) |
yes |
The pollution produced by a car must be non-negative. |
\(CarPollution \geq 0\) |
yes |
The number of employees that a bus can take must be non-negative. |
\(BusCapacity \geq 0\) |
yes |
The pollution produced by a bus must be non-negative. |
\(BusPollution \geq 0\) |
yes |
The minimum number of employees that need to be transported must be non-negative. |
\(MinEmployeesToTransport \geq 0\) |
yes |
The maximum number of buses that can be used must be non-negative. |
\(MaxBuses \geq 0\) |
yes |
Constraints¶
At least MinEmployeesToTransport employees must be transported.
\[ xCars \cdot CarCapacity + xBuses \cdot BusCapacity \geq MinEmployeesToTransport \]No more than MaxBuses buses can be used.
\[ xBuses \leq MaxBuses \]Number of cars used is non-negative. (implicit)
\[ xCars \geq 0 \]Number of buses used is non-negative. (implicit)
\[ xBuses \geq 0 \]
Objective¶
Total pollution produced is the sum of pollution from cars and buses. The objective is to minimize the total pollution produced.
Formulation b (valid)¶
See also
This formulation is sourced from EquivaFormulation (instance id: 183, variation id: c).
Note
Change the names of parameters and variables.
Parameters¶
Name |
Description |
Type |
Shape |
|---|---|---|---|
|
The lowest quantity of staff that must be transported |
continuous |
scalar |
|
The emissions generated by a vehicle |
continuous |
scalar |
|
The capacity of individuals that a vehicle can accommodate |
integer |
scalar |
|
The capacity of employees that a bus can accommodate. |
integer |
scalar |
|
The emissions generated by a bus. |
continuous |
scalar |
|
The highest possible quantity of buses that can be employed |
continuous |
scalar |
Variables¶
Name |
Description |
Type |
Shape / Indices |
|---|---|---|---|
|
The quantity of buses utilized for transportation |
integer |
scalar |
|
The quantity of vehicles utilized for travel purposes. |
integer |
scalar |
Assumptions¶
Description |
Formulation |
Implicit |
|---|---|---|
The lowest quantity of staff that must be transported must be non-negative. |
\(J \geq 0\) |
yes |
The emissions generated by a vehicle must be non-negative. |
\(M \geq 0\) |
yes |
The capacity of individuals that a vehicle can accommodate must be non-negative. |
\(K \geq 0\) |
yes |
The capacity of employees that a bus can accommodate must be non-negative. |
\(D \geq 0\) |
yes |
The emissions generated by a bus must be non-negative. |
\(O \geq 0\) |
yes |
The highest possible quantity of buses that can be employed must be non-negative. |
\(S \geq 0\) |
yes |
Constraints¶
The maximum number of buses that can be utilized is S.
\[ S \geq h \]A minimum of J employees need to be transported.
\[ J \leq m \cdot K + h \cdot D \]Number of vehicles used is non-negative. (implicit)
\[ m \geq 0 \]Number of buses used is non-negative. (implicit)
\[ h \geq 0 \]
Objective¶
The combined pollution generated consists of emissions from both cars and buses. The goal is to reduce the overall pollution produced as much as possible.
Formulation c (invalid)¶
See also
This formulation is sourced from EquivaFormulation (instance id: 183, variation id: d).
Note
Substitute integer variables with base-10 representations.
This formulation is marked invalid because it is only a reformulation at the instance-level, not the formulation-level.
Source represented bus variables with a single digit; we extended to a 2-digit substitution to match the car variables.
Parameters¶
Name |
Description |
Type |
Shape |
|---|---|---|---|
|
The lowest quantity of staff that must be transported |
continuous |
scalar |
|
The emissions generated by a vehicle |
continuous |
scalar |
|
The capacity of individuals that a vehicle can accommodate |
integer |
scalar |
|
The capacity of employees that a bus can accommodate. |
integer |
scalar |
|
The emissions generated by a bus. |
continuous |
scalar |
|
The highest possible quantity of buses that can be employed |
continuous |
scalar |
Variables¶
Name |
Description |
Type |
Shape / Indices |
|---|---|---|---|
|
Digit 0 of the The quantity of vehicles utilized for travel purposes. |
integer |
scalar |
|
Digit 1 of the The quantity of vehicles utilized for travel purposes. |
integer |
scalar |
|
Digit 0 of the The quantity of buses utilized for transportation |
integer |
scalar |
|
Digit 1 of the The quantity of buses utilized for transportation |
integer |
scalar |
Assumptions¶
Description |
Formulation |
Implicit |
|---|---|---|
The lowest quantity of staff that must be transported must be non-negative. |
\(J \geq 0\) |
yes |
The emissions generated by a vehicle must be non-negative. |
\(M \geq 0\) |
yes |
The capacity of individuals that a vehicle can accommodate must be non-negative. |
\(K \geq 0\) |
yes |
The capacity of employees that a bus can accommodate must be non-negative. |
\(D \geq 0\) |
yes |
The emissions generated by a bus must be non-negative. |
\(O \geq 0\) |
yes |
The highest possible quantity of buses that can be employed must be non-negative. |
\(S \geq 0\) |
yes |
Constraints¶
The maximum number of buses that can be utilized is S.
\[ S \geq (h_0 \cdot 10^0 + h_1 \cdot 10^1) \]A minimum of J employees need to be transported.
\[ J \leq (m_0 \cdot 10^0 + m_1 \cdot 10^1) \cdot K + (h_0 \cdot 10^0 + h_1 \cdot 10^1) \cdot D \]Digit 0 of car count is non-negative. (implicit)
\[ m_0 \geq 0 \]Digit 1 of car count is non-negative. (implicit)
\[ m_1 \geq 0 \]Digit 0 of bus count is non-negative. (implicit)
\[ h_0 \geq 0 \]Digit 1 of bus count is non-negative. (implicit)
\[ h_1 \geq 0 \]Digit 0 of car count is at most 9. (implicit)
\[ m_0 \leq 9 \]Digit 1 of car count is at most 9. (implicit)
\[ m_1 \leq 9 \]Digit 0 of bus count is at most 9. (implicit)
\[ h_0 \leq 9 \]Digit 1 of bus count is at most 9. (implicit)
\[ h_1 \leq 9 \]
Objective¶
The combined pollution generated consists of emissions from both cars and buses. The goal is to reduce the overall pollution produced as much as possible.
Formulation d (valid)¶
See also
This formulation is sourced from EquivaFormulation (instance id: 183, variation id: f).
Note
Substitute the objective function with a new variable and linking constraint.
Parameters¶
Name |
Description |
Type |
Shape |
|---|---|---|---|
|
The lowest quantity of staff that must be transported |
continuous |
scalar |
|
The emissions generated by a vehicle |
continuous |
scalar |
|
The capacity of individuals that a vehicle can accommodate |
integer |
scalar |
|
The capacity of employees that a bus can accommodate. |
integer |
scalar |
|
The emissions generated by a bus. |
continuous |
scalar |
|
The highest possible quantity of buses that can be employed |
continuous |
scalar |
Variables¶
Name |
Description |
Type |
Shape / Indices |
|---|---|---|---|
|
The quantity of buses utilized for transportation |
integer |
scalar |
|
The quantity of vehicles utilized for travel purposes. |
integer |
scalar |
|
New variable representing the objective function |
continuous |
scalar |
Assumptions¶
Description |
Formulation |
Implicit |
|---|---|---|
The lowest quantity of staff that must be transported must be non-negative. |
\(J \geq 0\) |
yes |
The emissions generated by a vehicle must be non-negative. |
\(M \geq 0\) |
yes |
The capacity of individuals that a vehicle can accommodate must be non-negative. |
\(K \geq 0\) |
yes |
The capacity of employees that a bus can accommodate must be non-negative. |
\(D \geq 0\) |
yes |
The emissions generated by a bus must be non-negative. |
\(O \geq 0\) |
yes |
The highest possible quantity of buses that can be employed must be non-negative. |
\(S \geq 0\) |
yes |
Constraints¶
Constraint defining zed in terms of original variables.
\[ zed = m * M + h * O \]The maximum number of buses that can be utilized is S.
\[ S \geq h \]A minimum of J employees need to be transported.
\[ J \leq m \cdot K + h \cdot D \]Number of vehicles used is non-negative. (implicit)
\[ m \geq 0 \]Number of buses used is non-negative. (implicit)
\[ h \geq 0 \]
Objective¶
Minimize the new variable zed.
Formulation e (valid)¶
See also
This formulation is sourced from EquivaFormulation (instance id: 183, variation id: g).
Note
Introduce slack variables to convert inequality constraints into equality constraints.
The \(S\) bus constraint upper bound was absent from the source; we add an explicit constraint with slack variable.
Parameters¶
Name |
Description |
Type |
Shape |
|---|---|---|---|
|
The lowest quantity of staff that must be transported |
continuous |
scalar |
|
The emissions generated by a vehicle |
continuous |
scalar |
|
The capacity of individuals that a vehicle can accommodate |
integer |
scalar |
|
The capacity of employees that a bus can accommodate. |
integer |
scalar |
|
The emissions generated by a bus. |
continuous |
scalar |
|
The highest possible quantity of buses that can be employed |
continuous |
scalar |
Variables¶
Name |
Description |
Type |
Shape / Indices |
|---|---|---|---|
|
The quantity of buses utilized for transportation |
integer |
scalar |
|
The quantity of vehicles utilized for travel purposes. |
integer |
scalar |
|
Slack variable for constraint: A minimum of J employees need to be transported. |
continuous |
scalar |
|
Slack variable for constraint: The maximum number of buses that can be utilized is S. |
continuous |
scalar |
Assumptions¶
Description |
Formulation |
Implicit |
|---|---|---|
The lowest quantity of staff that must be transported must be non-negative. |
\(J \geq 0\) |
yes |
The emissions generated by a vehicle must be non-negative. |
\(M \geq 0\) |
yes |
The capacity of individuals that a vehicle can accommodate must be non-negative. |
\(K \geq 0\) |
yes |
The capacity of employees that a bus can accommodate must be non-negative. |
\(D \geq 0\) |
yes |
The emissions generated by a bus must be non-negative. |
\(O \geq 0\) |
yes |
The highest possible quantity of buses that can be employed must be non-negative. |
\(S \geq 0\) |
yes |
Constraints¶
A minimum of J employees need to be transported. (Modified to include slack variable slack_0)
\[ m \cdot K + h \cdot D - slack_0 = J \]The maximum number of buses that can be utilized is S. (Modified to include slack variable slack_1)
\[ h + slack_1 = S \]Number of vehicles used is non-negative. (implicit)
\[ m \geq 0 \]Number of buses used is non-negative. (implicit)
\[ h \geq 0 \]Slack variable for transport constraint is non-negative. (implicit)
\[ slack_0 \geq 0 \]Slack variable for bus constraint is non-negative. (implicit)
\[ slack_1 \geq 0 \]
Objective¶
The combined pollution generated consists of emissions from both cars and buses. The goal is to reduce the overall pollution produced as much as possible.
Formulation f (valid)¶
See also
This formulation is sourced from EquivaFormulation (instance id: 183, variation id: h).
Note
Splits variables.
Parameters¶
Name |
Description |
Type |
Shape |
|---|---|---|---|
|
The lowest quantity of staff that must be transported |
continuous |
scalar |
|
The emissions generated by a vehicle |
continuous |
scalar |
|
The capacity of individuals that a vehicle can accommodate |
integer |
scalar |
|
The capacity of employees that a bus can accommodate. |
integer |
scalar |
|
The emissions generated by a bus. |
continuous |
scalar |
|
The highest possible quantity of buses that can be employed |
continuous |
scalar |
Variables¶
Name |
Description |
Type |
Shape / Indices |
|---|---|---|---|
|
Part 1 of variable h: The quantity of buses utilized for transportation |
integer |
scalar |
|
Part 2 of variable h: The quantity of buses utilized for transportation |
integer |
scalar |
|
Part 1 of variable m: The quantity of vehicles utilized for travel purposes. |
integer |
scalar |
|
Part 2 of variable m: The quantity of vehicles utilized for travel purposes. |
integer |
scalar |
Assumptions¶
Description |
Formulation |
Implicit |
|---|---|---|
The lowest quantity of staff that must be transported must be non-negative. |
\(J \geq 0\) |
yes |
The emissions generated by a vehicle must be non-negative. |
\(M \geq 0\) |
yes |
The capacity of individuals that a vehicle can accommodate must be non-negative. |
\(K \geq 0\) |
yes |
The capacity of employees that a bus can accommodate must be non-negative. |
\(D \geq 0\) |
yes |
The emissions generated by a bus must be non-negative. |
\(O \geq 0\) |
yes |
The highest possible quantity of buses that can be employed must be non-negative. |
\(S \geq 0\) |
yes |
Constraints¶
The maximum number of buses that can be utilized is S.
\[ S \geq h1 + h2 \]A minimum of J employees need to be transported.
\[ J \leq (m1_{index} + m2_{index})\cdot K + (h1_{index} + h2_{index})\cdot D \]Part 1 of car count is non-negative. (implicit)
\[ m1 \geq 0 \]Part 2 of car count is non-negative. (implicit)
\[ m2 \geq 0 \]Part 1 of bus count is non-negative. (implicit)
\[ h1 \geq 0 \]Part 2 of bus count is non-negative. (implicit)
\[ h2 \geq 0 \]
Objective¶
The combined pollution generated consists of emissions from both cars and buses. The goal is to reduce the overall pollution produced as much as possible.
Formulation g (valid)¶
See also
This formulation is sourced from EquivaFormulation (instance id: 183, variation id: i).
Note
Re-scale the objective function.
Source was missing objective re-scaling; applied arbitrary scaling factor of 2.
Parameters¶
Name |
Description |
Type |
Shape |
|---|---|---|---|
|
The lowest quantity of staff that must be transported |
continuous |
scalar |
|
The emissions generated by a vehicle |
continuous |
scalar |
|
The capacity of individuals that a vehicle can accommodate |
integer |
scalar |
|
The capacity of employees that a bus can accommodate. |
integer |
scalar |
|
The emissions generated by a bus. |
continuous |
scalar |
|
The highest possible quantity of buses that can be employed |
continuous |
scalar |
Variables¶
Name |
Description |
Type |
Shape / Indices |
|---|---|---|---|
|
The quantity of buses utilized for transportation |
integer |
scalar |
|
The quantity of vehicles utilized for travel purposes. |
integer |
scalar |
Assumptions¶
Description |
Formulation |
Implicit |
|---|---|---|
The lowest quantity of staff that must be transported must be non-negative. |
\(J \geq 0\) |
yes |
The emissions generated by a vehicle must be non-negative. |
\(M \geq 0\) |
yes |
The capacity of individuals that a vehicle can accommodate must be non-negative. |
\(K \geq 0\) |
yes |
The capacity of employees that a bus can accommodate must be non-negative. |
\(D \geq 0\) |
yes |
The emissions generated by a bus must be non-negative. |
\(O \geq 0\) |
yes |
The highest possible quantity of buses that can be employed must be non-negative. |
\(S \geq 0\) |
yes |
Constraints¶
The maximum number of buses that can be utilized is S.
\[ S \geq h \]A minimum of J employees need to be transported.
\[ J \leq m \cdot K + h \cdot D \]Number of vehicles used is non-negative. (implicit)
\[ m \geq 0 \]Number of buses used is non-negative. (implicit)
\[ h \geq 0 \]
Objective¶
The combined pollution generated consists of emissions from both cars and buses, scaled by a factor of 2. The goal is to reduce the overall pollution produced as much as possible.
Formulation h (invalid)¶
See also
This formulation is sourced from EquivaFormulation (instance id: 183, variation id: j).
Note
Random formulation unrelated to the original problem.
Parameters¶
Name |
Description |
Type |
Shape |
|---|---|---|---|
|
Duration of each trip taken by a runner (in hours) |
continuous |
scalar |
|
The highest number of hours available in the village for deliveries. |
continuous |
scalar |
|
The quantity of bags that a runner is permitted to transport during each journey. |
continuous |
scalar |
|
The duration of time a canoeist spends on each trip (in hours) |
continuous |
scalar |
|
The quantity of bags that a person in a canoe can transport on every journey |
continuous |
scalar |
|
The minimum amount of athletes required for participation. |
continuous |
scalar |
|
The highest proportion of all deliveries that can be transported via canoe. |
continuous |
scalar |
Variables¶
Name |
Description |
Type |
Shape / Indices |
|---|---|---|---|
|
The quantity of individuals employed for transporting goods |
continuous |
scalar |
|
Quantity of journeys taken by individuals using canoes |
continuous |
scalar |
|
Quantity of journeys completed by individuals who run |
continuous |
scalar |
Assumptions¶
Description |
Formulation |
Implicit |
|---|---|---|
The duration of each trip taken by a runner (in hours) must be non-negative. |
\(U \geq 0\) |
yes |
The highest number of hours available in the village for deliveries must be non-negative. |
\(C \geq 0\) |
yes |
The quantity of bags that a runner is permitted to transport during each journey must be non-negative. |
\(V \geq 0\) |
yes |
The duration of time a canoeist spends on each trip (in hours) must be non-negative. |
\(N \geq 0\) |
yes |
The quantity of bags that a person in a canoe can transport on every journey must be non-negative. |
\(Z \geq 0\) |
yes |
The minimum amount of athletes required for participation must be non-negative. |
\(E \geq 0\) |
yes |
The highest proportion of all deliveries that can be transported via canoe must be non-negative. |
\(P \geq 0\) |
yes |
Constraints¶
Canoeers are limited to delivering only a portion, P, of the total mail that is to be delivered.
\[ P \times \left( p \times Z + a \times V \right) \geq p \times Z \]The combined time devoted to deliveries by both runners and individuals using canoes must not surpass the limit of C hours.
\[ C \geq U \times a + N \times p \]A minimum of E runners are required to carry out the deliveries.
\[ E \leq e \]Number of runners is non-negative. (implicit)
\[ e \geq 0 \]Number of canoe trips is non-negative. (implicit)
\[ p \geq 0 \]Number of runner trips is non-negative. (implicit)
\[ a \geq 0 \]
Objective¶
Maximize the overall volume of mail transported by runners and canoeists while abiding by the specified time, capacity, and usage limitations.
Formulation i (invalid)¶
See also
This formulation is sourced from EquivaFormulation (instance id: 183, variation id: k).
Note
Random formulation unrelated to the original problem, with the same optimal objective value as the original problem.
Parameters¶
Name |
Description |
Type |
Shape |
|---|---|---|---|
|
Duration of each trip taken by a runner (in hours) |
continuous |
scalar |
|
The highest number of hours available in the village for deliveries. |
continuous |
scalar |
|
The quantity of bags that a runner is permitted to transport during each journey. |
continuous |
scalar |
|
The duration of time a canoeist spends on each trip (in hours) |
continuous |
scalar |
|
The quantity of bags that a person in a canoe can transport on every journey |
continuous |
scalar |
|
The minimum amount of athletes required for participation. |
continuous |
scalar |
|
The highest proportion of all deliveries that can be transported via canoe. |
continuous |
scalar |
Variables¶
Name |
Description |
Type |
Shape / Indices |
|---|---|---|---|
|
The quantity of individuals employed for transporting goods |
continuous |
scalar |
|
Quantity of journeys taken by individuals using canoes |
continuous |
scalar |
|
Quantity of journeys completed by individuals who run |
continuous |
scalar |
Assumptions¶
Description |
Formulation |
Implicit |
|---|---|---|
The duration of each trip taken by a runner (in hours) must be non-negative. |
\(U \geq 0\) |
yes |
The highest number of hours available in the village for deliveries must be non-negative. |
\(C \geq 0\) |
yes |
The quantity of bags that a runner is permitted to transport during each journey must be non-negative. |
\(V \geq 0\) |
yes |
The duration of time a canoeist spends on each trip (in hours) must be non-negative. |
\(N \geq 0\) |
yes |
The quantity of bags that a person in a canoe can transport on every journey must be non-negative. |
\(Z \geq 0\) |
yes |
The minimum amount of athletes required for participation must be non-negative. |
\(E \geq 0\) |
yes |
The highest proportion of all deliveries that can be transported via canoe must be non-negative. |
\(P \geq 0\) |
yes |
Constraints¶
Canoeers are limited to delivering only a portion, P, of the total mail that is to be delivered.
\[ P \times \left( p \times Z + a \times V \right) \geq p \times Z \]The combined time devoted to deliveries by both runners and individuals using canoes must not surpass the limit of C hours.
\[ C \geq U \times a + N \times p \]A minimum of E runners are required to carry out the deliveries.
\[ E \leq e \]Number of runners is non-negative. (implicit)
\[ e \geq 0 \]Number of canoe trips is non-negative. (implicit)
\[ p \geq 0 \]Number of runner trips is non-negative. (implicit)
\[ a \geq 0 \]
Objective¶
The objective has been replaced by the solution value.
Formulation j (invalid)¶
See also
This formulation is sourced from EquivaFormulation (instance id: 183, variation id: l).
Note
Arbitrarily remove constraints from the original formulation.
Parameters¶
Name |
Description |
Type |
Shape |
|---|---|---|---|
|
The lowest quantity of staff that must be transported |
continuous |
scalar |
|
The emissions generated by a vehicle |
continuous |
scalar |
|
The capacity of individuals that a vehicle can accommodate |
integer |
scalar |
|
The capacity of employees that a bus can accommodate. |
integer |
scalar |
|
The emissions generated by a bus. |
continuous |
scalar |
|
The highest possible quantity of buses that can be employed |
continuous |
scalar |
Variables¶
Name |
Description |
Type |
Shape / Indices |
|---|---|---|---|
|
The quantity of buses utilized for transportation |
integer |
scalar |
|
The quantity of vehicles utilized for travel purposes. |
integer |
scalar |
Assumptions¶
Description |
Formulation |
Implicit |
|---|---|---|
The lowest quantity of staff that must be transported must be non-negative. |
\(J \geq 0\) |
yes |
The emissions generated by a vehicle must be non-negative. |
\(M \geq 0\) |
yes |
The capacity of individuals that a vehicle can accommodate must be non-negative. |
\(K \geq 0\) |
yes |
The capacity of employees that a bus can accommodate must be non-negative. |
\(D \geq 0\) |
yes |
The emissions generated by a bus must be non-negative. |
\(O \geq 0\) |
yes |
The highest possible quantity of buses that can be employed must be non-negative. |
\(S \geq 0\) |
yes |
Constraints¶
Number of vehicles used is non-negative. (implicit)
\[ m \geq 0 \]Number of buses used is non-negative. (implicit)
\[ h \geq 0 \]
Objective¶
The combined pollution generated consists of emissions from both cars and buses. The goal is to reduce the overall pollution produced as much as possible.