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
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
@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
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
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
@abstractmethod
def __next__(self) -> Model:
    """Return the next instance."""
    pass

next()

Alias for next.

Source code in gyozas/instances/instance_generator.py
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
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
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
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)
        if isinstance(n_items, Callable):
            n_items = n_items(rng)  # ty: ignore[call-top-callable]
        if isinstance(n_bids, Callable):
            n_bids = n_bids(rng)  # ty: ignore[call-top-callable]
        if isinstance(min_value, Callable):
            min_value = min_value(rng)  # ty: ignore[call-top-callable]
        if isinstance(max_value, Callable):
            max_value = max_value(rng)  # ty: ignore[call-top-callable]
        if isinstance(max_n_sub_bids, Callable):
            max_n_sub_bids = max_n_sub_bids(rng)  # ty: ignore[call-top-callable]
        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
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

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