Accession Number:



Canonical Duality Theory and Algorithm for Solving NP-Hard Problems in Decision Science and Complex Systems

Descriptive Note:

[Technical Report, Final Report]

Corporate Author:


Personal Author(s):

Report Date:


Pagination or Media Count:



Supported by this AFOSR grant, the PI and his Co-PI, student, post-doctoral fellow and coworkers have successfully applied the canonical duality theory and its associated algorithms for solving a large class of challenging problems in global optimization and decision science. His group has published 2 books and about 26 papers. The most significant achievements of this project are the analytical solution to the linear knapsack problem and its applications to structural topology optimization. The knapsack problems are well-known NP-Hard problems in computer science and global optimization. Due to the integer constraint, traditional theories and methods cannot be applied to obtain global optimal solution in polynomial time. Even the simplest linear knapsack problem is listed as one of Karps 21 NP-complete problems. However, by using the canonical duality theory, the integer constrained global optimization problems in n-dimensional space can be equivalently converted to a unified concave maximization problem in ONE dimensional continuous space, which can be solved to obtain global optimal solution in polynomial time. Particularly, the linear knapsack problem can be solved analytically. Results show that as long as the knapsack problem has a unique solution, it is not NP-hard and its solution can be obtained analytically by the canonical duality theory. This research reveals, for the first time, the reason for NP-Hardness, i.e. the so-called NP-hardness is mainly due to certain symmetry such that the problem may have multiple solutions. Therefore, most of NP-hard problems are artificially proposed since the perfect symmetry does not exist in real world. Applications to topology optimization leads to a correct mathematical model and a powerful algorithm for 3-D structural optimal design. A powerful deterministic method and algorithm have been developed, which can be used for lightweight design of aircrafts and armored vehicles.


Subject Categories:

  • Operations Research
  • Theoretical Mathematics

Distribution Statement:

[A, Approved For Public Release]