平成９年度第６回KSMAP

日時：１月１２日（月）　１５：００〜１７：００

場所：京都大学 工学部８号館 ２階 共同３教室

       京都大学へのアクセス

講演題目と講演者(Note: Both talks will be given in English.)：

  Title: Efficient 2 and 3-Flip Neighborhood Search Algorithms for the MAX SAT

  Speaker: Mutsunori Yagiura (Graduate School of Engineering, Kyoto University)

  Abstract: For problems SAT and MAX SAT, local search algorithms are widely
    acknowledged as one of the most effective approaches. Most of the local
    search algorithms are based on the 1-flip neighborhood, which is defined
    to be the set of solutions obtainable by flipping the truth assignment of
    one variable. In this paper, we consider $r$-flip neighborhood for
    $r \geq 2$, and propose, for $r=2, 3$, new implementations that reduce the
    number of candidates in the neighborhood without sacrificing the solution
    quality. For 2-flip (resp., 3-flip) neighborhood, we show that the expected
    size of the new neighborhood is $O(n+m)$ (resp., $O(m+t^2n)$), which is
    usually much smaller than the original size $O(n^2)$ (resp., $O(n^3)$),
    where $n$ is the number of variables, $m$ is the number of clauses and $t$
    is the maximum number of appearances of one variable. Computational results
    tell that these estimates by the expectation represent the real performance
    of the local search with $r$-flip neighborhoods. These neighborhoods are
    then used under the framework of tabu search etc., and compared with other
    existing algorithms based on 1-flip neighborhood. The results exhibit good
    prospects of the proposed algorithms.

    Keywords: MAX SAT, SAT, local search, neighborhood.


  Title: Global Optimization via Boltzmann Distribution, Importance Sampling
    and Markov Chains

  Speaker: Reuven Y. Rubinstein
    (Faculty of Industrial Engineering and Management, Technion, Haifa, Israel)

  Abstract: We present a new method for finding the optimal solution for
    combinatorial and continuous nonconvex optimization problems with
    convex bounded domains. To find the optimal solution we solve a sequence
    of simple auxiliary smooth optimization problems based on importance
    sampling, Markov chain and Boltzmann distribution. We use the importance
    sampling as an important ingredient to adjust adaptively the temperature
    in the Boltzmann distribution and to find the optimal solution. In fact,
    we use the mode of the unimodal importance sampling distribution as
    estimate of the optimal solution for both continuous and combinatorial
    optimization problems. We show that our approach has certain advantages
    to the well-known heuristic algorithms, like simulated annealing, tabu
    search and genetic algorithms. Supporting numerical results are provided
    as well.