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. 3760. 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 subadditive bids, while additivity > 0 gives superadditive 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 LeytonBrown, Mark Pearson, and Yoav Shoham. “Towards a universal test suite for combinatorial auction algorithms”. Proceedings of ACM Conference on Electronic Commerce (EC01) pp. 6676. 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 JM. “A Comparison of Heuristics and Relaxations for the Capacitated Plant Location Problem”. European Journal of Operations Research 50, pp. 280297. 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, WillemJan 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. 290297, 1959.
 Barabasi1999
AlbertLászló Barabási and Réka Albert. “Emergence of scaling in random networks” Science vol. 286, num. 5439, pp. 509512, 1999.

property
graph_type
¶

property
n_nodes
¶

seed
(self: ecole.instance.IndependentSetGenerator, seed: int) → None¶

class