Optimization Algorithm Based on the Less Flexibility First Principle and Its Practical Applications
(Y. L. Wu)

The academia known NP-hard problem can be considered a byname of those “hardest” optimization problems. NP-hard problems are almost ubiquitous, from classical graph theory, sequencing, coding problems, to our many real-life related practical problems like air-flight/shop scheduling, ship cargo packing and so on. To solve these difficult optimization problems, many optimization heuristics emulate certain natural optimization processes, from biology evolution, mathematics, physics, neural system and statistic mechanics, etc. Since most of these nature-process emulated algorithms involve randomness-based non-deterministic procedures that will take quite large CPU resources for large problem instances, they are not necessarily practical for our today’s real-life problems that tend to have larger and larger input sizes. For example, in a simulated annealing algorithm for the deep sub-micron placement and routing problems, multiple objectives and constraints need to be integrated together in the cost function, which might unfortunately cause mutual conflicts on the penalty function and jeopardize the searching conversion for global optimization solutions. In this proposal, we are proposing a newly invented deterministic heuristic, Less Flexibility First (LFF) methodology, which can efficiently reflect the multiple optimization goals more effectively and thus should be able to overcome the drawbacks of the non-deterministic based methods. We will apply this new technique for solving 3D ship-cargo packing optimization and VLSI EDA (Electronic Design Automation) problems.