【主题】《Multi-Exchange (r-flip) Neighborhood Structure for Pseudo-Boolean Optimization》 及 《A Unified Modeling and Solution Framework for Combinatorial Optimi
【时间】2005-5-23上午10:30
【地点】清华经管学院 伟伦楼北406
【语言】英文
【内容摘要】
《Multi-Exchange (r-flip) Neighborhood Structure for Pseudo-Boolean Optimization》
Bahram Alidaee, Gary Kochenberger, Haibo Wang, Hongman Gao
(Estimated 45 minutes, Logistics)
In this paper, Pseudo-Boolean optimization is considered. A definition of partial derivatives is presented. Based on such derivatives, a multi-exchange neighborhood strategy is presented. For several decades neighborhood strategies, such as r-opt and r-flip rules, have been used for solving difficult combinatorial optimization. In recent years, such strategies have become even more popular. However, in all of the previous researches the presented strategies are highly problem specific. In this paper, based on the presented partial derivatives we give an r-flip strategy that can be used in a wide variety of optimization problems.
Compound move strategies, such as Strategic Oscillation and Filtration and Sequential Fan (F&F) that have been developed in recent years, may be considered to contain multi-exchange strategies as special cases. Such compound move strategies have shown to be very effective in solving discrete optimization. We use a simple F&F strategy as well as a 2-flip move strategy for solution of 3-SAT problem which may be formulated as Pseudo-Boolean optimization. We use our algorithms to solve problems from DIMACS series of benchmarks and compare the result with GRASP. Our results show for quick solutions a combination of 1 and 2-flip search is effective. However, F&F strategy are very effective with reasonable use of computer time for 3-SAT problems.
《A Unified Modeling and Solution Framework for Combinatorial Optimization Problems》
Gary Kochenberger, Fred Glover, Bahram Alidaee and Haibo Wang
(Estimated 45 minutes, general business)
In recent years the unconstrained quadratic binary program (UQP) has emerged as a unified framework for modeling and solving a wide variety of combinatorial optimization problems. This talk gives an introduction to this evolving area. The methodology is illustrated by several examples and substantial computational experience demonstrating the viability and robustness of the approach.
【主讲人简介】Dr. Gary Kochenberger
the director of Decision Sciences,Business School of University of Colorado at Denver
former Dean of the Business School of Pennsylvania State University
former Dean of the Business School of University of Colorado at Denver
the Program Chair of INFORMS Annual Meeting 2004
个人网页：http://www.cudenver.edu/Academics/Colleges/Business/Faculty/Decision+Sciences/gKochenberger.htm
Dr. Bahram Alidaee
Interim Director of the Hearin Center for Enterprise Science since 2004
Associate Professor of Operations Management,
School of Business Administration,
The University of Mississippi
个人网页：http://faculty.bus.olemiss.edu/balidaee/ | 
