Combinatorial Optimization
Prof. Flavio Keidi Miyazawa

Optimization problems, in general, aim to maximize or minimize a function defined over a certain domain. The classical optimization theory deals with the case where the domain is infinite. In the case of so-called combinatorial optimization problems, the domain is typically finite; moreover, it is generally easy to list its elements and also test whether a given element belongs to that domain. Even so, the naive idea of ​​testing all the elements of this domain in the search for the best proves to be unfeasible in practice, even for instances of moderate size.

As classic examples of combinatorial optimization problems we can mention the traveling salesman problem, the backpack problem, the minimum set coverage problem, the Steiner forest problem and the maximum satisfiability problem. They all arise naturally in practical applications, such as the design of telecommunication networks and VLSI circuits, the packaging of objects in containers, the location of distribution centers, the scheduling and routing of vehicles, etc. Other areas of application include statistics (data analysis), economics (input / output matrices), physics (minimum energy states), molecular biology (DNA and protein alignment, pattern inference), etc.

Strategies that have been successful in addressing these problems involve methods in entire schedule, probabilistic algorithms and approximation algorithms.

Informal description of some of these problems:

Network Design with Connectivity Restrictions
Minimum Path Project
Traveling Salesman Problem
Vehicle Routing Problem
Cutting Boards
Task Scheduling
Classification and Partitioning Problems
Cutting and Packing Problems
Frequency Assignments in Cellular Telephony

 Network Design with Connectivity Restrictions
Suppose you are designing a computer network with some connectivity restrictions. In this network, some important computers must always be able to communicate with each other, others are less important and can only serve as an intermediate node to connect the main computers. With this set of restrictions in hand and the cost to directly connect two computers through optical fibers, design the lowest cost network, respecting connectivity restrictions.

We can also consider adding security restrictions against failures. For example, the network could be built in such a way that even if a connection connecting two computers is temporarily down, the projected network must allow an alternate route that connects all the main computers.

Example of a network connecting cities. Important cities (in red) remain connected even if a connection fails.

In VLSI circuits, there are restrictions on the shape of the connections, which often must be horizontal or vertical. The blue dots in the figure above must be connected by a network.

Minimum Path Problem
One of the most studied problems in Combinatorial Optimization is the problem of connecting two points of minimum cost. In this case, we have a map of connections between points (not necessarily for each pair) and each connection has a cost to be covered. In addition, we have a starting point and an ending point. The minimum cost path is the sequence of connections that must be followed from the start point to the end point, whose total cost is minimal. Although well studied, this is still a very interesting problem, especially when it is required that we have quick solutions for maps containing tens of millions of points and connections.

Example of the Minimum Path Problem applied to image segmentation.

Traveling Salesman Problem
An electronic components factory needs to weld thousands of printed circuit boards. To make things faster, all plates of the same type are welded one after the other, at previously specified points. The objective is to know the path of the positions that the welding machine must travel so that it spends the shortest possible time on each plate. Note that any time gain on this path can be crucial to welding the thousands of plates in a short time.

Now, suppose that you want to visit some cities in the State of Sao Paulo and from a starting city, go through other cities and return to the city of initial, spending the least time possible. 

Example of a route connecting some cities in Sao Paulo, without repetition.

Example of a route connecting 52 points of a park in the city of Berlin.

See more about this problem on the page about Traveling Salesman Problem.

 Vehicle Routing Problem

Consider that you have a warehouse (matrix) from which trucks loaded with certain products leave and must pass through some cities. However, in each city the truck must deliver certain products and there is a maximum capacity that the truck can carry on each trip. The goal is to minimize the total expense (say in kilometers driven) to deliver all products and respecting the truck's capacity. Example routes:

Classification and Partitioning Problems
Consider that you have a set of objects P (eg web pages), a set of classes L, costs c_lj to associate a class l with object j (distance from the page to a class) and costs w_ij applied when the objects iej receive distinct classes. The goal is to find a classification of objects in classes with the lowest cost.

                         

Example: Classification of pixels in an image. On the left we have an image with 50% degradation and on the right, the image with its pixels classified in black or white.

In the next figure, we have an illustrative example of animals that should be classified into four classes. The edges indicate the existence of classification weights (for an animal to be classified in a class) and separation (proximity between animals and how much they would weigh if they are in different classes).

Cutting and Packing Problems
Now consider that you are building a building. The windows and glass partitions of the building are needed in different quantities and sizes. The construction company makes the purchase order to a glass company, specifying the dimensions and quantities of each item. The glass manufacturer must cut these pieces from fixed-sized glass plates, which are supplied by the glass manufacturer. To minimize costs, the purpose of glass making is to use the fewest of these plates.

Example of cutting rectangular flaps from boards.

Note that a related problem, but now three-dimensional, is the problem of packing objects inside containers, in order to maximize the load in the container, or to minimize the amount of containers used to transport a certain set of objects.

Example of packing boxes in containers.

If you want to know more about this type of problem, see the Cutting and Packing Problems

 Frequency Assignments in Cellular Telephony
Now consider a company that has several towers (antennas) that cover a certain region where cell phone users travel. When two antennas very close to each other receive the same frequencies, the region that is covered by these antennas presents a lot of interference. The objective is to assign the frequencies (of limited quantity) to the antennas in order to minimize the total interference of the assignment.

You may have realized that these combinatorial optimization problems can be easily formulated and understood. In these problems, we aim to maximize or minimize a function defined over a typically finite domain. But make no mistake, although finite, this domain is for many problems, extremely large and in most cases it is computationally unfeasible to go through this entire domain.

Some of the main lines to tackle NP-difficult problems are:

Approximation Algorithms
Probabilistic Algorithms
Hybrid Algorithms
Integer Linear Programming
Quadratic Programming
Semi-defined programming
Heuristics

Flávio Keidi Miyazawa's Homepage