Skip to content

Instance Generators

Protocol

InstanceGenerator

Bases: ABC

Abstract base class for instance generators. Subclasses must implement the generate_instance method.

Source code in gyozas/instances/instance_generator.py 
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
class InstanceGenerator(ABC):
    """
    Abstract base class for instance generators.
    Subclasses must implement the `generate_instance` method.
    """

    def __init__(self, rng: Generator | int | None = None) -> None:
        self.rng = sanitize_rng(rng)

    @abstractmethod
    def generate_instance(self, *args, **kwargs) -> Model:
        """
        Generate an instance with the given parameters.
        Must be implemented by subclasses.
        """
        pass

    def seed(self, seed) -> None:
        """Set the random seed for the generator."""
        self.rng = sanitize_rng(seed)

    def __iter__(self) -> "InstanceGenerator":
        """Return the iterator object itself."""
        return self

    @abstractmethod
    def __next__(self) -> Model:
        """Return the next instance."""
        pass

    def next(self) -> Model:
        """Alias for __next__."""
        return self.__next__()

generate_instance(*args, **kwargs) abstractmethod

Generate an instance with the given parameters. Must be implemented by subclasses.

Source code in gyozas/instances/instance_generator.py 
31
32
33
34
35
36
37
@abstractmethod
def generate_instance(self, *args, **kwargs) -> Model:
    """
    Generate an instance with the given parameters.
    Must be implemented by subclasses.
    """
    pass

seed(seed)

Set the random seed for the generator.

Source code in gyozas/instances/instance_generator.py 
39
40
41
def seed(self, seed) -> None:
    """Set the random seed for the generator."""
    self.rng = sanitize_rng(seed)

__iter__()

Return the iterator object itself.

Source code in gyozas/instances/instance_generator.py 
43
44
45
def __iter__(self) -> "InstanceGenerator":
    """Return the iterator object itself."""
    return self

__next__() abstractmethod

Return the next instance.

Source code in gyozas/instances/instance_generator.py 
47
48
49
50
@abstractmethod
def __next__(self) -> Model:
    """Return the next instance."""
    pass

next()

Alias for next.

Source code in gyozas/instances/instance_generator.py 
52
53
54
def next(self) -> Model:
    """Alias for __next__."""
    return self.__next__()

SetCoverGenerator

SetCoverGenerator

Bases: InstanceGenerator

Generator for random instances of the Set Cover problem.

Attributes: n_rows (int): Number of rows (elements to be covered). Default is 500. n_cols (int): Number of columns (sets available for covering). Default is 1000. density (float): Fraction of nonzero entries in the set cover matrix. Default is 0.05. max_coef (int): Maximum coefficient value for the set cover matrix. Default is 100. rng (np.random.Generator): Random number generator for reproducibility.

Source code in gyozas/instances/set_cover.py 
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
class SetCoverGenerator(InstanceGenerator):
    """Generator for random instances of the Set Cover problem.

    Attributes:
        n_rows (int): Number of rows (elements to be covered). Default is 500.
        n_cols (int): Number of columns (sets available for covering). Default is 1000.
        density (float): Fraction of nonzero entries in the set cover matrix. Default is 0.05.
        max_coef (int): Maximum coefficient value for the set cover matrix. Default is 100.
        rng (np.random.Generator): Random number generator for reproducibility.
    """

    def __init__(self, n_rows=500, n_cols=1000, density=0.05, max_coef=100, rng=None) -> None:
        super().__init__(rng=rng)
        self.n_rows = n_rows
        self.n_cols = n_cols
        self.density = density
        self.max_coef = max_coef

    def __next__(self) -> Model:
        return self.generate_instance(
            n_rows=self.n_rows, n_cols=self.n_cols, density=self.density, max_coef=self.max_coef, rng=self.rng
        )

    @staticmethod
    def _get_counts(indices, n_cols) -> NDArray[np.int64]:
        counts = np.zeros(n_cols, dtype=int)
        for idx in indices:
            counts[idx] += 1
        return counts

    def _get_choice_in_range(self, start_index, end_index, num_samples, rng=None) -> NDArray[np.int64]:
        if rng is None:
            rng = self.rng
        choices = np.arange(start_index, end_index)
        samples = rng.choice(choices, num_samples, replace=False)
        return samples

    @staticmethod
    def _convert_csc_to_csr(indices, indptr, n_rows, n_cols) -> tuple[NDArray[np.int64], NDArray[np.int64]]:
        indptr_csr = np.zeros(n_rows + 1, dtype=int)
        indices_csr = np.zeros_like(indices)
        for j in range(len(indices)):
            indptr_csr[indices[j] + 1] += 1
        indptr_csr = np.cumsum(indptr_csr)
        for col in range(n_cols):
            for jj in range(indptr[col], indptr[col + 1]):
                row = indices[jj]
                indices_csr[indptr_csr[row]] = col
                indptr_csr[row] += 1
        last = 0
        for row in range(n_rows + 1):
            last, indptr_csr[row] = indptr_csr[row], last
        return indptr_csr, indices_csr

    def generate_instance(self, n_rows=500, n_cols=1000, density=0.05, max_coef=100, rng=None) -> Model:
        rng = sanitize_rng(rng, default=self.rng)

        nnzrs = int(n_rows * n_cols * density)
        indices = np.zeros(nnzrs, dtype=int)

        # Force at least 2 rows per column
        first_indices = np.arange(0, 2 * n_cols) % n_cols
        indices[0 : 2 * n_cols] = first_indices

        # Assign remaining column indexes at random
        samples = self._get_choice_in_range(0, n_cols * (n_rows - 2), nnzrs - (2 * n_cols), rng=rng) % n_cols
        indices[2 * n_cols : nnzrs] = samples

        # Get counts of unique elements
        col_n_rows = self._get_counts(indices, n_cols)

        # Ensure at least 1 column per row
        perm = rng.permutation(n_rows)
        indices[0:n_rows] = perm

        i = 0
        indptr = np.zeros(n_cols + 1, dtype=int)
        indptr_idx = 1

        for _idx, n in enumerate(col_n_rows):
            if i + n <= n_rows:
                pass
            elif i >= n_rows:
                sampled_rows = self._get_choice_in_range(0, n_rows, n, rng=rng)
                indices[i : i + n] = sampled_rows
            elif i + n > n_rows:
                remaining_rows = np.setdiff1d(np.arange(n_rows), indices[i:n_rows])
                choices = rng.choice(remaining_rows, i + n - n_rows, replace=False)
                indices[n_rows : i + n] = choices
            i += n
            indptr[indptr_idx] = i
            indptr_idx += 1

        # Convert CSC indices/ptrs to CSR
        indptr_csr, indices_csr = self._convert_csc_to_csr(indices, indptr, n_rows, n_cols)

        # Sample coefficients
        c = rng.integers(1, max_coef + 1, size=n_cols)

        model = Model(problemName=f"SetCover-{n_rows}-{n_cols}")
        model.setMinimize()

        # Add variables
        b_vars = []
        for i in range(n_cols):
            b_vars.append(model.addVar(vtype="B", lb=0.0, ub=1.0, name=f"x_{i}", obj=c[i]))

        # Add constraints
        for i in range(n_rows):
            model.addCons(
                quicksum(b_vars[indices_csr[j]] for j in range(indptr_csr[i], indptr_csr[i + 1])) >= 1,
                name=f"cover_{i}",
            )

        return model

IndependentSetGenerator

IndependentSetGenerator

Bases: InstanceGenerator

Generator for random Maximum Independent Set problem instances.

Source code in gyozas/instances/independent_set.py 
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
class IndependentSetGenerator(InstanceGenerator):
    """Generator for random Maximum Independent Set problem instances."""

    def __init__(self, n_nodes=500, edge_probability=0.25, affinity=4, graph_type="barabasi_albert", rng=None) -> None:
        super().__init__(rng=rng)
        self.n_nodes = n_nodes
        self.edge_probability = edge_probability
        self.affinity = affinity
        self.graph_type = graph_type

    def __next__(self) -> Model:
        return self.generate_instance(
            n_nodes=self.n_nodes,
            edge_probability=self.edge_probability,
            affinity=self.affinity,
            graph_type=self.graph_type,
            rng=self.rng,
        )

    def generate_instance(
        self, n_nodes=500, edge_probability=0.25, affinity=4, graph_type="barabasi_albert", rng=None
    ) -> Model:
        rng = sanitize_rng(rng, default=self.rng)

        graph = self._make_graph(n_nodes, edge_probability, affinity, graph_type, rng)
        model = Model(problemName=f"IndependentSet-{n_nodes}")
        model.setMaximize()

        b_vars = [
            model.addVar(vtype="B", name=f"n_{i}", lb=0.0, ub=1.0, obj=1.0) for i in range(graph.number_of_nodes())
        ]
        clique_partition = list(nx.find_cliques_recursive(graph))

        # Clique constraints
        for clique in clique_partition:
            model.addCons(quicksum(b_vars[n] for n in clique) <= 1.0, name=f"clique_{clique}")

        # Edge constraints for edges not covered by cliques
        clique_index = CliqueIndex(clique_partition, graph.number_of_nodes())
        for n1, n2 in graph.edges():
            if not clique_index.are_in_same_clique(n1, n2):
                model.addCons(b_vars[n1] + b_vars[n2] <= 1.0, name=f"edge_{n1}_{n2}")

        return model

    def _make_graph(self, n_nodes=50, edge_probability=0.1, affinity=2, graph_type="erdos_renyi", rng=None) -> nx.Graph:
        if rng is None:
            rng = self.rng
        if graph_type.lower() == "erdos_renyi":
            return nx.erdos_renyi_graph(n_nodes, edge_probability, seed=rng)
        elif graph_type.lower() == "barabasi_albert":
            m = min(affinity, n_nodes - 1)
            return nx.barabasi_albert_graph(n_nodes, m, seed=rng)
        else:
            raise ValueError("Unknown graph type")

CombinatorialAuctionGenerator

CombinatorialAuctionGenerator

Bases: InstanceGenerator

Generator for random Combinatorial Auction winner determination problem instances.

Source code in gyozas/instances/combinatorial_auction.py 
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
class CombinatorialAuctionGenerator(InstanceGenerator):
    """Generator for random Combinatorial Auction winner determination problem instances."""

    def __init__(
        self,
        n_items: IntOrIntGenerator = 100,
        n_bids: IntOrIntGenerator = 500,
        min_value: IntOrIntGenerator = 1,
        max_value: IntOrIntGenerator = 100,
        max_n_sub_bids: IntOrIntGenerator = 5,
        integers=False,
        value_deviation=0.5,
        additivity=0.2,
        add_item_prob=0.65,
        budget_factor=1.5,
        resale_factor=0.5,
        warnings=False,
        rng=None,
    ) -> None:
        self.n_items = n_items
        self.n_bids = n_bids
        self.min_value = min_value
        self.max_value = max_value
        self.max_n_sub_bids = max_n_sub_bids
        self.integers = integers
        self.value_deviation = value_deviation
        self.additivity = additivity
        self.add_item_prob = add_item_prob
        self.budget_factor = budget_factor
        self.resale_factor = resale_factor
        self.warnings = warnings
        super().__init__(rng=rng)

    def __next__(self) -> Model:
        return self.generate_instance(
            n_items=self.n_items,
            n_bids=self.n_bids,
            min_value=self.min_value,
            max_value=self.max_value,
            max_n_sub_bids=self.max_n_sub_bids,
            integers=self.integers,
            value_deviation=self.value_deviation,
            additivity=self.additivity,
            add_item_prob=self.add_item_prob,
            budget_factor=self.budget_factor,
            resale_factor=self.resale_factor,
            warnings=self.warnings,
            rng=self.rng,
        )

    def generate_instance(
        self,
        n_items: IntOrIntGenerator = 10,
        n_bids: IntOrIntGenerator = 20,
        min_value: IntOrIntGenerator = 1,
        max_value: IntOrIntGenerator = 10,
        max_n_sub_bids: IntOrIntGenerator = 2,
        integers=True,
        value_deviation=0.1,
        additivity=0.0,
        add_item_prob=0.5,
        budget_factor=1.5,
        resale_factor=0.5,
        warnings=False,
        rng=None,
    ) -> Model:
        rng = sanitize_rng(rng, default=self.rng)
        n_items = _resolve_int(n_items, rng)
        n_bids = _resolve_int(n_bids, rng)
        min_value = _resolve_int(min_value, rng)
        max_value = _resolve_int(max_value, rng)
        max_n_sub_bids = _resolve_int(max_n_sub_bids, rng)
        if not (max_value >= min_value):
            raise ValueError("Parameters max_value and min_value must be defined such that: min_value <= max_value.")
        if not (0 <= add_item_prob <= 1):
            raise ValueError("Parameter add_item_prob must be in range [0,1].")
        logger = getLogger(__name__)
        if not warnings:
            logger.setLevel("ERROR")
        # Generate data
        rand_val = rng.uniform(0.0, 1.0, n_items)
        values = min_value + (max_value - min_value) * rand_val
        compats_rand = rng.uniform(0.0, 1.0, (n_items, n_items))
        compats = np.triu(compats_rand, 1)
        compats = compats + compats.T
        compats = compats / np.sum(compats, axis=1, keepdims=True)
        bids, n_dummy_items = _get_bids(
            values,
            compats,
            max_value,
            n_items,
            n_bids,
            max_n_sub_bids,
            integers,
            value_deviation,
            additivity,
            add_item_prob,
            budget_factor,
            resale_factor,
            logger,
            rng,
        )
        model = Model(f"CombinatorialAuction-{n_items}-{n_bids}")
        model.setMaximize()
        # Build bids_per_item mapping
        bids_per_item = [[] for _ in range(n_items + n_dummy_items)]
        for i, (bundle, _) in enumerate(bids):
            for item in bundle:
                bids_per_item[item].append(i)
        # Variables
        vars = []
        for i, (_, price) in enumerate(bids):
            v = model.addVar(vtype="BINARY", obj=price, name=f"x_{i}")
            vars.append(v)
        # Constraints
        for idx, item_bids in enumerate(bids_per_item):
            if item_bids:
                model.addCons(quicksum(vars[j] for j in item_bids) <= 1, name=f"c_{idx}")
        return model

CapacitatedFacilityLocationGenerator

CapacitatedFacilityLocationGenerator

Bases: InstanceGenerator

Generator for random Capacitated Facility Location problem instances.

Source code in gyozas/instances/capacitated_facility_location.py 
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
class CapacitatedFacilityLocationGenerator(InstanceGenerator):
    """Generator for random Capacitated Facility Location problem instances."""

    def __init__(
        self,
        n_customers=100,
        n_facilities=100,
        demand_interval=(5, 36),
        capacity_interval=(10, 161),
        fixed_cost_scale_interval=(100, 111),
        fixed_cost_cste_interval=(0, 91),
        ratio=5.0,
        continuous_assignment=True,
        rng=None,
    ) -> None:
        self.n_customers = n_customers
        self.n_facilities = n_facilities
        self.demand_interval = demand_interval
        self.capacity_interval = capacity_interval
        self.fixed_cost_scale_interval = fixed_cost_scale_interval
        self.fixed_cost_cste_interval = fixed_cost_cste_interval
        self.ratio = ratio
        self.continuous_assignment = continuous_assignment
        super().__init__(rng=rng)

    def __next__(self) -> Model:
        return self.generate_instance(
            n_customers=self.n_customers,
            n_facilities=self.n_facilities,
            demand_interval=self.demand_interval,
            capacity_interval=self.capacity_interval,
            fixed_cost_scale_interval=self.fixed_cost_scale_interval,
            fixed_cost_cste_interval=self.fixed_cost_cste_interval,
            ratio=self.ratio,
            continuous_assignment=self.continuous_assignment,
            rng=self.rng,
        )

    @staticmethod
    def _unit_transportation_costs(n_customers, n_facilities, rng) -> NDArray[np.float64]:
        scaling = 10.0
        customer_x = rng.random((n_customers, 1))
        customer_y = rng.random((n_customers, 1))
        facility_x = rng.random((1, n_facilities))
        facility_y = rng.random((1, n_facilities))
        costs = scaling * np.sqrt((customer_x - facility_x) ** 2 + (customer_y - facility_y) ** 2)
        assert costs.shape == (n_customers, n_facilities)
        return costs

    def generate_instance(
        self,
        n_customers=100,
        n_facilities=100,
        demand_interval=(5, 36),
        capacity_interval=(10, 161),
        fixed_cost_scale_interval=(100, 111),
        fixed_cost_cste_interval=(0, 91),
        ratio=5.0,
        continuous_assignment=True,
        rng=None,
    ) -> Model:
        rng = sanitize_rng(rng, default=self.rng)

        def randint(n, interval) -> NDArray[np.int64]:
            return rng.integers(interval[0], interval[1], size=n)

        # Generate data
        demands = randint(n_customers, demand_interval)
        capacities = randint(n_facilities, capacity_interval)
        fixed_costs = randint(n_facilities, fixed_cost_scale_interval) * np.sqrt(capacities) + randint(
            n_facilities, fixed_cost_cste_interval
        )
        transportation_costs = (
            CapacitatedFacilityLocationGenerator._unit_transportation_costs(n_customers, n_facilities, rng)
            * demands[:, np.newaxis]
        )

        # Scale capacities
        capacities = capacities * ratio * np.sum(demands) / np.sum(capacities)
        capacities = np.rint(capacities)

        # Build SCIP model
        model = Model(f"CapacitatedFacilityLocation-{n_customers}-{n_facilities}")

        # Facility opening variables
        facility_vars = [model.addVar(vtype="BINARY", obj=fixed_costs[j], name=f"f_{j}") for j in range(n_facilities)]

        # Assignment variables
        serving_vars = np.empty((n_customers, n_facilities), dtype=object)
        for i in range(n_customers):
            for j in range(n_facilities):
                vtype = "CONTINUOUS" if continuous_assignment else "BINARY"
                serving_vars[i, j] = model.addVar(
                    vtype=vtype,
                    lb=0.0,
                    ub=1.0,
                    obj=transportation_costs[i, j],
                    name=f"s_{i}_{j}",
                )

        # Demand constraints
        for i in range(n_customers):
            model.addCons(
                quicksum(serving_vars[i, j] for j in range(n_facilities)) == 1.0,
                name=f"d_{i}",
            )

        # Capacity constraints
        for j in range(n_facilities):
            model.addCons(
                quicksum(serving_vars[i, j] * demands[i] for i in range(n_customers))
                <= capacities[j] * facility_vars[j],
                name=f"c_{j}",
            )

        # Tightening constraints
        total_demand = np.sum(demands)
        model.addCons(
            quicksum(facility_vars[j] * capacities[j] for j in range(n_facilities)) >= total_demand,
            name="t_total_demand",
        )
        for i in range(n_customers):
            for j in range(n_facilities):
                model.addCons(
                    serving_vars[i, j] <= facility_vars[j],
                    name=f"t_{i}_{j}",
                )

        model.setMinimize()
        return model

MultipleKnapsackGenerator

MultipleKnapsackGenerator

Bases: InstanceGenerator

Generator for random instances of the Multiple Knapsack problem.

Items with a weight and a profit must be assigned to at most one of several capacitated knapsacks so as to maximize the total profit of packed items. Instances follow the schemes described in section 2.1 of

Fukunaga, Alex S. (2011). A branch-and-bound algorithm for hard multiple
knapsack problems. Annals of Operations Research, 184, 97-119.

Parameters:

Name Type Description Default
n_items int

Number of items. Default is 100.

 100
n_knapsacks int

Number of knapsacks. Default is 6.

 6
min_range int

Lower bound (inclusive) of the range used to sample item weights. Default is 10.

 10
max_range int

Upper bound (exclusive) of the range used to sample item weights. Default is 20. Must be strictly greater than min_range.

 20
scheme str

Weight/profit correlation scheme, one of "uncorrelated", "weakly correlated", "strongly correlated", or "subset-sum". Default is "weakly correlated".

 'weakly correlated'
rng Generator | int | None

Random number generator (or seed) for reproducibility.

 None
Source code in gyozas/instances/multiple_knapsack.py 
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
class MultipleKnapsackGenerator(InstanceGenerator):
    """Generator for random instances of the Multiple Knapsack problem.

    Items with a weight and a profit must be assigned to at most one of several
    capacitated knapsacks so as to maximize the total profit of packed items.
    Instances follow the schemes described in section 2.1 of

        Fukunaga, Alex S. (2011). A branch-and-bound algorithm for hard multiple
        knapsack problems. Annals of Operations Research, 184, 97-119.

    Parameters
    ----------
    n_items : int
        Number of items. Default is 100.
    n_knapsacks : int
        Number of knapsacks. Default is 6.
    min_range : int
        Lower bound (inclusive) of the range used to sample item weights. Default is 10.
    max_range : int
        Upper bound (exclusive) of the range used to sample item weights. Default is 20.
        Must be strictly greater than ``min_range``.
    scheme : str
        Weight/profit correlation scheme, one of ``"uncorrelated"``,
        ``"weakly correlated"``, ``"strongly correlated"``, or ``"subset-sum"``.
        Default is ``"weakly correlated"``.
    rng : numpy.random.Generator | int | None
        Random number generator (or seed) for reproducibility.
    """

    def __init__(
        self,
        n_items=100,
        n_knapsacks=6,
        min_range=10,
        max_range=20,
        scheme="weakly correlated",
        rng=None,
    ) -> None:
        super().__init__(rng=rng)
        self.n_items = n_items
        self.n_knapsacks = n_knapsacks
        self.min_range = min_range
        self.max_range = max_range
        self.scheme = scheme

    def __next__(self) -> Model:
        return self.generate_instance(
            n_items=self.n_items,
            n_knapsacks=self.n_knapsacks,
            min_range=self.min_range,
            max_range=self.max_range,
            scheme=self.scheme,
            rng=self.rng,
        )

    @staticmethod
    def _sample_profits(
        weights: NDArray[np.int64], min_range: int, max_range: int, scheme: str, rng: np.random.Generator
    ) -> NDArray:
        """Sample item profits correlated to ``weights`` according to ``scheme``."""
        n_items = len(weights)
        spread = max_range - min_range
        match scheme.lower():
            case "uncorrelated":
                return rng.integers(min_range, max_range, n_items)
            case "weakly correlated":
                low = np.maximum(weights - spread, 1)
                high = weights + spread
                return rng.integers(low, high)
            case "strongly correlated":
                return weights + spread / 10
            case "subset-sum":
                return weights
            case _:
                raise ValueError(
                    f"Unknown scheme {scheme!r}. Expected one of 'uncorrelated', "
                    "'weakly correlated', 'strongly correlated', 'subset-sum'."
                )

    @staticmethod
    def _sample_capacities(weights: NDArray[np.int64], n_knapsacks: int, rng: np.random.Generator) -> NDArray[np.int64]:
        """Sample knapsack capacities summing to roughly half the total item weight."""
        total_weight = int(weights.sum())
        capacities = np.zeros(n_knapsacks, dtype=int)
        capacities[:-1] = rng.integers(
            int(0.4 * total_weight // n_knapsacks),
            int(0.6 * total_weight // n_knapsacks),
            n_knapsacks - 1,
        )
        capacities[-1] = int(0.5 * total_weight) - capacities[:-1].sum()
        return capacities

    def generate_instance(
        self,
        n_items=100,
        n_knapsacks=6,
        min_range=10,
        max_range=20,
        scheme="weakly correlated",
        rng=None,
    ) -> Model:
        if min_range >= max_range:
            raise ValueError(f"min_range ({min_range}) must be strictly less than max_range ({max_range}).")
        rng = sanitize_rng(rng, default=self.rng)

        weights = rng.integers(min_range, max_range, n_items)
        profits = self._sample_profits(weights, min_range, max_range, scheme, rng)
        capacities = self._sample_capacities(weights, n_knapsacks, rng)

        model = Model(problemName=f"MultipleKnapsack-{n_items}-{n_knapsacks}")
        model.setMaximize()

        # x[i, k] = 1 if item i is placed in knapsack k.
        x = {
            (i, k): model.addVar(vtype="B", lb=0.0, ub=1.0, name=f"x_{i}_{k}", obj=profits[i])
            for i in range(n_items)
            for k in range(n_knapsacks)
        }

        # Each knapsack must respect its capacity.
        for k in range(n_knapsacks):
            model.addCons(
                quicksum(weights[i] * x[i, k] for i in range(n_items)) <= capacities[k],
                name=f"capacity_{k}",
            )

        # Each item is placed in at most one knapsack.
        for i in range(n_items):
            model.addCons(
                quicksum(x[i, k] for k in range(n_knapsacks)) <= 1,
                name=f"assign_{i}",
            )

        return model

FileGenerator

FileGenerator

Bases: InstanceGenerator

Instance generator that loads SCIP models from files on disk.

Parameters:

Name Type Description Default
directory Path | str

Path to the directory containing instance files.

 '.'
pattern str

Glob pattern to match files (e.g. "*.mps").

 '*'
recursive bool

If True, search subdirectories recursively.

 False
sampling_mode Literal['remove', 'replace']

"replace" to sample with replacement (default), "remove" to sample without.

 'replace'
rng Generator | int | None

Random seed or numpy Generator for reproducibility.

 None
Source code in gyozas/instances/files.py 
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
class FileGenerator(InstanceGenerator):
    """Instance generator that loads SCIP models from files on disk.

    Parameters
    ----------
    directory
        Path to the directory containing instance files.
    pattern
        Glob pattern to match files (e.g. ``"*.mps"``).
    recursive
        If True, search subdirectories recursively.
    sampling_mode
        ``"replace"`` to sample with replacement (default), ``"remove"`` to sample without.
    rng
        Random seed or numpy Generator for reproducibility.
    """

    def __init__(
        self,
        directory: Path | str = ".",
        pattern: str = "*",
        recursive: bool = False,
        sampling_mode: Literal["remove", "replace"] = "replace",
        rng: Generator | int | None = None,
    ) -> None:
        self.directory = directory
        self.pattern = pattern
        self.recursive = recursive
        self.sampling_mode = sampling_mode
        super().__init__(rng=rng)
        self.files = self._list_files()
        self._reset_file_list()

    def _list_files(self) -> list[Path]:
        files = []
        directory = Path(self.directory)
        if self.recursive:
            it = directory.rglob(self.pattern)
        else:
            it = directory.glob(self.pattern)
        for file in it:
            if file.is_file() or (file.is_symlink() and file.exists()):
                files.append(file)
        return files

    def __next__(self) -> Model:
        if self.done():
            raise StopIteration("No more files available.")
        if self.files_remaining == 0:
            self.files_remaining = len(self.files)

        idx = self.rng.integers(low=0, high=self.files_remaining)
        if self.sampling_mode.lower() == "replace":
            return self.generate_instance(self.files[idx])
        self.files_remaining -= 1
        self.files[idx], self.files[self.files_remaining] = self.files[self.files_remaining], self.files[idx]
        return self.generate_instance(self.files[self.files_remaining])

    def seed(self, seed) -> None:
        self._reset_file_list()
        super().seed(seed)

    def done(self) -> bool:
        no_files_at_all = len(self.files) == 0
        seen_all_files = self.files_remaining == 0 and self.sampling_mode.lower() == "remove"
        return no_files_at_all or seen_all_files

    def _reset_file_list(self) -> None:
        self.files.sort()
        self.files_remaining = len(self.files)

    def generate_instance(self, filepath) -> Model:
        """Load a SCIP model from a file.

        Parameters
        ----------
        filepath
            Path to the instance file.
        """
        model = Model()
        model.readProblem(filename=str(filepath))
        return model

generate_instance(filepath)

Load a SCIP model from a file.

Parameters:

Name Type Description Default
filepath

Path to the instance file.

 required
Source code in gyozas/instances/files.py 
81
82
83
84
85
86
87
88
89
90
91
def generate_instance(self, filepath) -> Model:
    """Load a SCIP model from a file.

    Parameters
    ----------
    filepath
        Path to the instance file.
    """
    model = Model()
    model.readProblem(filename=str(filepath))
    return model