Contents

9. Benchmark Problems

9.1. miplearn.problems.binpack

class miplearn.problems.binpack.BinPackData(sizes: numpy.ndarray, capacity: int)

Data for the bin packing problem.

Parameters

  • sizes (numpy.ndarray) – Sizes of the items

  • capacity (int) – Capacity of the bin

class miplearn.problems.binpack.BinPackGenerator(n: scipy.stats._distn_infrastructure.rv_frozen, sizes: scipy.stats._distn_infrastructure.rv_frozen, capacity: scipy.stats._distn_infrastructure.rv_frozen, sizes_jitter: scipy.stats._distn_infrastructure.rv_frozen, capacity_jitter: scipy.stats._distn_infrastructure.rv_frozen, fix_items: bool)

Random instance generator for the bin packing problem.

If fix_items=False, the class samples the user-provided probability distributions n, sizes and capacity to decide, respectively, the number of items, the sizes of the items and capacity of the bin. All values are sampled independently.

If fix_items=True, the class creates a reference instance, using the method previously described, then generates additional instances by perturbing its item sizes and bin capacity. More specifically, the sizes of the items are set to s_i * gamma_i where s_i is the size of the i-th item in the reference instance and gamma_i is sampled from sizes_jitter. Similarly, the bin capacity is set to B * beta, where B is the reference bin capacity and beta is sampled from capacity_jitter. The number of items remains the same across all generated instances.

Parameters

  • n – Probability distribution for the number of items.

  • sizes – Probability distribution for the item sizes.

  • capacity – Probability distribution for the bin capacity.

  • sizes_jitter – Probability distribution for the item size randomization.

  • capacity_jitter – Probability distribution for the bin capacity.

  • fix_items – If True, generates a reference instance, then applies some perturbation to it. If False, generates completely different instances.

generate(n_samples: int) → List[miplearn.problems.binpack.BinPackData]

Generates random instances.

Parameters

n_samples – Number of samples to generate.

miplearn.problems.binpack.build_binpack_model(data: Union[str, miplearn.problems.binpack.BinPackData]) → miplearn.solvers.gurobi.GurobiModel

Converts bin packing problem data into a concrete Gurobipy model.

9.2. miplearn.problems.multiknapsack

class miplearn.problems.multiknapsack.MultiKnapsackData(prices: numpy.ndarray, capacities: numpy.ndarray, weights: numpy.ndarray)

Data for the multi-dimensional knapsack problem

Parameters

  • prices (numpy.ndarray) – Item prices.

  • capacities (numpy.ndarray) – Knapsack capacities.

  • weights (numpy.ndarray) – Matrix of item weights.

class miplearn.problems.multiknapsack.MultiKnapsackGenerator(n: scipy.stats._distn_infrastructure.rv_frozen = <scipy.stats._distn_infrastructure.rv_frozen object>, m: scipy.stats._distn_infrastructure.rv_frozen = <scipy.stats._distn_infrastructure.rv_frozen object>, w: scipy.stats._distn_infrastructure.rv_frozen = <scipy.stats._distn_infrastructure.rv_frozen object>, K: scipy.stats._distn_infrastructure.rv_frozen = <scipy.stats._distn_infrastructure.rv_frozen object>, u: scipy.stats._distn_infrastructure.rv_frozen = <scipy.stats._distn_infrastructure.rv_frozen object>, alpha: scipy.stats._distn_infrastructure.rv_frozen = <scipy.stats._distn_infrastructure.rv_frozen object>, fix_w: bool = False, w_jitter: scipy.stats._distn_infrastructure.rv_frozen = <scipy.stats._distn_infrastructure.rv_frozen object>, p_jitter: scipy.stats._distn_infrastructure.rv_frozen = <scipy.stats._distn_infrastructure.rv_frozen object>, round: bool = True)

Random instance generator for the multi-dimensional knapsack problem.

Instances have a random number of items (or variables) and a random number of knapsacks (or constraints), as specified by the provided probability distributions n and m, respectively. The weight of each item i on knapsack j is sampled independently from the provided distribution w. The capacity of knapsack j is set to alpha_j * sum(w[i,j] for i in range(n)), where alpha_j, the tightness ratio, is sampled from the provided probability distribution alpha.

To make the instances more challenging, the costs of the items are linearly correlated to their average weights. More specifically, the weight of each item i is set to sum(w[i,j]/m for j in range(m)) + K * u_i, where K, the correlation coefficient, and u_i, the correlation multiplier, are sampled from the provided probability distributions. Note that K is only sample once for the entire instance.

If fix_w=True, then weights[i,j] are kept the same in all generated instances. This also implies that n and m are kept fixed. Although the prices and capacities are derived from weights[i,j], as long as u and K are not constants, the generated instances will still not be completely identical.

If a probability distribution w_jitter is provided, then item weights will be set to w[i,j] * gamma[i,j] where gamma[i,j] is sampled from w_jitter. When combined with fix_w=True, this argument may be used to generate instances where the weight of each item is roughly the same, but not exactly identical, across all instances. The prices of the items and the capacities of the knapsacks will be calculated as above, but using these perturbed weights instead.

By default, all generated prices, weights and capacities are rounded to the nearest integer number. If round=False is provided, this rounding will be disabled.

Parameters

  • n (rv_discrete) – Probability distribution for the number of items (or variables).

  • m (rv_discrete) – Probability distribution for the number of knapsacks (or constraints).

  • w (rv_continuous) – Probability distribution for the item weights.

  • K (rv_continuous) – Probability distribution for the profit correlation coefficient.

  • u (rv_continuous) – Probability distribution for the profit multiplier.

  • alpha (rv_continuous) – Probability distribution for the tightness ratio.

  • fix_w (boolean) – If true, weights are kept the same (minus the noise from w_jitter) in all instances.

  • w_jitter (rv_continuous) – Probability distribution for random noise added to the weights.

  • round (boolean) – If true, all prices, weights and capacities are rounded to the nearest integer.

miplearn.problems.multiknapsack.build_multiknapsack_model(data: Union[str, miplearn.problems.multiknapsack.MultiKnapsackData]) → miplearn.solvers.gurobi.GurobiModel

Converts multi-knapsack problem data into a concrete Gurobipy model.

9.3. miplearn.problems.pmedian

class miplearn.problems.pmedian.PMedianData(distances: numpy.ndarray, demands: numpy.ndarray, p: int, capacities: numpy.ndarray)

Data for the capacitated p-median problem

Parameters

  • distances (numpy.ndarray) – Matrix of distances between customer i and facility j.

  • demands (numpy.ndarray) – Customer demands.

  • p (int) – Number of medians that need to be chosen.

  • capacities (numpy.ndarray) – Facility capacities.

class miplearn.problems.pmedian.PMedianGenerator(x: scipy.stats._distn_infrastructure.rv_frozen = <scipy.stats._distn_infrastructure.rv_frozen object>, y: scipy.stats._distn_infrastructure.rv_frozen = <scipy.stats._distn_infrastructure.rv_frozen object>, n: scipy.stats._distn_infrastructure.rv_frozen = <scipy.stats._distn_infrastructure.rv_frozen object>, p: scipy.stats._distn_infrastructure.rv_frozen = <scipy.stats._distn_infrastructure.rv_frozen object>, demands: scipy.stats._distn_infrastructure.rv_frozen = <scipy.stats._distn_infrastructure.rv_frozen object>, capacities: scipy.stats._distn_infrastructure.rv_frozen = <scipy.stats._distn_infrastructure.rv_frozen object>, distances_jitter: scipy.stats._distn_infrastructure.rv_frozen = <scipy.stats._distn_infrastructure.rv_frozen object>, demands_jitter: scipy.stats._distn_infrastructure.rv_frozen = <scipy.stats._distn_infrastructure.rv_frozen object>, capacities_jitter: scipy.stats._distn_infrastructure.rv_frozen = <scipy.stats._distn_infrastructure.rv_frozen object>, fixed: bool = True)

Random generator for the capacitated p-median problem.

This class first decides the number of customers and the parameter p by sampling the provided n and p distributions, respectively. Then, for each customer i, the class builds its geographical location (xi, yi) by sampling the provided x and y distributions. For each i, the demand for customer i and the capacity of facility i are decided by sampling the distributions demands and capacities, respectively. Finally, the costs w[i,j] are set to the Euclidean distance between the locations of customers i and j.

If fixed=True, then the number of customers, their locations, the parameter p, the demands and the capacities are only sampled from their respective distributions exactly once, to build a reference instance which is then perturbed. Specifically, for each perturbation, the distances, demands and capacities are multiplied by factors sampled from the distributions distances_jitter, demands_jitter and capacities_jitter, respectively. The result is a list of instances that have the same set of customers, but slightly different demands, capacities and distances.

Parameters

  • x – Probability distribution for the x-coordinate of the points.

  • y – Probability distribution for the y-coordinate of the points.

  • n – Probability distribution for the number of customer.

  • p – Probability distribution for the number of medians.

  • demands – Probability distribution for the customer demands.

  • capacities – Probability distribution for the facility capacities.

  • distances_jitter – Probability distribution for the random scaling factor applied to distances.

  • demands_jitter – Probability distribution for the random scaling factor applied to demands.

  • capacities_jitter – Probability distribution for the random scaling factor applied to capacities.

  • fixed – If True, then customer are kept the same across instances.

miplearn.problems.pmedian.build_pmedian_model(data: Union[str, miplearn.problems.pmedian.PMedianData]) → miplearn.solvers.gurobi.GurobiModel

Converts capacitated p-median data into a concrete Gurobipy model.

9.4. miplearn.problems.setcover

class miplearn.problems.setcover.SetCoverData(costs: numpy.ndarray, incidence_matrix: numpy.ndarray)

9.5. miplearn.problems.setpack

class miplearn.problems.setpack.SetPackData(costs: numpy.ndarray, incidence_matrix: numpy.ndarray)

9.6. miplearn.problems.stab

class miplearn.problems.stab.MaxWeightStableSetData(graph: networkx.classes.graph.Graph, weights: numpy.ndarray)
class miplearn.problems.stab.MaxWeightStableSetGenerator(w: scipy.stats._distn_infrastructure.rv_frozen = <scipy.stats._distn_infrastructure.rv_frozen object>, n: scipy.stats._distn_infrastructure.rv_frozen = <scipy.stats._distn_infrastructure.rv_frozen object>, p: scipy.stats._distn_infrastructure.rv_frozen = <scipy.stats._distn_infrastructure.rv_frozen object>, fix_graph: bool = True)

Random instance generator for the Maximum-Weight Stable Set Problem.

The generator has two modes of operation. When fix_graph=True is provided, one random Erdős-Rényi graph $G_{n,p}$ is generated in the constructor, where $n$ and $p$ are sampled from user-provided probability distributions n and p. To generate each instance, the generator independently samples each $w_v$ from the user-provided probability distribution w.

When fix_graph=False, a new random graph is generated for each instance; the remaining parameters are sampled in the same way.

9.7. miplearn.problems.tsp

class miplearn.problems.tsp.TravelingSalesmanData(n_cities: int, distances: numpy.ndarray)
class miplearn.problems.tsp.TravelingSalesmanGenerator(x: scipy.stats._distn_infrastructure.rv_frozen = <scipy.stats._distn_infrastructure.rv_frozen object>, y: scipy.stats._distn_infrastructure.rv_frozen = <scipy.stats._distn_infrastructure.rv_frozen object>, n: scipy.stats._distn_infrastructure.rv_frozen = <scipy.stats._distn_infrastructure.rv_frozen object>, gamma: scipy.stats._distn_infrastructure.rv_frozen = <scipy.stats._distn_infrastructure.rv_frozen object>, fix_cities: bool = True, round: bool = True)

Random generator for the Traveling Salesman Problem.

9.8. miplearn.problems.uc

class miplearn.problems.uc.UnitCommitmentData(demand: numpy.ndarray, min_power: numpy.ndarray, max_power: numpy.ndarray, min_uptime: numpy.ndarray, min_downtime: numpy.ndarray, cost_startup: numpy.ndarray, cost_prod: numpy.ndarray, cost_fixed: numpy.ndarray)
miplearn.problems.uc.build_uc_model(data: Union[str, miplearn.problems.uc.UnitCommitmentData]) → miplearn.solvers.gurobi.GurobiModel

Models the unit commitment problem according to equations (1)-(5) of:

Bendotti, P., Fouilhoux, P. & Rottner, C. The min-up/min-down unit commitment polytope. J Comb Optim 36, 1024-1058 (2018). https://doi.org/10.1007/s10878-018-0273-y

9.9. miplearn.problems.vertexcover

class miplearn.problems.vertexcover.MinWeightVertexCoverData(graph: networkx.classes.graph.Graph, weights: numpy.ndarray)
8. Learning Solver 10. Collectors & Extractors