p2 | Electricity Generation Experiment

See also

This problem is sourced from EquivaFormulation [3] (instance id: 74).

Note

• The source variable type is continuous; we correct the variable type to integer.

• The cutting plane (source variation 74_e) is excluded because it is instance-specific.

• Implicit non-negativity assumptions are added for every parameter.

• The problem is NP-hard: it is a multi-dimensional integer knapsack problem.

NP-hard: yes

Description

A scientist is conducting NumExperiments different experiments to produce electricity. Each experiment \(i\) produces ElectricityProduced[i] units of electricity and requires specific amounts of NumResources types of resources as defined by ResourceRequired[j][i]. The laboratory has ResourceAvailable[j] units of each resource available. The scientist aims to determine the number of each experiment to conduct in order to maximize the total electricity produced.

Formulations

Formulation a (valid)

See also

This formulation is sourced from EquivaFormulation [3] (instance id: 74, variation id: original).

Note

• Original formulation; no transformations.

Parameters

Name	Description	Type	Shape
NumExperiments	Number of experiment types	integer	scalar
NumResources	Number of resource types	integer	scalar
ResourceAvailable	Amount of resource \(j\) available	continuous	[NumResources]
ResourceRequired	Amount of resource \(j\) required for experiment \(i\)	continuous	[NumResources, NumExperiments]
ElectricityProduced	Amount of electricity produced by experiment \(i\)	continuous	[NumExperiments]

Variables

Name	Description	Type	Shape / Indices
ConductExperiment	The number of times each experiment is conducted	integer	[NumExperiments]

Assumptions

Description	Formulation	Implicit
The electricity produced by each experiment must be non-negative.	\(ElectricityProduced_i \geq 0 \quad \forall i\)	yes
The resource required by each experiment must be non-negative.	\(ResourceRequired_{j,i} \geq 0 \quad \forall j, i\)	yes
The amount of each resource available must be non-negative.	\(ResourceAvailable_j \geq 0 \quad \forall j\)	yes
The number of resource types must be positive.	\(NumResources \geq 1\)	yes
The number of experiment types must be positive.	\(NumExperiments \geq 1\)	yes

Constraints

• For each resource, the total amount required across all experiments does not exceed the available amount.

  \[ \sum_{i=1}^{NumExperiments} ResourceRequired_{j,i} \times ConductExperiment_i \leq ResourceAvailable_j \quad \forall j \in \{1, \ldots, NumResources\} \]

• The number of times each experiment is conducted must be non-negative. (implicit)

  \[ ConductExperiment_i \geq 0 \quad \forall i \]

Objective

Maximize the total electricity produced by conducting the experiments.

\[ Max \sum_{i=1}^{NumExperiments} ConductExperiment_{i} \times ElectricityProduced_{i} \]

Formulation b (valid)

See also

This formulation is sourced from EquivaFormulation [3] (instance id: 74, variation id: c).

Note

• Transformation of formulation a: Change the names of parameters and variables.

Parameters

Name	Description	Type	Shape
N	Number of resource types	integer	scalar
Y	The quantity of resource \(j\) that is accessible.	continuous	[N]
A	The quantity of electrical energy generated from trial \(i\)	continuous	[M]
I	Resource \(j\) quantity needed for experiment \(i\).	continuous	[N, M]
M	Number of experiment types	integer	scalar

Variables

Name	Description	Type	Shape / Indices
j	The frequency at which each experiment is performed.	integer	[M]

Assumptions

Description	Formulation	Implicit
The electrical energy generated from each trial must be non-negative.	\(A_i \geq 0 \quad \forall i\)	yes
The resource quantity needed for each experiment must be non-negative.	\(I_{j,i} \geq 0 \quad \forall j, i\)	yes
The quantity of each accessible resource must be non-negative.	\(Y_j \geq 0 \quad \forall j\)	yes
The number of resource types must be positive.	\(N \geq 1\)	yes
The number of experiment types must be positive.	\(M \geq 1\)	yes

Constraints

• For each resource, the total amount required across all experiments does not exceed the available amount.

  \[ \sum_{i=1}^{M} I_{k,i} \times j_i \leq Y_k \quad \forall k \in \{1, \ldots, N\} \]

• The frequency at which each experiment is performed must be non-negative. (implicit)

  \[ j_i \geq 0 \quad \forall i \]

Objective

Increase the overall electrical output by conducting the experiments to their full potential.

\[ Max \sum_{i=1}^{M} j_{i} \times A_{i} \]

Formulation c (invalid)

See also

This formulation is sourced from EquivaFormulation [3] (instance id: 74, variation id: d).

Note

• Transformation of formulation a: 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 variation was missing the substitution; we applied a 2-digit base-10 substitution.

Parameters

Name	Description	Type	Shape
N	Number of resource types	integer	scalar
Y	The quantity of resource \(j\) that is accessible.	continuous	[N]
A	The quantity of electrical energy generated from trial \(i\)	continuous	[M]
I	Resource \(j\) quantity needed for experiment \(i\).	continuous	[N, M]
M	Number of experiment types	integer	scalar

Variables

Name	Description	Type	Shape / Indices
j_0	Digit 0 of the frequency at which each experiment is performed.	integer	[M]
j_1	Digit 1 of the frequency at which each experiment is performed.	integer	[M]

Assumptions

Description	Formulation	Implicit
The electrical energy generated from each trial must be non-negative.	\(A_i \geq 0 \quad \forall i\)	yes
The quantity of each accessible resource must be non-negative.	\(Y_j \geq 0 \quad \forall j\)	yes
The resource quantity needed for each experiment must be non-negative.	\(I_{j,i} \geq 0 \quad \forall j, i\)	yes
The number of resource types must be positive.	\(N \geq 1\)	yes
The number of experiment types must be positive.	\(M \geq 1\)	yes

Constraints

• For each resource, the total amount required across all experiments does not exceed the available amount.

  \[ \sum_{i=1}^{M} I_{k,i} \times (j\_0_i \times 10^0 + j\_1_i \times 10^1) \leq Y_k \quad \forall k \in \{1, \ldots, N\} \]

• The upper bound on digit 0 of each experiment frequency (must be at most 9). (implicit)

  \[ j\_0_i \leq 9 \quad \forall i \]

• The upper bound on digit 1 of each experiment frequency (must be at most 9). (implicit)

  \[ j\_1_i \leq 9 \quad \forall i \]

• Digit 0 of each experiment frequency must be non-negative. (implicit)

  \[ j\_0_i \geq 0 \quad \forall i \]

• Digit 1 of each experiment frequency must be non-negative. (implicit)

  \[ j\_1_i \geq 0 \quad \forall i \]

Objective

Increase the overall electrical output by conducting the experiments to their full potential.

\[ Max \sum_{i=1}^{M} (j\_0_i \times 10^0 + j\_1_i \times 10^1) \times A_{i} \]

Formulation d (valid)

See also

This formulation is sourced from EquivaFormulation [3] (instance id: 74, variation id: f).

Note

• Transformation of formulation a: Substitute the objective function with a new variable and linking constraint.

Parameters

Name	Description	Type	Shape
N	Number of resource types	integer	scalar
Y	The quantity of resource \(j\) that is accessible.	continuous	[N]
A	The quantity of electrical energy generated from trial \(i\)	continuous	[M]
I	Resource \(j\) quantity needed for experiment \(i\).	continuous	[N, M]
M	Number of experiment types	integer	scalar

Variables

Name	Description	Type	Shape / Indices
j	The frequency at which each experiment is performed.	integer	[M]
zed	New variable representing the objective function	continuous	scalar

Assumptions

Description	Formulation	Implicit
The electrical energy generated from each trial must be non-negative.	\(A_i \geq 0 \quad \forall i\)	yes
The quantity of each accessible resource must be non-negative.	\(Y_j \geq 0 \quad \forall j\)	yes
The resource quantity needed for each experiment must be non-negative.	\(I_{j,i} \geq 0 \quad \forall j, i\)	yes
The number of resource types must be positive.	\(N \geq 1\)	yes
The number of experiment types must be positive.	\(M \geq 1\)	yes

Constraints

• Constraint defining \(\text{zed}\) in terms of original variables.

  \[ zed = \sum_{i=1}^{M} A_i \times j_i \]

• For each resource, the total amount required across all experiments does not exceed the available amount.

  \[ \sum_{i=1}^{M} I_{k,i} \times j_i \leq Y_k \quad \forall k \in \{1, \ldots, N\} \]

• The frequency at which each experiment is performed must be non-negative. (implicit)

  \[ j_i \geq 0 \quad \forall i \]

Objective

Maximize the new variable \(\text{zed}\).

\[ Maximize \ zed \]

Formulation e (valid)

See also

This formulation is sourced from EquivaFormulation [3] (instance id: 74, variation id: g).

Note

• Transformation of formulation a: Introduce slack variables to convert inequality constraints into equality constraints.

• Source variation was missing the slack variables; we introduced them.

Parameters

Name	Description	Type	Shape
N	Number of resource types	integer	scalar
Y	The quantity of resource \(j\) that is accessible.	continuous	[N]
A	The quantity of electrical energy generated from trial \(i\)	continuous	[M]
I	Resource \(j\) quantity needed for experiment \(i\).	continuous	[N, M]
M	Number of experiment types	integer	scalar

Variables

Name	Description	Type	Shape / Indices
j	The frequency at which each experiment is performed.	integer	[M]
s	Slack variable for constraint: For each resource, the total amount required across all experiments does not exceed the available amount.	continuous	[N]

Assumptions

Description	Formulation	Implicit
The electrical energy generated from each trial must be non-negative.	\(A_i \geq 0 \quad \forall i\)	yes
The quantity of each accessible resource must be non-negative.	\(Y_j \geq 0 \quad \forall j\)	yes
The resource quantity needed for each experiment must be non-negative.	\(I_{j,i} \geq 0 \quad \forall j, i\)	yes
The number of resource types must be positive.	\(N \geq 1\)	yes
The number of experiment types must be positive.	\(M \geq 1\)	yes

Constraints

• For each resource, the total amount required across all experiments plus slack equals the available amount.

  \[ \sum_{i=1}^{M} I_{k,i} \times j_i + s_k = Y_k \quad \forall k \in \{1, \ldots, N\} \]

• The frequency at which each experiment is performed must be non-negative. (implicit)

  \[ j_i \geq 0 \quad \forall i \]

• The slack variable for each resource constraint must be non-negative. (implicit)

  \[ s_k \geq 0 \quad \forall k \]

Objective

Increase the overall electrical output by conducting the experiments to their full potential.

\[ Max \sum_{i=1}^{M} j_{i} \times A_{i} \]

Formulation f (valid)

See also

This formulation is sourced from EquivaFormulation [3] (instance id: 74, variation id: h).

Note

• Transformation of formulation a: Splits variables.

Parameters

Name	Description	Type	Shape
N	Number of resource types	integer	scalar
Y	The quantity of resource \(j\) that is accessible.	continuous	[N]
A	The quantity of electrical energy generated from trial \(i\)	continuous	[M]
I	Resource \(j\) quantity needed for experiment \(i\).	continuous	[N, M]
M	Number of experiment types	integer	scalar

Variables

Name	Description	Type	Shape / Indices
j1	Part 1 of variable \(j\): The frequency at which each experiment is performed.	integer	[M]
j2	Part 2 of variable \(j\): The frequency at which each experiment is performed.	integer	[M]

Assumptions

Description	Formulation	Implicit
The electrical energy generated from each trial must be non-negative.	\(A_i \geq 0 \quad \forall i\)	yes
The quantity of each accessible resource must be non-negative.	\(Y_j \geq 0 \quad \forall j\)	yes
The resource quantity needed for each experiment must be non-negative.	\(I_{j,i} \geq 0 \quad \forall j, i\)	yes
The number of resource types must be positive.	\(N \geq 1\)	yes
The number of experiment types must be positive.	\(M \geq 1\)	yes

Constraints

• For each resource, the total amount required across all experiments does not exceed the available amount.

  \[ \sum_{i=1}^{M} I_{k,i} \times (j1_i + j2_i) \leq Y_k \quad \forall k \in \{1, \ldots, N\} \]

• Part 1 of each experiment frequency must be non-negative. (implicit)

  \[ j1_i \geq 0 \quad \forall i \]

• Part 2 of each experiment frequency must be non-negative. (implicit)

  \[ j2_i \geq 0 \quad \forall i \]

Objective

Increase the overall electrical output by conducting the experiments to their full potential.

\[ Max \sum_{i=1}^{M} (j1_{i} + j2_{i}) \times A_{i} \]

Formulation g (valid)

See also

This formulation is sourced from EquivaFormulation [3] (instance id: 74, variation id: i).

Note

• Transformation of formulation a: Re-scale the objective function.

• Source variation scaled the variables and objective by a factor of 1/10. This makes the reformulation invalid when the decision variables are integer. We replace the source transformation by simply scaling the objective by a factor of 2.

Parameters

Name	Description	Type	Shape
N	Number of resource types	integer	scalar
Y	The quantity of resource \(j\) that is accessible.	continuous	[N]
A	The quantity of electrical energy generated from trial \(i\)	continuous	[M]
I	Resource \(j\) quantity needed for experiment \(i\).	continuous	[N, M]
M	Number of experiment types	integer	scalar

Variables

Name	Description	Type	Shape / Indices
j	The frequency at which each experiment is performed.	integer	[M]

Assumptions

Description	Formulation	Implicit
The electrical energy generated from each trial must be non-negative.	\(A_i \geq 0 \quad \forall i\)	yes
The quantity of each accessible resource must be non-negative.	\(Y_j \geq 0 \quad \forall j\)	yes
The resource quantity needed for each experiment must be non-negative.	\(I_{j,i} \geq 0 \quad \forall j, i\)	yes
The number of resource types must be positive.	\(N \geq 1\)	yes
The number of experiment types must be positive.	\(M \geq 1\)	yes

Constraints

• For each resource, the total amount required across all experiments does not exceed the available amount.

  \[ \sum_{i=1}^{M} I_{k,i} \times j_i \leq Y_k \quad \forall k \in \{1, \ldots, N\} \]

• The scaled experiment count for each experiment must be non-negative. (implicit)

  \[ j_i \geq 0 \quad \forall i \]

Objective

Increase the overall electrical output by conducting the experiments to their full potential.

\[ Max 2 \times \sum_{i=1}^{M} j_{i} \times A_{i} \]

Formulation h (invalid)

See also

This formulation is sourced from EquivaFormulation [3] (instance id: 74, variation id: j).

Note

• Transformation of formulation a: Random formulation unrelated to the original problem.

Parameters

Name	Description	Type	Shape
F	Proportion of cat paw treats in the initial blend	continuous	scalar
S	Profit earned per each kilogram of the initial blend	continuous	scalar
R	Quantity of cat paw treats in stock	continuous	scalar
Z	Revenue generated for each kilogram of the alternate blend	continuous	scalar
W	Gold shark treats in stock by weight.	continuous	scalar
M	The proportion of feline paw treats in the second blend	continuous	scalar

Variables

Name	Description	Type	Shape / Indices
v	The amount of the second blend in kilograms	continuous	scalar
n	The amount of the initial blend in kilograms	continuous	scalar

Assumptions

Description	Formulation	Implicit
The proportion of cat paw treats in the initial blend must be non-negative.	\(F \geq 0\)	yes
The profit earned per each kilogram of the initial blend must be non-negative.	\(S \geq 0\)	yes
The quantity of cat paw treats in stock must be non-negative.	\(R \geq 0\)	yes
The revenue generated for each kilogram of the alternate blend must be non-negative.	\(Z \geq 0\)	yes
The gold shark treats in stock by weight must be non-negative.	\(W \geq 0\)	yes
The proportion of feline paw treats in the second blend must be non-negative.	\(M \geq 0\)	yes

Constraints

• The combined weight of cat paw treats in both blends should not surpass \(R\) kilograms, determined by adding together \(F\) multiplied by \(n\) and \(M\) multiplied by \(v\).

  \[ R \geq F \times n + M \times v \]

• The combined weight of gold shark snacks in the two mixes should not go over \(W\) kilograms, which is determined as the sum of (\((100 - F)\) multiplied by \(n\)) and (\((100 - M)\) multiplied by \(v\)).

  \[ W \geq \frac{(100 - F)}{100} \times n + \frac{(100 - M)}{100} \times v \]

• The amount of the initial blend produced must be non-negative. (implicit)

  \[ n \geq 0 \]

• The amount of the second blend produced must be non-negative. (implicit)

  \[ v \geq 0 \]

Objective

The goal is to increase the overall profit to the highest possible level, which is determined by the formula \((S \times n) + (Z \times v)\).

\[ Max \left( S \times n + Z \times v \right) \]

Formulation i (invalid)

See also

This formulation is sourced from EquivaFormulation [3] (instance id: 74, variation id: k).

Note

• Transformation of formulation a: Random formulation unrelated to the original problem, with the same optimal objective value as the original problem.

Parameters

Name	Description	Type	Shape
F	Proportion of cat paw treats in the initial blend	continuous	scalar
S	Profit earned per each kilogram of the initial blend	continuous	scalar
R	Quantity of cat paw treats in stock	continuous	scalar
Z	Revenue generated for each kilogram of the alternate blend	continuous	scalar
W	Gold shark treats in stock by weight.	continuous	scalar
M	The proportion of feline paw treats in the second blend	continuous	scalar

Variables

Name	Description	Type	Shape / Indices
v	The amount of the second blend in kilograms	continuous	scalar
n	The amount of the initial blend in kilograms	continuous	scalar

Assumptions

Description	Formulation	Implicit
The proportion of cat paw treats in the initial blend must be non-negative.	\(F \geq 0\)	yes
The profit earned per each kilogram of the initial blend must be non-negative.	\(S \geq 0\)	yes
The quantity of cat paw treats in stock must be non-negative.	\(R \geq 0\)	yes
The revenue generated for each kilogram of the alternate blend must be non-negative.	\(Z \geq 0\)	yes
The gold shark treats in stock by weight must be non-negative.	\(W \geq 0\)	yes
The proportion of feline paw treats in the second blend must be non-negative.	\(M \geq 0\)	yes

Constraints

• The combined weight of cat paw treats in both blends should not surpass \(R\) kilograms, determined by adding together \(F\) multiplied by \(n\) and \(M\) multiplied by \(v\).

  \[ R \geq F \times n + M \times v \]

• The combined weight of gold shark snacks in the two mixes should not go over \(W\) kilograms, which is determined as the sum of (\((100 - F)\) multiplied by \(n\)) and (\((100 - M)\) multiplied by \(v\)).

  \[ W \geq \frac{(100 - F)}{100} \times n + \frac{(100 - M)}{100} \times v \]

• The amount of the initial blend produced must be non-negative. (implicit)

  \[ n \geq 0 \]

• The amount of the second blend produced must be non-negative. (implicit)

  \[ v \geq 0 \]

Objective

The objective has been replaced by the solution value.

\[ Max(164) \]

Formulation j (invalid)

See also

This formulation is sourced from EquivaFormulation [3] (instance id: 74, variation id: l).

Note

• Transformation of formulation a: Arbitrarily remove constraints from the original formulation.

Parameters

Name	Description	Type	Shape
N	Quantity of different types of resources	integer	scalar
Y	The quantity of resource \(j\) that is accessible.	continuous	[N]
A	The quantity of electrical energy generated from trial \(i\)	continuous	[M]
I	Resource \(j\) quantity needed for experiment \(i\).	continuous	[N, M]
M	Amount of trials conducted	integer	scalar

Variables

Name	Description	Type	Shape / Indices
j	The frequency at which each experiment is performed.	integer	[M]

Assumptions

Description	Formulation	Implicit
The electrical energy generated from each trial must be non-negative.	\(A_i \geq 0 \quad \forall i\)	yes
The quantity of each accessible resource must be non-negative.	\(Y_j \geq 0 \quad \forall j\)	yes
The resource quantity needed for each experiment must be non-negative.	\(I_{j,i} \geq 0 \quad \forall j, i\)	yes

Constraints

• The frequency at which each experiment is performed must be non-negative. (implicit)

  \[ j_i \geq 0 \quad \forall i \]

Objective

Increase the overall electrical output by conducting the experiments to their full potential.

\[ Max \sum_{i=1}^{M} j_{i} \times A_{i} \]

Reformulations

Each entry below pairs two formulations of this problem, records whether the second is a reformulation of the first, and gives the parameter map carrying the first formulation’s parameters to the second’s.

a → b (valid)

Note

• Formulation b renames every parameter of formulation a.

Parameter map

Name	Definition in terms of a
N	\(N = NumResources\)
Y	\(Y = ResourceAvailable\)
A	\(A = ElectricityProduced\)
I	\(I = ResourceRequired\)
M	\(M = NumExperiments\)

a → c (invalid)

Note

• Formulation c renames every parameter of formulation a.

Parameter map

Name	Definition in terms of a
N	\(N = NumResources\)
Y	\(Y = ResourceAvailable\)
A	\(A = ElectricityProduced\)
I	\(I = ResourceRequired\)
M	\(M = NumExperiments\)

a → d (valid)

Note

• Formulation d renames every parameter of formulation a.

Parameter map

Name	Definition in terms of a
N	\(N = NumResources\)
Y	\(Y = ResourceAvailable\)
A	\(A = ElectricityProduced\)
I	\(I = ResourceRequired\)
M	\(M = NumExperiments\)

a → e (valid)

Note

• Formulation e renames every parameter of formulation a.

Parameter map

Name	Definition in terms of a
N	\(N = NumResources\)
Y	\(Y = ResourceAvailable\)
A	\(A = ElectricityProduced\)
I	\(I = ResourceRequired\)
M	\(M = NumExperiments\)

a → f (valid)

Note

• Formulation f renames every parameter of formulation a.

Parameter map

Name	Definition in terms of a
N	\(N = NumResources\)
Y	\(Y = ResourceAvailable\)
A	\(A = ElectricityProduced\)
I	\(I = ResourceRequired\)
M	\(M = NumExperiments\)

a → g (valid)

Note

• Formulation g renames every parameter of formulation a.

Parameter map

Name	Definition in terms of a
N	\(N = NumResources\)
Y	\(Y = ResourceAvailable\)
A	\(A = ElectricityProduced\)
I	\(I = ResourceRequired\)
M	\(M = NumExperiments\)

a → h (invalid)

Note

• Formulation h is unrelated to formulation a, so we arbitrarily assign fixed values to formulation h.

Parameter map

Name	Definition in terms of a
F	\(F = 20\)
S	\(S = 12\)
R	\(R = 20\)
Z	\(Z = 15\)
W	\(W = 50\)
M	\(M = 35\)

a → i (invalid)

Note

• Formulation i is unrelated to formulation a, so we arbitrarily assign fixed values to formulation i.

Parameter map

Name	Definition in terms of a
F	\(F = 20\)
S	\(S = 12\)
R	\(R = 20\)
Z	\(Z = 15\)
W	\(W = 50\)
M	\(M = 35\)

a → j (invalid)

Note

• Formulation j renames every parameter of formulation a.

Parameter map

Name	Definition in terms of a
N	\(N = NumResources\)
Y	\(Y = ResourceAvailable\)
A	\(A = ElectricityProduced\)
I	\(I = ResourceRequired\)
M	\(M = NumExperiments\)