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 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[source]

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

seed(int) → None[source]

Seed the random engine of the class.

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.

  1. __init__(self: ecole.core.instance.IndependentSetGenerator.GraphType, value: int) -> None

  2. __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