Search Algorithms for Discrete Optimization Problems Ananth Grama, Anshul Gupta, George Karypis, and Vipin Kumar

A discrete optimization problem can be expressed as a tuple (S, f). The set is a finite or countably infinite set of all solutions that satisfy specified constraints.

The function f is the cost function that maps each element in set S onto the set of real numbers R.

The objective of a DOP is to find a feasible solution xopt, such that f(xopt) ≤ f(x) for all x  S.

A number of diverse problems such as VLSI layouts, robot motion planning, test pattern generation, and facility location can be formulated as DOPs.

Discrete Optimization: Example

• In the 0/1 integer-linear-programming problem, we are given an m×n matrix A, an m×1 vector b, and an n×1 vector c.

• The objective is to determine an n×1 vector whose elements can take on only the value 0 or 1.

•