After weeks of solo travel, Sofia is finally heading to Athens, ready to take in the city’s history and charm. In addition, she was meeting up with her whole group of friends from back home—all ten of them. But planning a trip with ten people proved more challenging than expected—especially when it came to deciding where to stay.

The group chat had been buzzing for weeks, but no consensus was in sight. Each friend had their own preferences: Anastasia wanted cozy cafes and boutique shopping, Bruno was keen on being near the sea, and Clara insisted on staying close to the historic center. Other friends were interested in nightlife, green spaces, or a more local vibe. Trying to find one neighborhood to satisfy everyone seemed impossible.

Sofia, ever the problem-solver, suggested a different approach. Instead of focusing on just one neighborhood, she proposed creating a shortlist of places that collectively met everyone’s preferences. Since many neighborhoods shared similar amenities—like cafes, seaside views, or proximity to attractions—Sofia’s goal became selecting the fewest number of neighborhoods that covered all the group’s needs. This way, they can avoid vote fragmentation over a long list and everyone has at least one neighborhood that covers every interest.

This is where the Set Covering Problem (SCP) comes in. What is the Set Covering Problem?The Set Covering Problem asks: How can you select the smallest number of neighborhoods to ensure that all your friends' preferences are satisfied?Unlike a scenario where every neighborhood must be included, the Set Covering Problem allows you to choose only those neighborhoods that collectively cover the interests of the group, minimizing distractions during decision-making.In Sofia’s case, she needs to identify the neighborhoods that will best meet the diverse tastes of her friends.

While some may prioritize cozy cafes, others might seek nightlife or cultural experiences. Balancing these preferences while keeping her list concise is key to making a successful decision together.In many practical situations, each neighborhood may have an associated cost or weight—this could be travel expenses, time required to visit, or popularity among tourists. F

or the sake of simplicity, we’ll assume all neighborhoods have the same cost in this scenario. However, it’s important to note that in real-world applications, these costs can vary, adding another layer of complexity to Sofia’s decision-making process.

Problem Overview

Objective: Sofia aims to create the shortest possible shortlist of neighborhoods to streamline decision-making for her and her friends, ensuring everyone can focus on the best options that meet their preferences.

Decision Variables: Each neighborhood represents a choice—whether to include it in the shortlist or not.

Constraints: Every shortlisted neighborhood must cover at least one of the interests identified by her friends and every interest should be covered by at least one chosen neighborhood.

Visualizing the neighborhoods Sofia creates the graph below to better understand how each neighborhood in Athens matches her friends' preferences. In this graph, each preference is represented as a point—such as cozy cafes, seaside views, or nightlife—and the neighborhoods are overlaid as sets.

If a neighborhood satisfies a particular preference, it is contained within the corresponding set. For instance, the neighborhood of Glyfada covers Seaside, Boutiques and Nightlife, while Kolonaki covers Boutiques, Trendy Bars, and Galleries. By using this visual, Sofia can easily see which neighborhoods cover the most preferences and how different sets of neighborhoods might work together to satisfy all of her friends' diverse interests.

Graph illustrating the neighborhoods in Athens (as sets) and the preferences (as points)

For example, these are two possible set coverings that cover all the interests of Sofia's friends:

• Option 1: Shortlist 4 neighborhoods: Glyfada, Plaka, Kolonaki, and Pagkrati.

• Option 2: Shortlist 4 neighborhoods: Kifisia, Monastiraki, Glyfada, and Exarchia.

These selections highlight how different combinations of neighborhoods can meet the diverse preferences of the group.

The Complexity of the Problem

While selecting neighborhoods may seem straightforward, the underlying problem is actually quite complex. The Set Covering Problem is classified as NP-hard, which means that finding the best solution can be very difficult and time-consuming, especially as the number of options increases.

What is NP-Hardness?

• Definition: A problem is considered NP-hard when no known algorithm can solve all instances of the problem in polynomial time. This means that, as the size of the problem increases, finding the optimal solution may require an impractically long time, often involving exhaustive searching through many possibilities.

• Implications: For Sofia, this means that as she considers more neighborhoods and preferences, the number of possible combinations can grow rapidly. While she might easily find a good solution with a few neighborhoods, figuring out the absolute best combination becomes much harder with each additional option.

• Everyday Relevance: Many real-life scenarios, such as planning a trip or optimizing a schedule, can be NP-hard. This is why people often use practical approaches or heuristics—methods that provide good enough solutions quickly—rather than seeking the perfect answer.

By framing her trip planning as a Set Covering Problem, Sofia not only faces the challenge of choosing neighborhoods but also navigates the complexities of decision-making in a situation that could be much more complicated than it seems.

Exploring the Set Covering Problem with Three Approaches

The accompanying notebook allows you to explore how three different algorithms solve the Set Covering Problem:

1. Greedy Algorithm: This method selects neighborhoods based on the immediate best choice, covering the most preferences at each step. It's fast but doesn't always give the optimal solution.

2. Mixed-Integer Programming (MIP): This approach guarantees the best solution by exploring all possible combinations through optimization techniques. While slower than greedy, it ensures an optimal result.

3. Backtracking: This method also explores all possibilities but does so by systematically testing every combination. It's the slowest but guarantees the optimal solution, especially useful for smaller datasets.

Each algorithm has its strengths: Greedy is fast but approximate, MIP finds the optimal solution quickly for small to medium problems, and Backtracking explores everything but is much slower. The notebook allows you to run all three approaches and compare their solutions and execution times directly. You can run and explore the notebook directly here: https://colab.research.google.com/drive/1DaPgMGZ2tnGXDLHHD_TtnB2yqpz39xBK?usp=sharing

Conclusion

Sofia’s journey through Europe taught her that making the best decisions often requires a little help from optimization. With the Set Covering Problem, she returned to her friends with a much shorter list of neighborhoods that fit everyone’s preferences perfectly. By narrowing down the options, Sofia ensured that the group's votes wouldn’t be fragmented by too many choices—making it easier for them to focus on the best neighborhoods and reach a decision quickly.

In the end, Sofia’s story shows that optimization is more than just a mathematical tool—it’s about simplifying complexity and making decisions easier, whether you're planning a trip or solving bigger challenges. As Sofia moves on, our next character—a chef—will face her own set of unique optimization problems in the kitchen. Stay tuned for more!