Constructive Heuristics in Discrete Optimization

Author:Murphy | View: 27040 | Time: 2025-03-22 21:32:08

Representation of a constructive heuristic selecting elements from a ground set. (Image by the author).

Discrete or Combinatorial Optimization is a relevant study area in Operations Research (OR) and Computer Science, dedicated to identifying the best (or a suitable) solution from a finite set of possibilities. With applications including vehicle routing, operations scheduling, and network design, often the problems cannot be tackled by exact approaches in tractable runtimes. Therefore, heuristics can be an interesting alternative to provide fast and good quality solutions guiding operations in reasonable computing time.

Not only as stand-alone techniques, constructive heuristics can be coupled with other Algorithms to improve their runtimes, cost functions, or other performance aspects. For instance, providing an initial solution to a Mixed-Integer Programming (MIP) solver can establish a dual bound that helps to prune the search space. Additionally, this initial solution can enable the solver to incorporate local search heuristics more effectively, potentially leading to faster convergence and better overall solution quality.

In this article, you will find basic definitions of discrete optimization with an introduction to constructive heuristics. Python examples will be used to illustrate the topics with applications to the Knapsack and Maximum Independent Set problems. Random choices and greedy selection of elements will be analyzed as we create our solutions.

The complete code for these problems, besides several other optimization examples, is available in my GitHub repository.

Discrete Optimization

In a broad sense, a numerical optimization problem aims to find the best value of an objective f which is a function of decision variables x and might be subject to some equality and inequality constraints, functions of x as well. The objective can be defined in either a minimization or a maximization sense.

Discrete optimization refers to a category of optimization problems in which decision variables can assume only discrete values. Therefore one faces a finite (although it might be large) set S of possible solutions from which it must be selected a feasible one leading to the best objective.

Solution Construction

Many algorithms for combinatorial optimization problems build a solution incrementally from scratch, where at each step, a single ground set element is added to the partial solution under construction. A ground set element to be added at each step cannot be such that its combination with one or more previously added elements leads to an infeasibility (Resende & Ribeiro, 2016).

Suppose we have a ground set E of elements that might be used to compose a solution S. Suppose F is a subset of elements from E that included into a partial solution S would not lead to infeasibility and would improve the overall results. A pseudocode for a constructive heuristic can be described as the following.

function constructive(E){
    S = {}
    F = {i for i in E if S union {i} is feasible}
    while F is not empty{
        i = choose(F)
        S = S union {i}
        F = {i for i in E if S union {i} is feasible}
    }
    return S
}

The choice of the next element to include in the solution can vary according to the problem and strategy adopted. In some situations, choosing one element that leads to the best immediate effect in the partial solution can be an interesting alternative, in other situations random effects might be desirable. We will compare both approaches in two different problems in the remainder of this article.

In some problems, there are exact constructive algorithms in polynomial time even when adopting a greedy incremental approach as will be presented in this article. An interesting example is the Minimum Spanning Tree (MST) problem. However, this is not the case for the problems that will be presented here.

The knapsack problem

In the knapsack problem, from a set of items with individual attributes of weight and value, one must select the most valuable ones to include in a knapsack of pre-defined capacity in such a way that the total weight of items selected does not exceed it. In this problem, we can think of the items available as our ground set.

So let us create a Python class to represent each of our items available.

class Item:

    index: int
    weight: float
    value: float
    density: float
    selected: bool

    def __init__(self, index, weight, value) -> None:
        self.index = index
        self.weight = weight
        self.value = value
        self.density = value / weight
        self.selected = False

    @classmethod
    def from_dict(cls, x: dict):
        index = x["index"]
        weight = x["weight"]
        value = x["value"]
        return cls(index, weight, value)

We also create attributes density with the corresponding "value per weight" ratio of the given item, index with its corresponding identifier, and selected to indicate if that item is part of our final solution. The classmethod from_dict is useful for initializing a new item from a Python dict with keys index, weight, and value.

Now, let us think of an abstraction of a constructive heuristic for the knapsack problem. It takes as initialization arguments the knapsack capacity and a list of items (as dictionaries). Both should be available as attributes of our class to be used in the solution procedure.

from typing import Dict, List, Union

class BaseConstructive:

    items: List[Item]
    capacity: float
    solution: List[Item]

    def __init__(self, capacity: float, items: List[Dict[str, Union[int, float]]]) -> None:
        self.items = []
        self.capacity = capacity
        for new_element in items:
            item = Item.from_dict(new_element)
            self.items.append(item)
        self.solution = []

    @property
    def cost(self):
        return sum(i.value for i in self.solution)

A naive solution procedure can iterate over our set of items and include the next item in the solution if its corresponding weight is lesser than or equal to the remaining capacity.

class BaseConstructive:
    # Check previous definition

    def solve(self):
        remaining = self.capacity
        for item in self.items:
            if remaining >= item.weight:
                item.selected = True
                self.solution.append(item)
                remaining = remaining - item.weight

However, this method can lead to poor-quality solutions. Suppose at the beginning of our list there was a heavy item with a small value. It would be included in the solution occupying available space that more valuable alternatives could use.

A better choice could have been to first sort items by their density and then run the previous procedure of including the next from the input if it fits in the remaining space. That leads us to the Greedy selection.

Greedy selection

A greedy approximation algorithm is an iterative algorithm which produces a partial solution incrementally. Each iteration makes a locally optimal or suboptimal augmentation to the current partial solution, so that a globally suboptimal solution is reached at the end of the algorithm (Wan, 2013).

In the context of the knapsack problem, we could choose the next element using a priority of density as previously suggested. In this case, a greedy approach does not guarantee the optimality of the solution, but it can be an interesting alternative for fast and good-quality results. In our Python code, we can achieve that just by sorting our items in place previously to applying the solution procedure.

class GreedyConstructive(BaseConstructive):

    def solve(self):
        self.items.sort(key=lambda x: x.density, reverse=True)
        super().solve()

In my GitHub repository, you might find an instance with 10 items to which I applied both methods. While the choice based on the original input sequence produced a solution with a total value of 68, the choice based on density resulted in a total value of 91. I would go with the greedy approach for good-quality and fast solutions on this one.

The maximum independent set problem

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 vertices
index: Its identifier
selected: 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, Tuple

class 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, Tuple

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

    def __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 random

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

Solution procedure of constructive heuristic applied to a maximum independent set problem. (Animation by the author).

Conclusions

Throughout this article, constructive heuristics in the context of discrete optimization were introduced and applied to the knapsack and the maximum independent set problems. Intuitions on how to choose ground elements to build a solution were presented exemplifying a greedy choice, random factors, and multi-starts. The complete code is available in my GitHub repository.

References

Feo, T. A., Resende, M. G., & Smith, S. H., 1994. A greedy randomized adaptive search procedure for maximum independent set. Operations Research, 42(5), 860–878.

Resende, M. G., & Ribeiro, C. C., 2016. Optimization by GRASP. Springer Science+ Business Media New York.

Wan, PJ., 2013. Greedy Approximation Algorithms. In: Pardalos, P., Du, DZ., Graham, R. (eds) Handbook of Combinatorial Optimization. Springer, New York, NY.

Tags: Algorithms Heuristics Operations Research Optimization Python