http://www.se.cuhk.edu.hk/~nlip/
Discrete Optimization Solver
Duan Li
Office Tel. : (852) 3943-8323
Facsimile : (852) 2603-5505
Email-address: dli@se.cuhk.
Facsimile : (852) 2603-5505
Email-address: dli@se.cuhk.
perturbation function
Fig. 1
level cut l<=f(x)<=uLemma 1: the quality(tightness) of the dual search can be improved by raising the value of the lower objective level cut.
Lemma 2: at least one infeasible solution will be removed when placing a cut higher.
seperable NLP
Theorem 2: finds a opt sol or reports infeas in at most u0-l0 + 1 iterations.
polynomial 0-1 programming
Two-level reformulation:
y = prod (x_j) ={0,1} feasible partial solution
===================================================
Recent Progress in Nonlinear Integer Programming
Duan Li and Xiaoling Sun
Many decision making problems in real applications naturally result in optimization
formulations in a form of nonlinear integer programming. Exemplary areas include
capital budgeting, production planning, capacity planning, reliability networks and
chemical engineering process. Although the past few decades have witnessed tremendous
efforts in achieving theoretical and methodological development of (linear) integer
programming, nonlinear integer programming has not received enthusiastic attention,
partly due to its challenging feature resulted from a combination of combinatorial nature
and the nonlinearity inherent in the problem. Existing solution methods for solving
nonlinear programming problems have been mainly branch-and-bound methods and
dynamic programming methods or their combinations [1-5]. Computational experiments
have showed that these methods are only capable of handling small size problems.
Our main research goal has been to establish convergent duality theory and to develop
efficient solution algorithms for large-scale nonlinear integer programming problems.
The fundamental target underlying our theoretical development is to eliminate duality
gap in the classical Lagrangian dual formulation. We have developed nonlinear
Lagrangian theory that has yielded several new dual formulations with asymptotic zero
duality gap [6-8]. The key concept is the construction of a nonlinear support for a
nonconvex piecewise-constant perturbation function. Our numerical implementation of a
duality-gap reduction process relies on some novel “cutting” procedures. Performing
objective-level cut, objective contour cut or domain cut reshapes the perturbation
function, thus exposing eventually an optimal solution to the convex hull of a revised
perturbation function and guaranteeing a zero duality gap for a convergent Lagrangian
method. We have successfully implemented convergent Lagrangian algorithms for
nonlinear knapsack problems [9], nonlinear separable integer programming problems
[10] and concave knapsack problems [11]. Extensive computational experiment has been
carried out. The numerical results show that our proposed methods are capable of solving
large-scale problems with up to several thousand integer variables in reasonable
computation time. An internet-based computing interface is available for test problem
solving (http://www.se.cuhk.edu.hk/~nlip).
The convexity of a function could be hidden in an original representation space.
Convexification methods [14][15] have been proposed to transform a monotone function
into an equivalent convex function in a new representation space. Based on the developed
convexification transformation schemes and concave minimization techniques in global
optimization, we have developed a branch-and-bound method for monotone nonlinear
integer programming problems that often arise in complex reliability networks [12] and
allocation resource problems [13]. Successful applications have been observed in
optimization of reliability networks [16]. The convexification algorithm can find an
exact solution of optimization problems in complex networks with the largest size ever
reported in the literature.For whatever definition of a local minimum in integer programming, there often exist
multiple minima in integer programming problems, even in linear or strictly convex
integer programming problems. In this sense, solving an integer programming problem is
equivalent to searching for the global minimum among local minima. A global-descent
method enables us to “escape” from the current local minimum to a better local
minimum. By utilizing the concept of the filled function in continuous global
optimization, we have recently developed a local-search and global-descent method
([17][18]) for general nonlinear integer programming problems without any special
structure. Preliminary computational results are very promising with problem size up to
several hundred integer variables. An internet-based computing interface is available for
test problem solving (http://www.se.cuhk.edu.hk/~nlip).
[1] M. W. Cooper, The use of dynamic programming for the solution of a class of
nonlinear programming problems, Naval Research Logistics Quarterly 27, 89-95, 1980.
[2] M. W. Cooper, Survey of methods of pure nonlinear integer programming,
Management Science 27, 353-361, 1981.
[3] R. E. Marsten and T. L. Morin, A hybrid approach to discrete mathematical
programming, Mathematical Programming 14, 21-40, 1978.
[4] O. K. Gupta and A. Ravindran, Branch and bound experiments in convex nonlinear
integer programming, Management Science 31, 1533-1546, 1985.
[5] K. M. Bretthauer and B. Shetty, The nonlinear resource allocation problem,
Operations Research 43, 670-683, 1995.
[6] D. Li and D. J. White, P-th power Lagrangian method for integer programming,
Annals of Operations Research 98, 151-170, 2000.
[7] D. Li and X. L. Sun, Success guarantee of dual search in nonlinear integer
programming: p-th power Lagrangian method, Journal of Global Optimization 18, 235-
254, 2000.
[8] X. L. Sun and D. Li, Asymptotic strong duality for bounded integer programming: A
Logarithmic-exponential dual formulation, Mathematics of Operations Research 25, 625-
644, 2000.
[9] D. Li, X. L. Sun, J. Wang and K. McKinnon, A convergent Lagrangian and domain
cut method for nonlinear knapsack problems, Technical Report, SEEM2002-10,
November, 2002, Department of Systems Engineering & Engineering Management, The
Chinese University of Hong Kong.
[10] D. Li, J. Wang and X. L. Sun, Exact solution to separable nonlinear integer
programming: Convergent Lagrangian and objective level cut method, Technical Report,
SEEM2003-08, May, 2003, Department of Systems Engineering & Engineering
Management, The Chinese University of Hong Kong.
[11] X. L. Sun, F. L. Wang and D. Li, A Partition-and-Bound Algorithm for Concave
Knapsack Problems, Working Paper, 2003.
[12] S. G. Tzafestas, Optimization of system reliability: A survey of problems and
techniques, International Journal of Systems Science 11, 455-486, 1980.
[13] T. Ibaraki and N. Katoh, Resource Allocation Problems: Algorithmic Approaches,
MIT Press, Cambridge, Mass, 1988.[14] D. Li, X. L. Sun, M. P. Biswal, and F. Gao, Convexification, concavification and
monotonization in global optimization, Annals of Operations Research 105, 213-226,
2001.
[15] X. L. Sun, K. I. M. McKinnon and D. Li, A convexification method for a class of
global optimization problems with applications to reliability optimization, Journal of
Global Optimization 21, 185-199, 2001.
[16] D. Li, X. L. Sun and K. McKinnon, An exact solution method for reliability
optimization in complex systems, to appear in Annals of Operations Research, 2003.
[17] L. S. Zhang, C. K. Ng, D. Li, and W. W. Tian, A new filled function method for
global optimization, to appear in Journal of Global Optimization, 2002.
[18] C. K. Ng, L. S. Zhang and D. Li, Discrete filled function method for discrete global
optimization, submitted for publication, 2002.
没有评论:
发表评论