Library

An error occurred while sending the email. Please try again.

Proceed reservation?

Export
• 1
Unknown
Publication Date: 2021-12-09
Description: We report our progress on the project for solving larger scale quadratic assignment problems (QAPs). Our main approach to solve large scale NP-hard combinatorial optimization problems such as QAPs is a parallel branch-and-bound method efficiently implemented on a powerful computer system using the Ubiquity Generator(UG) framework that can utilize more than 100,000 cores. Lower bounding procedures incorporated in the branch-and-bound method play a crucial role in solving the problems. For a strong lower bounding procedure, we employ the Lagrangian doubly nonnegative (DNN) relaxation and the Newton-bracketing method developed by the authors’ group. In this report, we describe some basic tools used in the project including the lower bounding procedure and branching rules, and present some preliminary numerical results. Our next target problem is QAPs with dimension at least 50, as we have succeeded to solve tai30a and sko42 from QAPLIB for the first time.
Language: English
Type: reportzib , doc-type:preprint
Format: application/pdf
Library Location Call Number Volume/Issue/Year Availability
Others were also interested in ...
• 2
Unknown
Publication Date: 2022-05-13
Description: 二次割当問題は線形緩和が弱いことが知られ，強化のため多様な緩和手法が考案されているが，その一つである二重非負値計画緩和（ DNN 緩和）及びその解法として近年研究が進んでいるニュートン・ブラケット法を紹介し，それらに基づく分枝限定法の実装及び数値実験結果について報告する．
Language: Japanese
Type: reportzib , doc-type:preprint
Format: application/pdf
Library Location Call Number Volume/Issue/Year Availability
Others were also interested in ...
• 3
Electronic Resource
Springer
Algorithmica 1 (1986), S. 499-515
ISSN: 1432-0541
Keywords: Linear program ; Karmarkar's algorithm ; Optimal basis
Source: Springer Online Journal Archives 1860-2000
Topics: Computer Science , Mathematics
Notes: Abstract This paper establishes a sufficient condition for a variable of a linear program to be positive at all optimal solutions. A numerical test using the condition is incorporated into Karmarkar's new LP algorithm to determine columns of optimal basis. Experimental results on the test are also reported.
Type of Medium: Electronic Resource
Library Location Call Number Volume/Issue/Year Availability
Others were also interested in ...
• 4
Electronic Resource
Springer
Mathematical programming 12 (1977), S. 110-130
ISSN: 1436-4646
Source: Springer Online Journal Archives 1860-2000
Topics: Computer Science , Mathematics
Notes: Abstract A complementarity problem is said to be globally uniquely solvable (GUS) if it has a unique solution, and this property will not change, even if any constant term is added to the mapping generating the problem. A characterization of the GUS property which generalizes a basic theorem in linear complementarity theory is given. Known sufficient conditions given by Cottle, Karamardian, and Moré for the nonlinear case are also shown to be generalized. In particular, several open questions concerning Cottle's condition are settled and a new proof is given for the sufficiency of this condition. A simple characterization for the two-dimensional case and a necessary condition for then-dimensional case are also given.
Type of Medium: Electronic Resource
Library Location Call Number Volume/Issue/Year Availability
Others were also interested in ...
• 5
Electronic Resource
Springer
Mathematical programming 62 (1993), S. 85-93
ISSN: 1436-4646
Keywords: Bigℳ ; affine scaling algorithm ; linear program ; interior point algorithm ; infeasibility ; global convergence
Source: Springer Online Journal Archives 1860-2000
Topics: Computer Science , Mathematics
Notes: Abstract When we apply the affine scaling algorithm to a linear program, we usually construct an artificial linear program having an interior feasible solution from which the algorithm starts. The artificial linear program involves a positive number called the bigℳ. Theoretically, there exists anℳ * such that the original problem to be solved is equivalent to the artificial linear program ifℳ 〉ℳ *. Practically, however, such anℳ * is unknown and a safe estimate ofℳ is often too large. This paper proposes a method of updatingℳ to a suitable value during the iteration of the affine scaling algorithm. Asℳ becomes large, the method gives information on infeasibility of the original problem or its dual.
Type of Medium: Electronic Resource
Library Location Call Number Volume/Issue/Year Availability
Others were also interested in ...
• 6
Electronic Resource
Springer
Mathematical programming 80 (1998), S. 129-160
ISSN: 1436-4646
Keywords: Semidefinite programming ; Infeasible-interior-point method ; Predictor—correctormethod ; Superlinear convergence ; Primal—dual nondegeneracy
Source: Springer Online Journal Archives 1860-2000
Topics: Computer Science , Mathematics
Notes: Abstract An example of an SDP (semidefinite program) exhibits a substantial difficulty in proving the superlinear convergence of a direct extension of the Mizuno—Todd—Ye type predictor—corrector primal-dual interior-point method for LPs (linear programs) to SDPs, and suggests that we need to force the generated sequence to converge to a solution tangentially to the central path (or trajectory). A Mizuno—Todd—Ye type predictor—corrector infeasible-interior-point algorithm incorporating this additional restriction for monotone SDLCPs (semidefinite linear complementarity problems) enjoys superlinear convergence under strict complementarity and nondegeneracy conditions. © 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.
Type of Medium: Electronic Resource
Library Location Call Number Volume/Issue/Year Availability
Others were also interested in ...
• 7
Electronic Resource
Springer
Mathematical programming 16 (1979), S. 37-62
ISSN: 1436-4646
Keywords: Roots of Polynomials ; Fixed Point Computing Methods ; Complementary Pivoting Methods ; Piecewise Linear Homotopy
Source: Springer Online Journal Archives 1860-2000
Topics: Computer Science , Mathematics
Notes: Abstract This paper presents a constructive method which gives, for any polynomialF(Z) of the degreen, approximate values of all the roots ofF(Z).. The point of the method is on the use of a piecewise linear function $$\bar H$$ (Z, t) which approximates a homotopyH(Z, t) betweenF(Z) and a polynomialG(Z) of the degreen withn known simple roots. It is shown that the set of solutions to $$\bar H$$ (Z, t) = 0 includesn distinct paths,m of which converges to a root ofF(Z) if and only if the root has the multiplicitym. Starting from givenn roots ofG(Z), a complementary pivot algorithm generates thosen paths.
Type of Medium: Electronic Resource
Library Location Call Number Volume/Issue/Year Availability
Others were also interested in ...
• 8
Electronic Resource
Springer
Mathematical programming 44 (1989), S. 1-26
ISSN: 1436-4646
Keywords: Linear complementarity problem ; polynomial-time algorithm ; path of centers ; Karmarkar's algorithm
Source: Springer Online Journal Archives 1860-2000
Topics: Computer Science , Mathematics
Notes: Abstract Given ann × n matrixM and ann-dimensional vectorq, the problem of findingn-dimensional vectorsx andy satisfyingy = Mx + q, x ≥ 0,y ≥ 0,x i y i = 0 (i = 1, 2,⋯,n) is known as a linear complementarity problem. Under the assumption thatM is positive semidefinite, this paper presents an algorithm that solves the problem in O(n 3 L) arithmetic operations by tracing the path of centers,{(x, y) ∈ S: x i y i =μ (i = 1, 2,⋯,n) for some μ 〉 0} of the feasible regionS = {(x, y) ≥ 0:y = Mx + q}, whereL denotes the size of the input data of the problem.
Type of Medium: Electronic Resource
Library Location Call Number Volume/Issue/Year Availability
Others were also interested in ...
• 9
Electronic Resource
Springer
Mathematical programming 65 (1994), S. 43-72
ISSN: 1436-4646
Keywords: Monotone complementarity problem ; Interior-point algorithm ; Potential reduction algorithm ; Infeasibility ; Global convergence
Source: Springer Online Journal Archives 1860-2000
Topics: Computer Science , Mathematics
Notes: Abstract This paper presents a wide class of globally convergent interior-point algorithms for the nonlinear complementarity problem with a continuously differentiable monotone mapping in terms of a unified global convergence theory given by Polak in 1971 for general nonlinear programs. The class of algorithms is characterized as: Move in a Newton direction for approximating a point on the path of centers of the complementarity problem at each iteration. Starting from a strictly positive but infeasible initial point, each algorithm in the class either generates an approximate solution with a given accuracy or provides us with information that the complementarity problem has no solution in a given bounded set. We present three typical examples of our interior-point algorithms, a horn neighborhood model, a constrained potential reduction model with the use of the standard potential function, and a pure potential reduction model with the use of a new potential function.
Type of Medium: Electronic Resource
Library Location Call Number Volume/Issue/Year Availability
Others were also interested in ...
• 10
Electronic Resource
Springer
Mathematical programming 89 (2000), S. 79-111
ISSN: 1436-4646
Keywords: Key words: nonconvex quadratic optimization problem – semidefinite programming – linear matrix inequality – global optimization – SDP relaxation – semi-infinite LP relaxation – interior-point method
Source: Springer Online Journal Archives 1860-2000
Topics: Computer Science , Mathematics
Notes: Abstract. Based on the authors’ previous work which established theoretical foundations of two, conceptual, successive convex relaxation methods, i.e., the SSDP (Successive Semidefinite Programming) Relaxation Method and the SSILP (Successive Semi-Infinite Linear Programming) Relaxation Method, this paper proposes their implementable variants for general quadratic optimization problems. These problems have a linear objective function c T x to be maximized over a nonconvex compact feasible region F described by a finite number of quadratic inequalities. We introduce two new techniques, “discretization” and “localization,” into the SSDP and SSILP Relaxation Methods. The discretization technique makes it possible to approximate an infinite number of semi-infinite SDPs (or semi-infinite LPs) which appeared at each iteration of the original methods by a finite number of standard SDPs (or standard LPs) with a finite number of linear inequality constraints. We establish:¶•Given any open convex set U containing F, there is an implementable discretization of the SSDP (or SSILP) Relaxation Method which generates a compact convex set C such that F⊆C⊆U in a finite number of iterations.¶The localization technique is for the cases where we are only interested in upper bounds on the optimal objective value (for a fixed objective function vector c) but not in a global approximation of the convex hull of F. This technique allows us to generate a convex relaxation of F that is accurate only in certain directions in a neighborhood of the objective direction c. This cuts off redundant work to make the convex relaxation accurate in unnecessary directions. We establish:¶•Given any positive number ε, there is an implementable localization-discretization of the SSDP (or SSILP) Relaxation Method which generates an upper bound of the objective value within ε of its maximum in a finite number of iterations.
Type of Medium: Electronic Resource
Library Location Call Number Volume/Issue/Year Availability
Others were also interested in ...
Close ⊗