共查询到20条相似文献,搜索用时 31 毫秒
1.
Gary A. Kochenberger Fred Glover Bahram Alidaee Cesar Rego 《Annals of Operations Research》2005,139(1):229-241
The vertex coloring problem has been the subject of extensive research for many years. Driven by application potential as
well as computational challenge, a variety of methods have been proposed for this difficult class of problems. Recent successes
in the use of the unconstrained quadratic programming (UQP) model as a unified framework for modeling and solving combinatorial
optimization problems have motivated a new approach to the vertex coloring problem. In this paper we present a UQP approach
to this problem and illustrate its attractiveness with preliminary computational experience. 相似文献
2.
This paper introduces a new model for the planar maximal covering location problem (PMCLP) under different block norms. The problem involves locating g facilities anywhere on the plane in order to cover the maximum number of n given demand points. The generalization, in this paper, is that the distance measures assigned to facilities are block norms of different types and different proximity measures. First, the PMCLP under different block norms is modelled as a maximum clique partition problem on an equivalent multi-interval graph. Then, the equivalent graph problem is modelled as an unconstrained binary quadratic problem (UQP). Both the maximum clique partition problem and the UQP are NP-hard problems; therefore, we solve the UQP format through a genetic algorithm heuristic. Computational examples are given. 相似文献
3.
《European Journal of Operational Research》2002,137(2):272-287
Many significant advances have been made in recent years for solving unconstrained binary quadratic programs (UQP). As a result, the size of problem instances that can be efficiently solved has grown from a hundred or so variables a few years ago to 2000 or 3000 variables today. These advances have motivated new applications of the model which, in turn, have created the need to solve even larger problems. In response to this need, we introduce several new “one-pass” heuristics for solving very large versions of this problem. Our computational experience on problems of up to 9000 variables indicates that these methods are both efficient and effective for very large problems. The significance of problems of this size is that they not only open the door to solving a much wider array of real world problems, but also that the standard linear mixed integer formulations of the nonlinear models involve over 40,000,000 variables and three times that many constraints. Our approaches can be used as stand-alone solution methods, or they can serve as procedures for quickly generating high quality starting points for other, more sophisticated methods. 相似文献
4.
In this paper an integrated problem formulated as an integer linear programming problem is presented to find an optimal solution to the cutting stock problem under particular pattern sequencing constraints. The solution uses a Lagrangian approach. The dual problem is solved using a modified subgradient method. A heuristic for the integrated problem is also presented. The computational results obtained from a set of unidimensional instances that use these procedures are reported. 相似文献
5.
Bahram Alidaee Gary Kochenberger Karen Lewis Mark Lewis Haibo Wang 《European Journal of Operational Research》2008
In recent years the unconstrained quadratic binary program has emerged as a unified modeling and solution framework for a variety of combinatorial optimization problems. Experience reported in the literature with several problem classes has demonstrated that this unified approach works surprisingly well in terms of solution quality and computational times, often rivaling and sometimes surpassing special purpose methods. In this paper we report on the application of this unified framework to set packing problems with a variety of coefficient distributions. Computational experience is reported illustrating the attractiveness of the approach. In particular, our results highlight both the effectiveness and robustness of our approach across a wide array of test problems. 相似文献
6.
7.
In this paper we consider linear fractional programming problem and look at its linear complementarity formulation. In the
literature, uniqueness of solution of a linear fractional programming problem is characterized through strong quasiconvexity.
We present another characterization of uniqueness through complementarity approach and show that the solution set of a fractional
programming problem is convex. Finally we formulate the complementarity condition as a set of dynamical equations and prove
certain results involving the neural network model. A computational experience is also reported.
相似文献
8.
G Scheithauer J Terno A Müller G Belov 《The Journal of the Operational Research Society》2001,52(12):1390-1401
When solving the one-dimensional cutting stock problem (1D CSP) as an integer linear programming problem one has to overcome computational difficulties arising from the integrality condition and a huge number of variables. In the Gilmore–Gomory approach the corresponding continuous relaxation is solved via column generation techniques followed by an appropriate rounding of the in general non-integer solution. Obviously, there is no guarantee of obtaining an optimal solution in this way but it is extremely effective in practice. However, in two- and three-dimensional cutting stock problems the heuristics are not so good which necessitates the research of effective exact methods. In this paper we present an exact solution approach for the 1D CSP which is based on a combination of the cutting plane method and the column generation technique. Results of extensive computational experiments are reported. 相似文献
9.
《European Journal of Operational Research》2006,171(3):797-810
The problem of routing and wavelength assignment in all-optical networks may be solved by a combined approach involving the computation of alternative routes for the lightpaths, followed by the solution of a partition colouring problem in a conflict graph. A new tabu search heuristic is also proposed for the partition colouring problem, which may be viewed as an extension of the graph colouring problem. Computational experiments are reported, showing that the tabu search heuristic outperforms the best heuristic for partition colouring by approximately 20% in the average and illustrating that the new approach for the problem of routing and wavelength assignment is more robust than a well established heuristic for this problem. 相似文献
10.
Julien Roland Yves De Smet José Rui Figueira 《4OR: A Quarterly Journal of Operations Research》2012,10(4):379-389
This paper deals with stability analysis in multi-objective combinatorial optimization problems. The stability radius of an efficient solution is defined as the maximal adjustment of the problem parameters such that this solution remains efficient. An algorithm based on inverse optimization is proposed to compute it. The adjustment is limited to the coefficients of the objective functions and measured by the Chebyshev norm. This approach is applied to randomly generated instances of the bi-objective knapsack problem and computational results are reported. Several illustrative examples are analyzed. 相似文献
11.
Dulce Rosas Jordi Castro Lídia Montero 《Computational Optimization and Applications》2009,44(2):289-313
The purpose of the traffic assignment problem is to obtain a traffic flow pattern given a set of origin-destination travel
demands and flow dependent link performance functions of a road network. In the general case, the traffic assignment problem
can be formulated as a variational inequality, and several algorithms have been devised for its efficient solution. In this
work we propose a new approach that combines two existing procedures: the master problem of a simplicial decomposition algorithm
is solved through the analytic center cutting plane method. Four variants are considered for solving the master problem. The
third and fourth ones, which heuristically compute an appropriate initial point, provided the best results. The computational
experience reported in the solution of real large-scale diagonal and difficult asymmetric problems—including a subset of the
transportation networks of Madrid and Barcelona—show the effectiveness of the approach. 相似文献
12.
Nizami A. Gasilov Şahin Emrah Amrahov 《Mathematical Methods in the Applied Sciences》2020,43(4):1825-1837
In this study, a new approach is developed to solve the initial value problem for interval linear differential equations. In the considered problem, the coefficients and the initial values are constant intervals. In the developed approach, there is no need to define a derivative for interval-valued functions. All derivatives used in the approach are classical derivatives of real functions. The reason for this is that the solution of the problem is defined as a bunch of real functions. Such a solution concept is compatible also with the robust stability concept. Sufficient conditions are provided for the solution to be expressed analytically. In addition, on a numerical example, the solution obtained by the proposed approach is compared with the solution obtained by the generalized Hukuhara differentiability. It is shown that the proposed approach gives a new type of solution. The main advantage of the proposed approach is that the solution to the considered interval initial value problem exists and is unique, as in the real case. 相似文献
13.
《Journal of Computational and Applied Mathematics》2005,176(1):203-214
We present a computational method for the solution of the third-order boundary value problem characterized by the well-known Falkner–Skan equation on a semi-infinite domain. Numerical treatments of this problem reported in the literature thus far are based on shooting and finite differences. While maintaining the simplicity of the shooting approach, the method presented in this paper uses a technique known as automatic differentiation, which is neither numerical nor symbolic. Using automatic differentiation, a Taylor series solution is constructed for the initial value problems by calculating the Taylor coefficients recursively. The effectiveness of the method is illustrated by applying it successfully to various instances of the Falkner–Skan equation. 相似文献
14.
We study the sensor cover energy problem (SCEP) in wireless communication—a difficult nonconvex problem with nonconvex constraints. A local approach based on DC programming called DCA was proposed by Astorino and Miglionico (Optim Lett 10(2):355–368, 2016) for solving this problem. In the present paper, we propose a global approach to (SCEP) based on the theory of monotonic optimization. By using an appropriate reformulation of (SCEP) we propose an algorithm for finding quickly a local optimal solution along with an efficient algorithm for computing a global optimal solution. Computational experiments are reported which demonstrate the practicability of the approach. 相似文献
15.
THE PREDICTION-CORRECTION LEGENDRE COLLOCATION METHOD FOR NONLINEAR EVOLUTIONARY PROBLEMS 总被引:1,自引:0,他引:1
Li-pingHe Shun-kaiSun 《计算数学(英文版)》2004,22(5):753-768
The initial-boundary value problem of Burgers equation is considered. A prediction-correction Legendre collocation scheme is presented, which is easy to be performed. Its numerical solution possesses the accuracy of second-order in time and higher order in space. Numerical results are reported, which show the high accuracy of this approach. The techniques used in this paper are also applicable to other nonlinear evolutionary problems. 相似文献
16.
《European Journal of Operational Research》2002,136(2):422-429
In most of the Goal Programming (GP) applications reported in the literature the election of the GP variant is made in a mechanistic way by the analyst. However, each variant implies a different preference structure and, thus, it should be chosen by the decision-maker. Moreover, the final solution of the problem depends critically on the variant chosen. In this paper, it is assumed that the use of a combination of GP variants may reflect in many cases more precisely the actual preferences of the decision-maker. In this way, a “sensitivity analysis” of the solution obtained as well as of the own model structure can be very helpful to let the decision-maker clarify his/her knowledge about the reality analysed. This type of problem requires a more general approach that leads to a GP formulation of the initial GP model. This type of Meta-GP approach is presented in this paper. 相似文献
17.
D. S. Filippychev 《Computational Mathematics and Modeling》2008,19(3):271-281
The dual operator is an analogue of the conjugate operator in linear theory. In this study the dual operator is applied to
a second-order differential equation describing the behavior of the zero-order boundary function in the boundary function
method used to derive the asymptotic solution of the singularly perturbed integro-differential plasma-sheath equation. This
approach produces is a three-point difference scheme. The results of a numerical solution of the Cauchy problem are reported.
__________
Translated from Prikladnaya Matematika i Informatika, No. 26, pp. 49–60, 2007. 相似文献
18.
A new augmented Lagrangian function for inequality constraints in nonlinear programming problems 总被引:2,自引:0,他引:2
In this paper, a new augmented Lagrangian function is introduced for solving nonlinear programming problems with inequality constraints. The relevant feature of the proposed approach is that, under suitable assumptions, it enables one to obtain the solution of the constrained problem by a single unconstrained minimization of a continuously differentiable function, so that standard unconstrained minimization techniques can be employed. Numerical examples are reported. 相似文献
19.
In this paper, we propose several heuristics for approximately solving the multiple-choice multidimensional knapsack problem (noted MMKP), an NP-Hard combinatorial optimization problem. The first algorithm is a constructive approach used especially for constructing an initial feasible solution for the problem. The second approach is applied in order to improve the quality of the initial solution. Finally, we introduce the main algorithm, which starts by applying the first approach and tries to produce a better solution to the MMKP. The last approach can be viewed as a two-stage procedure: (i) the first stage is applied in order to penalize a chosen feasible solution and, (ii) the second stage is used in order to normalize and to improve the solution given by the firs stage. The performance of the proposed approaches has been evaluated based problem instances extracted from the literature. Encouraging results have been obtained. 相似文献
20.
We propose a primal-dual continuation approach for the capacitated multi-facility Weber problem (CMFWP) based on its nonlinear
second-order cone program (SOCP) reformulation. The main idea of the approach is to reformulate the CMFWP as a nonlinear SOCP
with a nonconvex objective function, and then introduce a logarithmic barrier term and a quadratic proximal term into the
objective to construct a sequence of convexified subproblems. By this, this class of nondifferentiable and nonconvex optimization
problems is converted into the solution of a sequence of nonlinear convex SOCPs. In this paper, we employ the semismooth Newton
method proposed in Kanzow et al. (SIAM Journal of Optimization 20:297–320, 2009) to solve the KKT system of the resulting convex SOCPs. Preliminary numerical results are reported for eighteen test instances,
which indicate that the continuation approach is promising to find a satisfying suboptimal solution, even a global optimal
solution for some test problems. 相似文献