-
作者：Markót, MC; Fernández, J; Casado, LG; Csendes, T
作者单位：Szeged University; Hungarian Academy of Sciences; European Space Agency; European Space Research & Technology Centre; University of Murcia; Universidad de Almeria; Szeged University
摘要：Interval analysis is a powerful tool which allows to design branch-and-bound algorithms able to solve many global optimization problems. In this paper we present new adaptive multisection rules which enable the algorithm to choose the proper multisection type depending on simple heuristic decision rules. Moreover, for the selection of the next box to be subdivided, we investigate new criteria. Both the adaptive multisection and the subinterval selection rules seem to be specially suitable for ...
-
作者：Ye, YY
作者单位：Stanford University
摘要：We present complexity results on solving real-number standard linear programs LP(A, b, c), where the constraint matrix A is an element of R-m x n, the right-hand-side vector b is an element of R-m and the objective coefficient vector c is an element of R-n are real. In particular, we present a two-layered interior-point method and show that LP(A, b, 0), i.e., the linear feasibility problem Ax = b and x >= 0, can be solved in in O(n(2.5)c(A)) interior-point method iterations. Here 0 is the vect...
-
作者：Ralphs, TK; Galati, MV
作者单位：Lehigh University; SAS Institute Inc
摘要：Decomposition algorithms such as Lagrangian relaxation and Dantzig-Wolfe decomposition are well-known methods that can be used to generate bounds for mixed-integer linear programming problems. Traditionally, these methods have been viewed as distinct from polyhedral methods, in which bounds are obtained by dynamically generating valid inequalities to strengthen an initial linear programming relaxation. Recently, a number of authors have proposed methods for integrating dynamic cut generation w...
-
作者：Adler, I; Cottle, RW; Verma, S
作者单位：University of California System; University of California Berkeley; Stanford University
摘要：In this paper, we establish a significant matrix class inclusion that seems to have been overlooked in the literature of the linear complementarity problem. We show that P-*,P- the class of sufficient matrices, is a subclass of L. In the course of demonstrating this inclusion, we introduce other new matrix classes that forge interesting new connections between known matrix classes.
-
作者：Griva, I; Polyak, RA
作者单位：George Mason University; George Mason University; George Mason University
摘要：In this paper we developed a general primal-dual nonlinear rescaling method with dynamic scaling parameter update (PDNRD) for convex optimization. We proved the global convergence, established 1.5-Q-superlinear rate of convergence under the standard second order optimality conditions. The PDNRD was numerically implemented and tested on a number of nonlinear problems from COPS and CUTE sets. We present numerical results, which strongly corroborate the theory.
-
作者：Kaul, H; Jacobson, SH
作者单位：University of Illinois System; University of Illinois Urbana-Champaign; University of Illinois System; University of Illinois Urbana-Champaign
摘要：The Kauffman NK model has been used in theoretical biology, physics and business organizations to model complex systems with interacting components. Recent NK model results have focused on local optima. This paper analyzes global optima of the NK model. The resulting global optimization problem is transformed into a stochastic network model that is closely related to two well-studied problems in operations research. This leads to applicable strategies for explicit computation of bounds on the ...
-
作者：Frangioni, A; Gentile, C
作者单位：University of Pisa; Consiglio Nazionale delle Ricerche (CNR); Istituto di Analisi dei Sistemi ed Informatica Antonio Ruberti (IASI-CNR)
摘要：We show that the convex envelope of the objective function of Mixed-Integer Programming problems with a specific structure is the perspective function of the continuous part of the objective function. Using a characterization of the subdifferential of the perspective function, we derive perspective cuts, a family of valid inequalities for the problem. Perspective cuts can be shown to belong to the general family of disjunctive cuts, but they do not require the solution of a potentially costly ...
