2.1 Beginnings

We start by looking at some of the most common types of single-objective optimization problems that arise in practice, and popular techniques for solving them. The following two toy problems introduce some of the fundamental notions.

  1. Let \(S\) be the set of all the four-letter English words. What is the maximum number of \(\ell\)’s a word in \(S\) can have?

    There are numerous four-letter words that contain the letter \(\ell\) – for example, “line”, “long”, “tilt”, and “full”. From this short list alone, we know the maximum number of \(\ell\)’s is at least 2 and at most 4. As “llll” is not an English word, the maximum number cannot be 4. Can the maximum number be 3? Yes, because “lull” is a four-letter word with three \(\ell\)’s.

    This example illustrates some fundamental ideas in optimization. In order to say that 3 is the correct answer, we need to

    • search for a word that has three \(\ell\)’s, and

    • provide an argument that rules out any value higher than 3.

    In this example, the only possible value of \(\ell\) higher than 3 is 4, which was easily ruled out. Unfortunately, that is not always easy to do, even in similar contexts.

    For instance, if the problem was to find the maximum number of y’s (instead of \(\ell\)’s), would the same approch work?

  2. A pirate lands on an island with a knapsack that can hold 50kg of treasure. She finds a cave with the following items:

    Item Weight Value Value/kg
    iron shield 20kg $2800.00 $140.00/kg
    gold chest 40kg $4400.00 $110.00/kg
    brass sceptre 30kg $1200.00 $40.00/kg

    Which items can she bring back home in order to maximize her reward without breaking the knapsack?

    If the pirate does not take the gold chest, she can take both the iron shield and the brass sceptre for a total value of $4000. If she takes the gold chest, she cannot take any of the remaining items. However, the value of the gold chest is $4400, which is larger than the combined value of the iron shield and the brass sceptre. Hence, the pirate should just take the gold chest.

    Here, we performed a case analysis and exhausted all the promising possibilities to arrive at our answer. Note that a greedy strategy that chooses items in descending value per weight would give us the sub-optimal solution of taking the iron shield and brass sceptre.

Even though there are problems for which the greedy approach would return an optimal solution, the second example is not such a problem. The general version of this problem is the classic binary knapsack problem and is known to be NP-hard (informally, NP-hard optimization problems are problems for which no algorithm can provide an output in polynomial time – when the problem size is large, the run time explodes).

Many real-world optimization problems are NP-hard. Despite the theoretical difficulty, practitioners often devise methods that return “good-enough solutions” using approximation methods and heuristics. There are also ways to obtain bounds to gauge the quality of the solutions obtained. We will be looking at these issues at a later stage.