# Combinatorial Optimization

# Discrete Optimization

In **discrete optimization**, some or all of the variables in a model are required to belong to a *discrete set*; this is in contrast to continuous optimization in which the variables are allowed to take on any value within a range of values. Here, we consider two branches of discrete optimization. In **integer programming**, the discrete set is a subset of integers.

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

# Traveling Salesman Problem

Back to Combinatorial Optimization

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