Combinatorial Optimization

Quadratic Assignment Problem

Summary: The objective of the Quadratic Assignment Problem (QAP) is to assign \(n\) facilities to \(n\) locations in such a way as to minimize the assignment cost. The assignment cost is the sum, over all pairs, of the flow between a pair of facilities multiplied by the distance between their assigned locations.

Multiple Traveling Salesman Problem (mTSP)

Summary: The Multiple Traveling Salesman Problem (\(m\)TSP) is a generalization of the Traveling Salesman Problem (TSP) in which more than one salesman is allowed. Given a set of cities, one depot where \(m\) salesmen are located, and a cost metric, the objective of the \(m\)TSP is to determine a tour for each salesman such that the total tour cost is minimized and that each city is visited exactly once by only one salesman.

Rogo Puzzle

Summary: Given a \(n \times m\) grid with numbered cells and forbidden cells, the objective of the Rogo puzzle is to find a loop of fixed length through the grid such that the sum of the numbers in the cells on the loop is maximized.

Subscribe to RSS - Combinatorial Optimization