Instance Generator Module¶
This module helps with generation of instances for our problem.
-
instance_generator.generate_random_instance(n_instants: int, cost_dim: int, items_per_instant: int = 1) → Tuple[List[List[float]], List[List[List[float]]], float, float][source]¶ Generates random values, costs and capacity for a Packing Problem instance. Instances generated here may not respect guarantees constraints.
- Parameters
- n_instantsint
Number of instants to be generated.
- cost_dimint
Dimension of the cost vectors to be generated.
- items_per_instantint
Number of items that should be available in each instant.
- Returns
- valueslist of list of float
A list containing, for each instant, a list with that instant item’s values.
- costslist of list of list of float
A list containing, for each instant, a list with that instant item’s cost vectors.
- capfloat
A random problem capacity.
- efloat
The best theorical epsilon for the generated problem.
-
instance_generator.generate_valid_instance(target_delta: float, n_instants: int, cost_dim: int, items_per_instant: int = 1) → Tuple[List[List[float]], List[List[List[float]]], float, float][source]¶ Generates values for a problem instance that respect guarantees premises, thus, theoric guarantees should be valid (see Notes section below).
- Parameters
- target_deltafloat
Capacity will be set with the constraint that delta <= target_delta.
- n_instantsint
Number of instants to be generated.
- cost_dimint
Dimension of the cost vectors to be generated.
- items_per_instantint
Number of items that should be available in each instant.
- Returns
- valueslist of list of float
A list containing, for each instant, a list with that instant item’s values.
- costslist of list of list of float
A list containing, for each instant, a list with that instant item’s cost vectors.
- capfloat
A random problem capacity.
- efloat
The best theorical epsilon for the generated problem.
Notes
target_delta should be calibrated relative to n_instants. Setting a target_delta too low can cause the \(optimum\_value\_sum \geq \log d / \epsilon^2\) premise to be violated. Setting target_delta too high is not ideal since the algorithm chooses the items randomly in the first target_delta fraction of instants.
The only premise that is guaranteed here is that \(cap \geq \log d / \epsilon^2\). The \(optimum\_value\_sum \geq \log d / \epsilon^2\) premise is not asserted since it would require solving the instance to find optimum_value_sum, making this function slow. Setting a higher target_delta will increase the chance that this premise is valid.