Sunyoung Kim

Equivalent Sufficient Conditions for Global Optimality of Quadratically Constrained Quadratic Program

  • Sunyoung Kim
  • Masakazu Kojima
    • Categories Global Optimization, Linear, Cone and Semidefinite Programming, Semi-definite Programming Tags , , , , ,

    \(\) We study the equivalence of several well-known sufficient optimality conditions for a general quadratically constrained quadratic program (QCQP). The conditions are classified in two categories. The first one is for determining an optimal solution and the second one is for finding an optimal value. The first category of conditions includes the existence of a … Read more

    The Largest Unsolved QAP Instance Tai256c Can Be Converted into A 256-dimensional Simple BQOP with A Single Cardinality Constraint

  • Koichi Fujii
  • Sunyoung Kim
  • Masakazu Kojima
  • Hans D Mittelmann
  • Yuji Shinano
    • Categories 0-1 Programming, Branch and Cut Algorithms, Semi-definite Programming Tags , , , , ,

    Tai256c is the largest unsolved quadratic assignment problem (QAP) instance in QAPLIB; a 1.48\% gap remains between the best known feasible objective value and lower bound of the unknown optimal value. This paper shows that the instance can be converted into a 256 dimensional binary quadratic optimization problem (BQOP) with a single cardinality constraint which … Read more

    Solving Challenging Large Scale QAPs

  • Koichi Fujii
  • Naoki Ito
  • Masakazu Kojima
  • Kim-Chuan Toh
  • Sunyoung Kim
  • Yuji Shinano
    • Categories Applications - OR and Management Sciences Tags ,

    We report our progress on the project for solving larger scale quadratic assignment problems (QAPs). Our main approach to solve large scale NP-hard combinatorial optimization problems such as QAPs is a parallel branch-and-bound method eciently implemented on a powerful computer system using the Ubiquity Generator (UG) framework that can utilize more than 100,000 cores. Lower … Read more