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)

A class to generate generate and iteratate over random problem instance.

The class combines a RandomEngine with the static function generate_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

Generate a problem instance using the random engine for any source of randomness.

seed(int) → None

Seed the random engine of the class.

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)

__init__(n_rows: int = 500, n_cols: int = 1000, density: float = 0.05, max_coef: int = 100)

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)

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

seed(seed: int)

Seeds SetCoverGenerator.

This method sets the random seed of the SetCoverGenerator.

Parameters

seed – The seed in which to set the random number generator with.

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)

__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)

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)

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

seed(seed: int)

Seeds CombinatorialAuctionGenerator.

This method sets the random seed of the CombinatorialAuctionGenerator.

Parameters

seed – The seed in which to set the random number generator with.

Capacitated Facility Location

class ecole.instance.CapacitatedFacilityLocationGenerator(n_customers: int = 100, n_facilities: int = 100, ratio: float = 5.0)

__init__(n_customers: int = 100, n_facilities: int = 100, ratio: float = 5.0)

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)

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

seed(seed: int)

Seeds CapacitatedFacilityLocationGenerator.

This method sets the random seed of the CapacitatedFacilityLocationGenerator.

Parameters

seed – The seed in which to set the random number generator with.

Independent Set

class ecole.instance.IndependentSetGenerator(n_nodes: int = 100, edge_probability: float = 0.25, affinity: int = 5, graph_type: str = 'barabasi_albert')

__init__(n_nodes: int = 100, edge_probability: float = 0.25, affinity: int = 5, graph_type: str = 'barabasi_albert')

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)

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

seed(seed: int)

Seeds IndependentSetGenerator.

This method sets the random seed of the IndependentSetGenerator.

Parameters

seed – The seed in which to set the random number generator with.