Graph Problems

Facility Location Problem (FLP)

FLPEnv

FLPEnv(
    generator: FLPGenerator = None,
    generator_params: dict = {},
    check_solution=False,
    **kwargs
)

Bases: RL4COEnvBase

Facility Location Problem (FLP) environment At each step, the agent chooses a location. The reward is 0 unless enough number of locations are chosen. The reward is (-) the total distance of each location to its closest chosen location.

Observations

• the locations
• the number of locations to choose

Constraints

• the given number of locations must be chosen

Finish condition

• the given number of locations are chosen

Reward

• (minus) the total distance of each location to its closest chosen location

Parameters:

• generator (FLPGenerator, default: None ) –

  FLPGenerator instance as the data generator

• generator_params (dict, default: {} ) –

  parameters for the generator

Source code in rl4co/envs/graph/flp/env.py

def __init__(
    self,
    generator: FLPGenerator = None,
    generator_params: dict = {},
    check_solution=False,
    **kwargs,
):
    super().__init__(**kwargs)
    if generator is None:
        generator = FLPGenerator(**generator_params)
    self.generator = generator
    self.check_solution = check_solution
    self._make_spec(self.generator)

FLPGenerator

FLPGenerator(
    num_loc: int = 100,
    min_loc: float = 0.0,
    max_loc: float = 1.0,
    loc_distribution: Union[
        int, float, str, type, Callable
    ] = Uniform,
    to_choose: int = 10,
    **kwargs
)

Bases: Generator

Data generator for the Facility Location Problem (FLP).

Parameters:

• num_loc (int, default: 100 ) –

  number of locations in the FLP

• min_loc (float, default: 0.0 ) –

  minimum value for the location coordinates

• max_loc (float, default: 1.0 ) –

  maximum value for the location coordinates

• loc_distribution (Union[int, float, str, type, Callable], default: Uniform ) –

  distribution for the location coordinates

Returns:

• –

  A TensorDict with the following keys: locs [batch_size, num_loc, 2]: locations orig_distances [batch_size, num_loc, num_loc]: original distances between locations distances [batch_size, num_loc]: the current minimum distance rom each location to the chosen locations chosen [batch_size, num_loc]: indicators of chosen locations to_choose [batch_size, 1]: number of locations to choose in the FLP

Source code in rl4co/envs/graph/flp/generator.py

def __init__(
    self,
    num_loc: int = 100,
    min_loc: float = 0.0,
    max_loc: float = 1.0,
    loc_distribution: Union[int, float, str, type, Callable] = Uniform,
    to_choose: int = 10,
    **kwargs,
):
    self.num_loc = num_loc
    self.min_loc = min_loc
    self.max_loc = max_loc
    self.to_choose = to_choose

    # Location distribution
    if kwargs.get("loc_sampler", None) is not None:
        self.loc_sampler = kwargs["loc_sampler"]
    else:
        self.loc_sampler = get_sampler(
            "loc", loc_distribution, min_loc, max_loc, **kwargs
        )

Maximum Coverage Problem (MCP)

MCPEnv

MCPEnv(
    generator: MCPGenerator = None,
    generator_params: dict = {},
    check_solution=False,
    **kwargs
)

Bases: RL4COEnvBase

Maximum Coverage Problem (MCP) environment At each step, the agent chooses a set. The reward is 0 unless enough number of sets are chosen. The reward is the total weights of the covered items (i.e., items in any chosen set).

Observations

• the weights of items
• the membership of items in sets
• the number of sets to choose

Constraints

• the given number of sets must be chosen

Finish condition

• the given number of sets are chosen

Reward

• the total weights of the covered items (i.e., items in any chosen set)

Parameters:

• generator (MCPGenerator, default: None ) –

  MCPGenerator instance as the data generator

• generator_params (dict, default: {} ) –

  parameters for the generator

Source code in rl4co/envs/graph/mcp/env.py

def __init__(
    self,
    generator: MCPGenerator = None,
    generator_params: dict = {},
    check_solution=False,
    **kwargs,
):
    super().__init__(**kwargs)
    if generator is None:
        generator = MCPGenerator(**generator_params)
    self.generator = generator
    self.check_solution = check_solution
    self._make_spec(self.generator)

MCPGenerator

MCPGenerator(
    num_items: int = 200,
    num_sets: int = 100,
    min_weight: int = 1,
    max_weight: int = 10,
    min_size: int = 5,
    max_size: int = 15,
    n_sets_to_choose: int = 10,
    size_distribution: Union[
        int, float, str, type, Callable
    ] = Uniform,
    weight_distribution: Union[
        int, float, str, type, Callable
    ] = Uniform,
    **kwargs
)

Bases: Generator

Data generator for the Maximum Coverage Problem (MCP).

Parameters:

• num_items (int, default: 200 ) –

  number of items in the MCP

• num_sets (int, default: 100 ) –

  number of sets in the MCP

• min_weight (int, default: 1 ) –

  minimum value for the item weights

• max_weight (int, default: 10 ) –

  maximum value for the item weights

• min_size (int, default: 5 ) –

  minimum size for the sets

• max_size (int, default: 15 ) –

  maximum size for the sets

• n_sets_to_choose (int, default: 10 ) –

  number of sets to choose in the MCP

Returns:

• –

  A TensorDict with the following keys: membership [batch_size, num_sets, max_size]: membership of items in sets weights [batch_size, num_items]: weights of the items n_sets_to_choose [batch_size, 1]: number of sets to choose in the MCP

Source code in rl4co/envs/graph/mcp/generator.py

def __init__(
    self,
    num_items: int = 200,
    num_sets: int = 100,
    min_weight: int = 1,
    max_weight: int = 10,
    min_size: int = 5,
    max_size: int = 15,
    n_sets_to_choose: int = 10,
    size_distribution: Union[int, float, str, type, Callable] = Uniform,
    weight_distribution: Union[int, float, str, type, Callable] = Uniform,
    **kwargs,
):
    self.num_items = num_items
    self.num_sets = num_sets
    self.min_weight = min_weight
    self.max_weight = max_weight
    self.min_size = min_size
    self.max_size = max_size
    self.n_sets_to_choose = n_sets_to_choose

    # Set size distribution
    if kwargs.get("size_sampler", None) is not None:
        self.size_sampler = kwargs["size_sampler"]
    else:
        self.size_sampler = get_sampler(
            "size", size_distribution, min_size, max_size + 1, **kwargs
        )

    # Item weight distribution
    if kwargs.get("weight_sampler", None) is not None:
        self.weight_sampler = kwargs["weight_sampler"]
    else:
        self.weight_sampler = get_sampler(
            "weight", weight_distribution, min_weight, max_weight + 1, **kwargs
        )