Instance Generators¶
Protocol¶
The protocol of instance generators in Ecole. There are no constraints for user defined gnerators. The protocol is given for users to know what they can expect from Ecole generators.
- class ecole.typing.InstanceGenerator(*args: Any, random_engine: ecole.RandomEngine, **kwargs: Any)[source]¶
A class to generate generate and iteratate over random problem instance.
The class combines a
RandomEngine
with the static functiongenerate_instance()
to provide iterating capabilities.- __init__(*args: Any, random_engine: ecole.RandomEngine, **kwargs: Any) → None¶
Initialize self. See help(type(self)) for accurate signature.
- static generate_instance(*args: Any, random_engine: ecole.RandomEngine, **kwargs: Any) → ecole.scip.Model[source]¶
Generate a problem instance using the random engine for any source of randomness.
Listing¶
The list of instance generators is given below.
Set Cover¶
- class ecole.instance.SetCoverGenerator¶
- __init__(self: ecole.instance.SetCoverGenerator, n_rows: int = 500, n_cols: int = 1000, density: float = 0.05, max_coef: int = 100, random_engine: ecole.RandomEngine = None) → None¶
- property density¶
- static generate_instance(n_rows: int = 500, n_cols: int = 1000, density: float = 0.05, max_coef: int = 100, random_engine: ecole.RandomEngine) → ecole.scip.Model¶
Generate a set cover MILP problem instance.
Algorithm described in [Balas1980].
- Parameters
n_rows – The number of rows.
n_cols – The number of columns.
density – The density of the constraint matrix. The value must be in the range ]0,1].
max_coef – Maximum objective coefficient. The value must be greater than one.
random_engine – The random number generator used to peform all sampling.
References
- Balas1980
Egon Balas and Andrew Ho. “Set covering algorithms using cutting planes, heuristics, and subgradient optimization: A computational study”. Mathematical Programming, 12, pp. 37-60. 1980.
- property max_coef¶
- property n_cols¶
- property n_rows¶
- seed(self: ecole.instance.SetCoverGenerator, seed: int) → None¶
Combinatorial Auction¶
- class ecole.instance.CombinatorialAuctionGenerator¶
- __init__(self: ecole.instance.CombinatorialAuctionGenerator, n_items: int = 100, n_bids: int = 500, min_value: int = 1, max_value: int = 100, value_deviation: float = 0.5, add_item_prob: float = 0.7, max_n_sub_bids: int = 5, additivity: float = 0.2, budget_factor: float = 1.5, resale_factor: float = 0.5, integers: bool = False, warnings: bool = False, random_engine: ecole.RandomEngine = None) → None¶
- property add_item_prob¶
- property additivity¶
- property budget_factor¶
- static generate_instance(n_items: int = 100, n_bids: int = 500, min_value: int = 1, max_value: int = 100, value_deviation: float = 0.5, add_item_prob: float = 0.7, max_n_sub_bids: int = 5, additivity: float = 0.2, budget_factor: float = 1.5, resale_factor: float = 0.5, integers: bool = False, warnings: bool = False, random_engine: ecole.RandomEngine) → ecole.scip.Model¶
Generate a combinatorial auction MILP problem instance.
This method generates an instance of a combinatorial auction problem based on the specified parameters and returns it as an ecole model.
Algorithm described in [LeytonBrown2000].
- Parameters
n_items – The number of items.
n_bids – The number of bids.
min_value – The minimum resale value for an item.
max_value – The maximum resale value for an item.
value_deviation – The deviation allowed for each bidder’s private value of an item, relative from max_value.
add_item_prob – The probability of adding a new item to an existing bundle. This parameters must be in the range [0,1].
max_n_sub_bids – The maximum number of substitutable bids per bidder (+1 gives the maximum number of bids per bidder).
additivity – Additivity parameter for bundle prices. Note that additivity < 0 gives sub-additive bids, while additivity > 0 gives super-additive bids.
budget_factor – The budget factor for each bidder, relative to their initial bid’s price.
resale_factor – The resale factor for each bidder, relative to their initial bid’s resale value.
integers – Determines if the bid prices should be integral.
warnings – Determines if warnings should be printed when invalid bundles are skipped in instance generation.
random_engine – The random number generator used to peform all sampling.
References
- LeytonBrown2000
Kevin Leyton-Brown, Mark Pearson, and Yoav Shoham. “Towards a universal test suite for combinatorial auction algorithms”. Proceedings of ACM Conference on Electronic Commerce (EC01) pp. 66-76. Section 4.3., the ‘arbitrary’ scheme. 2000.
- property integers¶
- property max_n_sub_bids¶
- property max_value¶
- property min_value¶
- property n_bids¶
- property n_items¶
- property resale_factor¶
- seed(self: ecole.instance.CombinatorialAuctionGenerator, seed: int) → None¶
- property value_deviation¶
- property warnings¶
Capacitated Facility Location¶
- class ecole.instance.CapacitatedFacilityLocationGenerator¶
- __init__(self: ecole.instance.CapacitatedFacilityLocationGenerator, n_customers: int = 100, n_facilities: int = 100, continuous_assignment: bool = True, ratio: float = 5.0, demand_interval: Tuple[int, int] = (5, 36), capacity_interval: Tuple[int, int] = (10, 161), fixed_cost_cste_interval: Tuple[int, int] = (0, 91), fixed_cost_scale_interval: Tuple[int, int] = (100, 111), random_engine: ecole.RandomEngine = None) → None¶
- property capacity_interval¶
- property continuous_assignment¶
- property demand_interval¶
- property fixed_cost_cste_interval¶
- property fixed_cost_scale_interval¶
- static generate_instance(n_customers: int = 100, n_facilities: int = 100, continuous_assignment: bool = True, ratio: float = 5.0, demand_interval: Tuple[int, int] = (5, 36), capacity_interval: Tuple[int, int] = (10, 161), fixed_cost_cste_interval: Tuple[int, int] = (0, 91), fixed_cost_scale_interval: Tuple[int, int] = (100, 111), random_engine: ecole.RandomEngine) → ecole.scip.Model¶
Generate a capacitated facility location MILP problem instance.
The capacitated facility location assigns a number of customers to be served from a number of facilities. Not all facilities need to be opened. In fact, the problem is to minimized the sum of the fixed costs for each facilities and the sum of transportation costs for serving a given customer from a given facility. In a variant of the problem, the customers can be served from multiple facilities and the associated variables become [0,1] continuous.
The sampling algorithm is described in [Cornuejols1991], but uniform sampling as been replaced by integer uniform sampling.
- Parameters
n_customers – The number of customers.
n_facilities – The number of facilities.
continuous_assignment – Whether variable for assigning a customer to a facility are binary or [0,1] continuous.
ratio – After all sampling is performed, the capacities are scaled by ratio * sum(demands) / sum(capacities).
demand_interval – The customer demands are sampled independently as uniform integers in this interval [lower, upper[.
capacity_interval – The facility capacities are sampled independently as uniform integers in this interval [lower, upper[.
fixed_cost_cste_interval – The fixed costs are the sum of two terms. The first terms in the fixed costs for opening facilities are sampled independently as uniform integers in this interval [lower, upper[.
fixed_cost_scale_interval – The fixed costs are the sum of two terms. The second terms in the fixed costs for opening facilities are sampled independently as uniform integers in this interval [lower, upper[ multiplied by the square root of their capacity prior to scaling. This second term reflects the economies of scale.
random_engine – The random number generator used to peform all sampling.
References
- Cornuejols1991
Cornuejols G, Sridharan R, Thizy J-M. “A Comparison of Heuristics and Relaxations for the Capacitated Plant Location Problem”. European Journal of Operations Research 50, pp. 280-297. 1991.
- property n_customers¶
- property n_facilities¶
- property ratio¶
- seed(self: ecole.instance.CapacitatedFacilityLocationGenerator, seed: int) → None¶
Independent Set¶
- class ecole.instance.IndependentSetGenerator¶
- class GraphType¶
Members:
barabasi_albert
erdos_renyi
- __init__(*args, **kwargs)¶
Overloaded function.
__init__(self: ecole.core.instance.IndependentSetGenerator.GraphType, value: int) -> None
__init__(self: ecole.core.instance.IndependentSetGenerator.GraphType, arg0: str) -> None
- barabasi_albert = <GraphType.barabasi_albert: 0>¶
- erdos_renyi = <GraphType.erdos_renyi: 1>¶
- property name¶
- property value¶
- __init__(self: ecole.instance.IndependentSetGenerator, n_nodes: int = 500, graph_type: ecole.instance.IndependentSetGenerator.GraphType = <GraphType.barabasi_albert: 0>, edge_probability: float = 0.25, affinity: int = 4, random_engine: ecole.RandomEngine = None) → None¶
- property affinity¶
- barabasi_albert = <GraphType.barabasi_albert: 0>¶
- property edge_probability¶
- erdos_renyi = <GraphType.erdos_renyi: 1>¶
- static generate_instance(n_nodes: int = 500, graph_type: ecole.instance.IndependentSetGenerator.GraphType = <GraphType.barabasi_albert: 0>, edge_probability: float = 0.25, affinity: int = 4, random_engine: ecole.RandomEngine) → ecole.scip.Model¶
Generate an independent set MILP problem instance.
Given an undireted graph, the problem is to find a maximum subset of nodes such that no pair of nodes are connected. There are one variable per node in the underlying graph. Instead of adding one constraint per edge, a greedy algorithm is run to replace these inequalities when clique is found. The maximization problem is unwheighted, that is all objective coefficients are equal to one.
The problem are generated using the procedure from [Bergman2016], and the graphs are sampled following [Erdos1959] and [Barabasi1999].
- Parameters
n_nodes – The number of nodes in the graph, and therefore of variable.
graph_type – The method used in which to generate graphs. One of “barabasi_albert” or “erdos_renyi”
edge_probability – The probability of generating each edge. This parameter must be in the range [0, 1]. This parameter will only be used if graph_type == “erdos_renyi”.
affinity – The number of nodes each new node will be attached to, in the sampling scheme. This parameter must be an integer >= 1. This parameter will only be used if graph_type == “barabasi_albert”.
random_engine – The random number generator used to peform all sampling.
References
- Bergman2016
David Bergman, Andre A. Cire, Willem-Jan Van Hoeve, and John Hooker. “Decision diagrams for optimization”, Section 4.6.4. Springer International Publishing, 2016.
- Erdos1959
Paul Erdos and Alfréd Renyi. “On Random Graph” Publicationes Mathematicae, pp. 290-297, 1959.
- Barabasi1999
Albert-László Barabási and Réka Albert. “Emergence of scaling in random networks” Science vol. 286, num. 5439, pp. 509-512, 1999.
- property graph_type¶
- property n_nodes¶
- seed(self: ecole.instance.IndependentSetGenerator, seed: int) → None¶