共查询到20条相似文献,搜索用时 16 毫秒
1.
We formulate the fixed-charge multiple knapsack problem (FCMKP) as an extension of the multiple knapsack problem (MKP). The Lagrangian relaxation problem is easily solved, and together with a greedy heuristic we obtain a pair of upper and lower bounds quickly. We make use of these bounds in the pegging test to reduce the problem size. We also present a branch-and-bound (B&B) algorithm to solve FCMKP to optimality. This algorithm exploits the Lagrangian upper bound as well as the pegging result for pruning, and at each terminal subproblem solve MKP exactly by invoking MULKNAP code developed by Pisinger [Pisinger, D., 1999. An exact algorithm for large multiple knapsack problems. European Journal of Operational Research 114, 528–541]. As a result, we are able to solve almost all test problems with up to 32,000 items and 50 knapsacks within a few seconds on an ordinary computing environment, although the algorithm remains some weakness for small instances with relatively many knapsacks. 相似文献
2.
Alex S. Fukunaga 《Annals of Operations Research》2011,184(1):97-119
The multiple knapsack problem (MKP) is a classical combinatorial optimization problem. A recent algorithm for some classes of the MKP is bin-completion, a bin-oriented, branch-and-bound algorithm. In this paper, we propose path-symmetry and path-dominance criteria for pruning nodes in the MKP branch-and-bound search space. In addition, we integrate the ??bound-and-bound?? upper bound validation technique used in previous MKP solvers. We show experimentally that our new MKP solver, which successfully integrates dominance based pruning, symmetry breaking, and bound-and-bound, significantly outperforms previous solvers on some classes of hard problem instances. 相似文献
3.
《European Journal of Operational Research》2006,171(2):693-707
We are concerned with a variation of the knapsack problem as well as of the knapsack sharing problem, where we are given a set of n items and a knapsack of a fixed capacity. As usual, each item is associated with its profit and weight, and the problem is to determine the subset of items to be packed into the knapsack. However, in the problem there are s players and the items are divided into s + 1 disjoint groups, Nk (k = 0, 1, … , s). The player k is concerned only with the items in N0 ∪ Nk, where N0 is the set of ‘common’ items, while Nk represents the set of his own items. The problem is to maximize the minimum of the profits of all the players. An algorithm is developed to solve this problem to optimality, and through a series of computational experiments, we evaluate the performance of the developed algorithm. 相似文献
4.
An exact algorithm for team orienteering problems 总被引:1,自引:1,他引:0
Sylvain Boussier Dominique Feillet Michel Gendreau 《4OR: A Quarterly Journal of Operations Research》2007,5(3):211-230
Optimising routing of vehicles constitutes a major logistic stake in many industrial contexts. We are interested here in the
optimal resolution of special cases of vehicle routing problems, known as team orienteering problems. In these problems, vehicles
are guided by a reward that can be collected from customers, while the length of routes is limited. The main difference with
classical vehicle routing problems is that not all customers have to be visited. The solution method we propose here is based
on a Branch & Price algorithm. It is, as far as we know, the first exact method proposed for such problems, except for a preliminary
work from Gueguen (Methodes de résolution exacte pour problémes de tournées de véhicules. Thése de doctorat, école Centrale
Paris 1999) and a work from Butt and Ryan (Comput Oper Res 26(4):427–441 1999). It permits to solve instances with up to 100
customers.
相似文献
5.
Peter Brucker 《Operations Research Letters》1984,3(3):163-166
An algorithm is presented which solves bounded quadratic optimization problems with n variables and one linear constraint in at most O(n) steps. The algorithm is based on a parametric approach combined with well-known ideas for constructing efficient algorithms. It improves an O(n log n) algorithm which has been developed for a more restricted case of the problem. 相似文献
6.
《Discrete Applied Mathematics》1986,14(3):283-293
We describe an approximate algorithm for a special ‘quadratic semi-assignment problem’ arising from ‘equipartition’ applications, where one wants to cluster n objects with given weights wi into p classes, so as to minimize the variance of the class-weights. The algorithm can be viewed both as a list scheduling method and as a special case of a heuristic procedure, due to Nemhauser and Carlson, for quadratic semi-assignment problems. Our main result is that the relative approximation error is O(1/n) when p and r = (maxwi)/(min wi) are bounded. 相似文献
7.
Cutting planes have been used with great success for solving mixed integer programs. In recent decades, many contributions have led to successive improvements in branch-and-cut methods which incorporate cutting planes in branch and bound algorithm. Using advances that have taken place over the years on 0–1 knapsack problem, we investigate an efficient approach for 0–1 programs with knapsack constraints as local structure. Our approach is based on an efficient implementation of knapsack separation problem which consists of the four phases: preprocessing, row generation, controlling numerical errors and sequential lifting. This approach can be used independently to improve formulations with cutting planes generated or incorporated in branch and cut to solve a problem. We show that this approach allows us to efficiently solve large-scale instances of generalized assignment problem, multilevel generalized assignment problem, capacitated \(p\)-median problem and capacitated network location problem to optimality. 相似文献
8.
The multiple knapsack problem denoted by MKP (B,S,rn,n) can be defined as follows. A set B of n items and a set S of rn knapsacks are given such that each item j has a profit pi and weight wj,and each knapsack i has a capacity Ci. The goal is to find a subset of items of maximum profit such that they have a feasible packing in the knapsacks. MKP (B,S,m,n) is strongly NP-Complete and no polynomial time approximation algorithm can have an approximation ratio better than 0.5. In the last ten years,semi-definite programming has been empolyed to solve some combinatorial problems successfully. This paper firstly presents a semi-definite relaxation algorithm (MKPS) for MKP (B,S,rn,n). It is proved that MKPS have a approximation ratio better than 0. 5 for a subclass of MKP (B,S,m,n) with n≤100, m≤5 and max^nj=1{wj}/min^mi=1={Ci}≤2/3. 相似文献
9.
《European Journal of Operational Research》1999,113(3):544-559
Facility location problems are often encountered in many areas such as distribution, transportation and telecommunication. We describe a new solution approach for the capacitated facility location problem in which each customer is served by a single facility. An important class of heuristic solution methods for these problems are Lagrangian heuristics which have been shown to produce high quality solutions and at the same time be quite robust. A primal heuristic, based on a repeated matching algorithm which essentially solves a series of matching problems until certain convergence criteria are satisfied, is incorporated into the Lagrangian heuristic. Finally, a branch-and-bound method, based on the Lagrangian heuristic is developed, and compared computationally to the commercial code CPLEX. The computational results indicate that the proposed method is very efficient. 相似文献
10.
《European Journal of Operational Research》1988,33(3):314-325
In this paper we present a lower bound for the capacitated warehouse location problem based upon lagrangean relaxation of a mixed-integer formulation of the problem. Feasible solution exclusion constraints are used together with problem reduction tests derived from both the original problem and the lagrangean relaxation.By incorporating the lower bound and the reduction tests into a tree search procedure we are able to solve problems involving up to 500 potential warehouse locations and 1000 customers. 相似文献
11.
We study a variation of the knapsack problem in which each item has a profit, a weight and a penalty; the sum of profits of the selected items minus the largest penalty associated with the selected items must be maximized. We present an ILP formulation and an exact optimization algorithm. 相似文献
12.
《Journal of Computational and Applied Mathematics》1997,78(1):9-18
This paper presents an efficient algorithm for solving the Lagrangean dual of nonlinear knapsack problems with additional nested constraints. The dual solution provides a feasible primal solution (if it exists) and associated lower and upper bounds on the optimal objective function value of the primal problem. Computational experience is cited indicating computation time, number of dual iterations, and “tightness” of the bounds. 相似文献
13.
The subgraph homeomorphism problem is to decide if there is an injective mapping of the vertices of a pattern graph into vertices of a host graph so that the edges of the pattern graph can be mapped into (internally) vertex-disjoint paths in the host graph. The restriction of subgraph homeomorphism where an injective mapping of the vertices of the pattern graph into vertices of the host graph is already given in the input instance is termed fixed-vertex subgraph homeomorphism.We show that fixed-vertex subgraph homeomorphism for a pattern graph on p vertices and a host graph on n vertices can be solved in time 2n−pnO(1) or in time 3n−pnO(1) and polynomial space. In effect, we obtain new non-trivial upper bounds on the time complexity of the problem of finding k vertex-disjoint paths and general subgraph homeomorphism. 相似文献
14.
An exact algorithm is presented for solving edge weighted graph partitioning problems. The algorithm is based on a branch and bound method applied to a continuous quadratic programming formulation of the problem. Lower bounds are obtained by decomposing the objective function into convex and concave parts and replacing the concave part by an affine underestimate. It is shown that the best affine underestimate can be expressed in terms of the center and the radius of the smallest sphere containing the feasible set. The concave term is obtained either by a constant diagonal shift associated with the smallest eigenvalue of the objective function Hessian, or by a diagonal shift obtained by solving a semidefinite programming problem. Numerical results show that the proposed algorithm is competitive with state-of-the-art graph partitioning codes. 相似文献
15.
In this Note, we introduce a partitioned Newton based method for solving nonlinear coupled systems arising in the numerical approximation of fluid–structure interaction problems. The originality of this Schur–Newton algorithm lies in the exact Jacobians evaluation involving the fluid–structure linearized subsystems which are here fully developed. To cite this article: M.Á. Fernández, M. Moubachir, C. R. Acad. Sci. Paris, Ser. I 336 (2003). 相似文献
16.
In this paper we propose a recursive quadratic programming algorithm for nonlinear programming problems with inequality constraints that uses as merit function a differentiable exact penalty function. The algorithm incorporates an automatic adjustment rule for the selection of the penalty parameter and makes use of an Armijo-type line search procedure that avoids the need to evaluate second order derivatives of the problem functions. We prove that the algorithm possesses global and superlinear convergence properties. Numerical results are reported. 相似文献
17.
E. Loli Piccolomini F. Zama 《Applied mathematics and computation》2011,217(24):10343-10354
In this paper we propose an iterative algorithm to solve large size linear inverse ill posed problems. The regularization problem is formulated as a constrained optimization problem. The dual Lagrangian problem is iteratively solved to compute an approximate solution. Before starting the iterations, the algorithm computes the necessary smoothing parameters and the error tolerances from the data.The numerical experiments performed on test problems show that the algorithm gives good results both in terms of precision and computational efficiency. 相似文献
18.
By the term “Bound and Bound” we define a particular tree-search technique for the ILP, which, for a maximization problem, makes use of a lower bound to determine the branches to follow in the decision tree. This technique is applied to the solution of the Zero-One Multiple Knapsack Problem and an algorithm is derived; an illustrative example of the procedure is provided. We present extensive computational results showing that the method is capable of solving problems up to 4 knapsacks and 200 variables with running times considerably smaller than those of the most commonly utilized algorithms. 相似文献
19.
20.
George Mavrotas José Rui Figueira Alexandros Antoniadis 《Journal of Global Optimization》2011,49(4):589-606
We propose a methodology for obtaining the exact Pareto set of Bi-Objective Multi-Dimensional Knapsack Problems, exploiting
the concept of core expansion. The core concept is effectively used in single objective multi-dimensional knapsack problems
and it is based on the “divide and conquer” principle. Namely, instead of solving one problem with n variables we solve several sub-problems with a fraction of n variables (core variables). In the multi-objective case, the
general idea is that we start from an approximation of the Pareto set (produced with the Multi-Criteria Branch and Bound algorithm,
using also the core concept) and we enrich this approximation iteratively. Every time an approximation is generated, we solve
a series of appropriate single objective Integer Programming (IP) problems exploring the criterion space for possibly undiscovered,
new Pareto Optimal Solutions (POS). If one or more new POS are found, we appropriately expand the already found cores and
solve the new core problems. This process is repeated until no new POS are found from the IP problems. The paper includes
an educational example and some experiments. 相似文献