Constructive Heuristics in Discrete Optimization | by Bruno Scalia C. F. Leite | May, 2024
[ad_1]
The next example is a classical problem on subset partitioning in which our goal is to find a subset of elements from an undirected graph G(V, E) with the maximum number of elements such that there are no edges connecting any pair from the given subset.
Let us start by creating classes to work with the graph elements of this problem. The class Node will be used to represent a vertice (or node) from our undirected graph. It will have as attributes:
neighbors: A list of neighbor verticesindex: Its identifierselected: A boolean to indicate when it was included in the solution
Whenever a Node instance is deleted from our feasible subset of elements, we must remove it from its neighbors’ list of neighbors, so we create a method delete to make it easier.
The property degree computes the number of neighbors from a given node and will be used as our criterion for choosing the next element in the greedy approach.
import copy
from typing import Dict, List, Optional, Tupleclass Node:
neighbors: List['Node']
index: int
selected: bool
def __init__(self, index):
self.index = index
self.neighbors = []
self.selected = False
def __repr__(self) -> str:
return f"N{self.index}"
def add_neighbor(self, node: 'Node'):
if node not in self.neighbors:
self.neighbors.append(node)
def delete(self):
for n in self.neighbors:
n.neighbors.remove(self)
@property
def degree(self):
return len(self.neighbors)
Now, let us create our Graph class. It should be instantiated from a list of edges and an optional list of nodes. It should have an attribute N which is a dictionary of existing nodes (or vertices).
The property queue should return a list of nodes not yet selected for us to consider including in the solution at each step of our constructive heuristic.
Whenever a new Node instance is selected, the method select should be called, which changes its selected attribute and calls its delete method.
class Graph:N: Dict[int, Node]
def __init__(
self,
edges: List[Tuple[int, int]],
nodes: Optional[List[int]] = None
):
# Start the set
if nodes is None:
self.N = {}
else:
self.N = {i: Node(i) for i in nodes}
# Include all neighbors
for i, j in edges:
self._new_edge(i, j)
@property
def active_nodes(self):
return [node for node in self.N.values() if node.selected]
@property
def inactive_nodes(self):
return [node for node in self.N.values() if not node.selected]
@property
def nodelist(self):
return list(self.N.values())
@property
def queue(self):
return [n for n in self.nodelist if not n.selected]
def _new_node(self, i: int):
if i not in self.N:
self.N[i] = Node(i)
def _new_edge(self, i: int, j: int):
self._new_node(i)
self._new_node(j)
self.N[i].add_neighbor(self.N[j])
self.N[j].add_neighbor(self.N[i])
def select(self, node: Node):
node.selected = True
selected_neighbors = node.neighbors.copy()
for n in selected_neighbors:
other = self.N.pop(n.index)
other.delete()
def deactivate(self):
for n in self.N.values():
n.selected = False
def copy(self):
return copy.deepcopy(self)
Now, let us create an abstraction for our constructive heuristic. It should be instantiated, as its corresponding Graph, from a list of edges and an optional list of nodes. When instantiated, its attribute graph is defined from the original graph of the problem instance.
from abc import ABC, abstractmethod
from mis.graph import Graph, Node
from typing import List, Optional, Tupleclass BaseConstructive(ABC):
graph: Graph
def __init__(
self,
edges: List[Tuple[int, int]],
nodes: Optional[List[int]] = None,
):
self.graph = Graph(edges, nodes)
The solve method will be at the core of our solution procedure. It should return a subgraph of G(V, E) with a candidate solution. When using an instance of the solution procedure as a callable, it should overwrite its nodes’ selected attributes based on the result returned by the solve method.
Notice the choice method here is an abstraction yet to be overwritten by child classes.
class BaseConstructive(ABC):
# Check previous definitionsdef __call__(self, *args, **kwargs):
S = self.solve(*args, **kwargs)
for i, n in S.N.items():
self.graph.N[i].selected = n.selected
@property
def cost(self):
return len(self.graph.active_nodes)
def solve(self, *args, **kwargs) -> Graph:
self.graph.deactivate()
G = self.graph.copy()
for i in range(len(G.N)):
n = self.choice(G)
G.select(n)
if len(G.queue) == 0:
assert len(G.N) == i + 1, "Unexpected behavior in remaining nodes and iterations"
break
return G
@abstractmethod
def choice(self, graph: Graph) -> Node:
pass
Let us first create an algorithm that randomly chooses the next node to include into our solution.
import randomclass RandomChoice(BaseConstructive):
rng: random.Random
def __init__(
self,
edges: List[Tuple[int, int]],
nodes: Optional[List[int]] = None,
seed=None
):
super().__init__(edges, nodes)
self.rng = random.Random(seed)
def choice(self, graph: Graph) -> Node:
return self.rng.choice(graph.queue)
It can already be used in our solution procedure and creates feasible solutions that are maximal independent sets (not maximum). However, its performance varies according to the random sequence and we might be vulnerable to poor results.
Adaptive greedy
Alternatively, at each step, we could have chosen the next node that has the smallest impact on the “pool” of feasible elements from the ground set. It would mean choosing the next element that in the subgraph has the smallest number of neighbors. In other words, with the smallest degree attribute. This is the same approach adopted by Feo et al. (1994).
Notice the degree of our nodes might vary as the partial solution changes and elements are removed from the subgraph. It can be therefore defined as an adaptive greedy procedure.
There are other situations where the cost of the contribution of an element is affected by the previous choices of elements made by the algorithm. We shall call these adaptive greedy algorithms (Resende & Ribeiro, 2016).
Let us then implement an algorithm that chooses as the next element the one from the subgraph with the smallest degree.
class GreedyChoice(BaseConstructive):def choice(self, graph: Graph) -> Node:
return min([n for n in graph.queue], key=lambda x: x.degree)
Although it does not provide proof of optimality, the adaptive greedy approach can also be an interesting strategy for providing fast and good-quality results to this problem. But try running the random approach multiple times… In some instances, it might outperform the greedy strategy (at least in one or a few runs). Why not implement a multi-start framework then?
Multistarts
In this approach, multiple independent runs are performed, and a registry of the best solution is kept. In the end, the best solution is returned.
class MultiRandom(RandomChoice):def solve(self, n_iter: int = 10) -> Graph:
best_sol = None
best_cost = 0
for _ in range(n_iter):
G = super().solve()
if len(G.N) > best_cost:
best_cost = len(G.N)
best_sol = G
return best_sol
In my GitHub repository, you will find an example of a 32-node graph in which the adaptive greedy found a subset of 5 vertices, but a random framework with multi-start found a solution with 6. The solution procedure is represented below.
[ad_2]
