An assumption based combinatorial optimization method

Combinatorial optimization is a hard problem long studied in operations research. The solution the authors propose for the problem, an assumption based combinatorial optimization method, is a local search method in which a solution is formulated as a set of assumptions. Minimal support for the objective function is a minimal set of assumptions that guarantees the value of the objective function. Using minimal support, the method finds an approximate optimal solution efficiently because it (1) reduces the number of neighbors, (2) avoids cycles of search, (3) prunes search space, and (4) never stays at a local optimal solution. The authors applied this method to the job shop scheduling, a typical combinatorial optimization problem, and demonstrated the method’s effectiveness compared with the iterative improve method and the branch-and-bound method. [In Japanese.]