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, **kwds)[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
(n_rows: int = 500, n_cols: int = 1000, density: float = 0.05, max_coef: int = 100)[source]¶ -
__init__
(n_rows: int = 500, n_cols: int = 1000, density: float = 0.05, max_coef: int = 100)[source]¶ Constructor for the set cover generator.
The parameters passed in this constructor will be used when a user calls next() or iterates over the object.
- 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 in >= 1.
-
static
generate_instance
(n_rows: int, n_cols: int, density: float, max_coef: int, rng: numpy.random.mtrand.RandomState)[source]¶ Generates an instance of a combinatorial auction problem.
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:
E.Balas and A.Ho, Set covering algorithms using cutting planes, heuristics, and subgradient optimization: A computational study, Mathematical Programming, 12 (1980), 37-60.
- 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 in >= 1.
- Returns
an ecole model of a set cover instance.
- Return type
model
-
Combinatorial Auction¶
-
class
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.9, max_n_sub_bids: int = 5, additivity: float = 0.2, budget_factor: float = 1.5, resale_factor: float = 0.5, integers: float = False)[source]¶ -
__init__
(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.9, max_n_sub_bids: int = 5, additivity: float = 0.2, budget_factor: float = 1.5, resale_factor: float = 0.5, integers: float = False)[source]¶ Constructor for the CombinatorialAuctionGenerator generator.
The parameters passed in this constructor will be used when a user calls next() or iterates over the object.
- 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.
-
static
generate_instance
(n_items: int, n_bids: int, min_value: int, max_value: int, value_deviation: float, add_item_prob: float, max_n_sub_bids: int, additivity: float, budget_factor: float, resale_factor: float, integers: bool, logger: logging.Logger, rng: numpy.random.mtrand.RandomState)[source]¶ Generate an instance of a combinatorial auction problem.
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 Kevin Leyton-Brown, Mark Pearson, and Yoav Shoham. (2000). Towards a universal test suite for combinatorial auction algorithms. Proceedings of ACM Conference on Electronic Commerce (EC-00) 66-76. section 4.3., the ‘arbitrary’ scheme.
- 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.
rng – A random state used to sample random numbers.
- Returns
An ecole model of a combinatorial auction instance.
- Return type
model
-
Capacitated Facility Location¶
-
class
ecole.instance.
CapacitatedFacilityLocationGenerator
(n_customers: int = 100, n_facilities: int = 100, ratio: float = 5.0)[source]¶ -
__init__
(n_customers: int = 100, n_facilities: int = 100, ratio: float = 5.0)[source]¶ Constructor for the capacitated facility location generator.
The parameters passed in this constructor will be used when a user calls next() or iterates over the object.
- Parameters
n_customers – The number of customers.
n_facilities – The number of facilities.
ratio – The ratio of capacity/demand.
-
static
generate_instance
(n_customers: int, n_facilities: int, ratio: float, rng: numpy.random.mtrand.RandomState)[source]¶ Generates an instance of a capacitated facility location problem.
This method generates an instance of the capacitated facility location problem based on the specified parameters and returns it as an ecole model.
- The problem is generated following:
Cornuejols G, Sridharan R, Thizy J-M (1991) A Comparison of Heuristics and Relaxations for the Capacitated Plant Location Problem. European Journal of Operations Research 50:280-297.
- Parameters
n_customers – The number of customers.
n_facilities – The number of facilities.
ratio – The ratio of capacity/demand.
rng – A random number generator.
- Returns
an ecole model of a independent set instance.
- Return type
model
-
Independent Set¶
-
class
ecole.instance.
IndependentSetGenerator
(n_nodes: int = 100, edge_probability: float = 0.25, affinity: int = 5, graph_type: str = 'barabasi_albert')[source]¶ -
__init__
(n_nodes: int = 100, edge_probability: float = 0.25, affinity: int = 5, graph_type: str = 'barabasi_albert')[source]¶ Constructor for the independent set generator.
The parameters passed in this constructor will be used when a user calls next() or iterates over the object.
- Parameters
n_nodes – The number of nodes in the graph.
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”.
graph_type – The method used in which to generate graphs. One of “barabasi_albert” or “erdos_renyi”
-
static
generate_instance
(n_nodes: int, edge_probability: float, affinity: int, graph_type: str, rng: numpy.random.mtrand.RandomState)[source]¶ Generate an instance of an independent set problem.
This method generates an instance of the independent set problem based on the specified parameters and returns it as an ecole model.
- Parameters
n_nodes – The number of nodes in the graph.
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”.
graph_type – The method used in which to generate graphs. This parameter must be one of “barabasi_albert” or “erdos_renyi”.
rng – A random number generator.
- Returns
An ecole model of a independent set instance.
- Return type
model
-