共查询到20条相似文献,搜索用时 46 毫秒
1.
Gio K. Kao Edward C. Sewell Sheldon H. Jacobson Shane N. Hall 《Computational Optimization and Applications》2012,51(3):1253-1274
The paper proposes a new exact approach, based on a Branch, Bound, and Remember (BB&R) algorithm that uses the Cyclic Best
First Search (CBFS) strategy, for the 1|r
i
|∑U
i
scheduling problem, a single machine scheduling problem, where the objective is to find a schedule with the minimum number
of tardy jobs. The search space is reduced using new and improved dominance properties and tighter upper bounds, based on
a new dynamic programming algorithm. Computational results establish the effectiveness of the BB&R algorithm with CBFS for
a broad spectrum of problem instances. In particular, this algorithm was able to solve all problems instances, up to 300 jobs,
while existing best known algorithms only solve problems instances up to 200 jobs. Furthermore, the BB&R algorithm with CBFS
runs one to two orders of magnitude faster than the current best known algorithm on comparable instances. 相似文献
2.
A (v,k,t)-covering design is a collection of k-subsets (called blocks) of a v-set V{\mathcal{V}} such that every t-subset of V{\mathcal{V}} is contained in at least one block. Given v, k and t, the goal of the covering design problem is to find a covering made of a minimum number of blocks. In this paper, we present
a new tabu algorithm for tackling this problem. Our algorithm exploits a new implementation designed in order to evaluate
efficiently the performance of the neighbors of the current configuration. The new implementation is much less space-consuming
than the currently used technique, making it possible to tackle much larger problem instances. It is also significantly faster.
Thanks to these improved data structures, our tabu algorithm was able to improve the upper bound of more than 50 problem instances. 相似文献
3.
Clemens Nothegger Alfred Mayer Andreas Chwatal Günther R. Raidl 《Annals of Operations Research》2012,194(1):325-339
In this work we present a new approach to tackle the problem of Post Enrolment Course Timetabling as specified for the International Timetabling Competition 2007 (ITC2007), competition track 2. The heuristic procedure is
based on Ant Colony Optimization (ACO) where artificial ants successively construct solutions based on pheromones (stigmergy) and local information. The key feature of our algorithm is the use of two distinct but simplified pheromone matrices
in order to improve convergence but still provide enough flexibility for effectively guiding the solution construction process.
We show that by parallelizing the algorithm we can improve the solution quality significantly. We applied our algorithm to
the instances used for the ITC2007. The results document that our approach is among the leading algorithms for this problem;
in all cases the optimal solution could be found. Furthermore we discuss the characteristics of the instances where the algorithm
performs especially well. 相似文献
4.
In this paper, we approximately solve the multiple-choice multi-dimensional knapsack problem. We propose an algorithm which
is based upon reactive local search and where an explicit check for the repetition of configurations is added to the local
search. The algorithm starts by an initial solution and improved by using a fast iterative procedure. Later, both deblocking and degrading procedures are introduced in order (i) to escape to local optima and, (ii) to introduce diversification in the search space.
Finally, a memory list is applied in order to forbid the repetition of configurations. The performance of the proposed approaches
has been evaluated on several problem instances. Encouraging results have been obtained. 相似文献
5.
The field of cluster analysis is primarily concerned with the sorting of data points into different clusters so as to optimize
a certain criterion. Rapid advances in technology have made it possible to address clustering problems via optimization theory.
In this paper, we present a global optimization algorithm to solve the hard clustering problem, where each data point is to be assigned to exactly one cluster. The hard clustering problem is formulated
as a nonlinear program, for which a tight linear programming relaxation is constructed via the Reformulation-Linearization
Technique (RLT) in concert with additional valid inequalities that serve to defeat the inherent symmetry in the problem. This
construct is embedded within a specialized branch-and-bound algorithm to solve the problem to global optimality. Pertinent
implementation issues that can enhance the efficiency of the branch-and-bound algorithm are also discussed. Computational
experience is reported using several standard data sets found in the literature as well as using synthetically generated larger
problem instances. The results validate the robustness of the proposed algorithmic procedure and exhibit its dominance over
the popular k-means clustering technique. Finally, a heuristic procedure to obtain a good quality solution at a relative ease of computational
effort is also described. 相似文献
6.
Heuristic Procedures for the Capacitated Vehicle Routing Problem 总被引:6,自引:0,他引:6
In this paper we present two new heuristic procedures for the Capacitated Vehicle Routing Problem (CVRP). The first one solves the problem from scratch, while the second one uses the information provided by a strong linear relaxation of the original problem. This second algorithm is designed to be used in a branch and cut approach to solve to optimality CVRP instances. In both heuristics, the initial solution is improved using tabu search techniques. Computational results over a set of known instances, most of them with a proved optimal solution, are given. 相似文献
7.
The Capacitated Facility Location Problem (CFLP) is to locate a set of facilities with capacity constraints, to satisfy at the minimum cost the order-demands of a set of
clients. A multi-source version of the problem is considered in which each client can be served by more than one facility.
In this paper we present a reformulation of the CFLP based on Mixed Dicut Inequalities, a family of minimum knapsack inequalities of a mixed type, containing both binary and continuous (flow) variables. By aggregating
flow variables, any Mixed Dicut Inequality turns into a binary minimum knapsack inequality with a single continuous variable.
We will refer to the convex hull of the feasible solutions of this minimum knapsack problem as the Mixed Dicut polytope.
We observe that the Mixed Dicut polytope is a rich source of valid inequalities for the CFLP: basic families of valid CFLP inequalities, like Variable Upper Bounds, Cover, Flow Cover and Effective Capacity Inequalities, are valid for the Mixed
Dicut polytope. Furthermore we observe that new families of valid inequalities for the CFLP can be derived by the lifting procedures studied for the minimum knapsack problem with a single continuous variable.
To deal with large-scale instances, we have developed a Branch-and-Cut-and-Price algorithm, where the separation algorithm
consists of the complete enumeration of the facets of the Mixed Dicut polytope for a set of candidate Mixed Dicut Inequalities.
We observe that our procedure returns inequalities that dominate most of the known classes of inequalities presented in the
literature. We report on computational experience with instances up to 1000 facilities and 1000 clients to validate the approach. 相似文献
8.
Artur Alves Pessoa Peter M. Hahn Monique Guignard Yi-Rong Zhu 《European Journal of Operational Research》2010
In this paper, we propose two exact algorithms for the GQAP (generalized quadratic assignment problem). In this problem, given M facilities and N locations, the facility space requirements, the location available space, the facility installation costs, the flows between facilities, and the distance costs between locations, one must assign each facility to exactly one location so that each location has sufficient space for all facilities assigned to it and the sum of the products of the facility flows by the corresponding distance costs plus the sum of the installation costs is minimized. This problem generalizes the well-known quadratic assignment problem (QAP). Both exact algorithms combine a previously proposed branch-and-bound scheme with a new Lagrangean relaxation procedure over a known RLT (Reformulation-Linearization Technique) formulation. We also apply transformational lower bounding techniques to improve the performance of the new procedure. We report detailed experimental results where 19 out of 21 instances with up to 35 facilities are solved in up to a few days of running time. Six of these instances were open. 相似文献
9.
F. Sibel Salman Jayant R. Kalagnanam Sesh Murthy Andrew Davenport 《Journal of Heuristics》2002,8(2):215-239
For hard optimization problems, it is difficult to design heuristic algorithms which exhibit uniformly superior performance for all problem instances. As a result it becomes necessary to tailor the algorithms based on the problem instance. In this paper, we introduce the use of a cooperative problem solving team of heuristics that evolves algorithms for a given problem instance. The efficacy of this method is examined by solving six difficult instances of a bicriteria sparse multiple knapsack problem. Results indicate that such tailored algorithms uniformly improve solutions as compared to using predesigned heuristic algorithms. 相似文献
10.
An exact algorithm for the vehicle routing problem based on the set partitioning formulation with additional cuts 总被引:6,自引:0,他引:6
This paper presents a new exact algorithm for the Capacitated Vehicle Routing Problem (CVRP) based on the set partitioning
formulation with additional cuts that correspond to capacity and clique inequalities. The exact algorithm uses a bounding
procedure that finds a near optimal dual solution of the LP-relaxation of the resulting mathematical formulation by combining
three dual ascent heuristics. The first dual heuristic is based on the q-route relaxation of the set partitioning formulation of the CVRP. The second one combines Lagrangean relaxation, pricing
and cut generation. The third attempts to close the duality gap left by the first two procedures using a classical pricing
and cut generation technique. The final dual solution is used to generate a reduced problem containing only the routes whose
reduced costs are smaller than the gap between an upper bound and the lower bound achieved. The resulting problem is solved
by an integer programming solver. Computational results over the main instances from the literature show the effectiveness
of the proposed algorithm.
相似文献
11.
In this paper, we investigate a resource-constrained project scheduling problem with flexible resources. This is an \(\mathcal {NP}\)-hard combinatorial optimization problem that consists of scheduling a set of activities requiring specific resource units of several skills. The goal is to minimize the makespan of the project. We propose a biased random-key genetic algorithm for computing feasible solutions for the referred problem. We study different decoding mechanisms: an already existing method in the literature, a new adapted serial scheduling generation scheme, and a combination of both. The new procedure is tested using a set of benchmark instances of the problem. The results provide strong evidence that the new heuristic is robust and yields high-quality feasible solutions. 相似文献
12.
Mauricio G. C. Resende Rodrigo F. Toso José Fernando Gonçalves Ricardo M. A. Silva 《Optimization Letters》2012,6(4):605-619
We present a biased random-key genetic algorithm (BRKGA) for finding small covers of computationally difficult set covering
problems that arise in computing the 1-width of incidence matrices of Steiner triple systems. Using a parallel implementation
of the BRKGA, we compute improved covers for the two largest instances in a standard set of test problems used to evaluate
solution procedures for this problem. The new covers for instances A
405 and A
729 have sizes 335 and 617, respectively. On all other smaller instances our algorithm consistently produces covers of optimal
size. 相似文献
13.
《European Journal of Operational Research》2006,169(2):638-653
In the last few decades, several effective algorithms for solving the resource-constrained project scheduling problem have been proposed. However, the challenging nature of this problem, summarised in its strongly NP-hard status, restricts the effectiveness of exact optimisation to relatively small instances. In this paper, we present a new meta-heuristic for this problem, able to provide near-optimal heuristic solutions for relatively large instances. The procedure combines elements from scatter search, a generic population-based evolutionary search method, and from a recently introduced heuristic method for the optimisation of unconstrained continuous functions based on an analogy with electromagnetism theory. We present computational experiments on standard benchmark datasets, compare the results with current state-of-the-art heuristics, and show that the procedure is capable of producing consistently good results for challenging instances of the resource-constrained project scheduling problem. We also demonstrate that the algorithm outperforms state-of-the-art existing heuristics. 相似文献
14.
Approximation Algorithms for MAX 4-SAT and Rounding Procedures for Semidefinite Programs 总被引:1,自引:0,他引:1
Karloff and Zwick obtained recently an optimal 7/8-approximation algorithm for MAX 3-SAT. In an attempt to see whether similar methods can be used to obtain a 7/8-approximation algorithm for MAX SAT, we consider the most natural generalization of MAX 3-SAT, namely MAX 4-SAT. We present a semidefinite programming relaxation of MAX 4-SAT and a new family of rounding procedures that try to cope well with clauses of various sizes. We study the potential, and the limitations, of the relaxation and of the proposed family of rounding procedures using a combination of theoretical and experimental means. We select two rounding procedures from the proposed family of rounding procedures. Using the first rounding procedure we seem to obtain an almost optimal 0.8721-approximation algorithm for MAX 4-SAT. Using the second rounding procedure we seem to obtain an optimal 7/8-approximation algorithm for satisfiable instances of MAX 4-SAT. On the other hand, we show that no rounding procedure from the family considered can be shown, using the current techniques, to yield an approximation algorithm for MAX 4-SAT whose performance guarantee for all instances of the problem is greater than 0.8724. We also show that the integrality ratio of the proposed relaxation, as a relaxation of MAX {1, 4}-SAT, is at most 0.8754.The 0.8721-approximation for MAX 4-SAT that we seem to obtain substantially improves the performance guarantees of all previous algorithms suggested for the problem. It is extremely close to being optimal as a (7/8 + ε)-approximation algorithm for MAX 4-SAT, for any fixed ε > 0, would imply that P = NP. Our investigation also indicates, however, that additional ideas are required in order to obtain optimal 7/8-approximation algorithms for MAX 4-SAT and MAX SAT.Although most of this paper deals specifically with the MAX 4-SAT problem, we believe that the new family of rounding procedures introduced and the methodology used in the design and in the analysis of the various rounding procedures considered have a much wider range of applicability. 相似文献
15.
The field of cluster analysis is primarily concerned with the partitioning of data points into different clusters so as to
optimize a certain criterion. Rapid advances in technology have made it possible to address clustering problems via optimization
theory. In this paper, we present a global optimization algorithm to solve the fuzzy clustering problem, where each data point is to be assigned to (possibly) several clusters, with a membership grade assigned
to each data point that reflects the likelihood of the data point belonging to that cluster. The fuzzy clustering problem
is formulated as a nonlinear program, for which a tight linear programming relaxation is constructed via the Reformulation-Linearization
Technique (RLT) in concert with additional valid inequalities. This construct is embedded within a specialized branch-and-bound
(B&B) algorithm to solve the problem to global optimality. Computational experience is reported using several standard data
sets from the literature as well as using synthetically generated larger problem instances. The results validate the robustness
of the proposed algorithmic procedure and exhibit its dominance over the popular fuzzy c-means algorithmic technique and the
commercial global optimizer BARON. 相似文献
16.
The Social Golfer Problem (SGP) is a combinatorial optimization problem that exhibits a lot of symmetry and has recently attracted
significant attention. In this paper, we present a new greedy heuristic for the SGP, based on the intuitive concept of freedom among players. We use this heuristic in a complete backtracking search, and match the best current results of constraint
solvers for several SGP instances with a much simpler method. We then use the main idea of the heuristic to construct initial
configurations for a metaheuristic approach, and show that this significantly improves results obtained by local search alone.
In particular, our method is the first metaheuristic technique that can solve the original problem instance optimally. We
show that our approach is also highly competitive with other metaheuristic and constraint-based methods on many other benchmark
instances from the literature. 相似文献
17.
Cristina Bazgan W. Fernandez de la Vega Marek Karpinski 《Random Structures and Algorithms》2003,23(1):73-91
It is known that large fragments of the class of dense Minimum Constraint Satisfaction (MIN‐CSP) problems do not have polynomial time approximation schemes (PTASs) contrary to their Maximum Constraint Satisfaction analogs. In this paper we prove, somewhat surprisingly, that the minimum satisfaction of dense instances of kSAT ‐formulas, and linear equations mod 2, Ek‐LIN2, do have PTASs for any k. The MIN‐Ek‐LIN2 problems are equivalent to the k‐ary versions of the Nearest Codeword problem, the problem which is known to be exceedingly hard to approximate on general instances. The method of solution of the above problems depends on the development of a new density sampling technique for k‐uniform hypergraphs which could be of independent interest. © 2003 Wiley Periodicals, Inc. Random Struct. Alg., 23: 73–91, 2003 相似文献
18.
Sandra Ulrich Ngueveu Christian Prins Roberto Wolfler Calvo 《4OR: A Quarterly Journal of Operations Research》2010,8(4):387-406
The m-Peripatetic Vehicle Routing Problem (m-PVRP) consists in finding a set of routes of minimum total cost over m periods so that two customers are never sequenced consecutively during two different periods. It models for example money
transports or cash machines supply, and the aim is to minimize the total cost of the routes chosen. The m-PVRP can be considered as a generalization of two well-known NP-hard problems: the Vehicle Routing Problem (VRP or 1-PVRP)
and the m-Peripatetic Salesman Problem (m-PSP). In this paper we discuss some complexity results of the problem before presenting upper and lower bounding procedures.
Good results are obtained not only on the m-PVRP in general, but also on the VRP and the m-PSP using classical VRP instances and TSPLIB instances. 相似文献
19.
Yannis Marinakis Magdalene Marinaki 《Journal of Mathematical Modelling and Algorithms》2008,7(1):59-78
This paper introduces a new hybrid algorithmic nature inspired approach based on particle swarm optimization, for solving
successfully one of the most popular logistics management problems, the location routing problem (LRP). The proposed algorithm
for the solution of the location routing problem, the hybrid particle swarm optimization (HybPSO-LRP), combines a particle
swarm optimization (PSO) algorithm, the multiple phase neighborhood search – greedy randomized adaptive search procedure (MPNS-GRASP)
algorithm, the expanding neighborhood search (ENS) strategy and a path relinking (PR) strategy. The algorithm is tested on
a set of benchmark instances. The results of the algorithm are very satisfactory for these instances and for six of them a
new best solution has been found.
相似文献
20.
The splitting method is one of the most powerful and well-studied approaches to solving various NP-hard problems. The main idea of this method is to split the input instance of a problem into several simpler instances (further
simplified by certain simplification rules) such that when the solution for each of them is found, one can construct the solution
for the initial instance in polynomial time. There exists a huge number of papers describing algorithms of this type, and
usually a considerable part of such a paper is devoted to case analysis. In this paper, we present a program that, given a
set of simplification rules, automatically generates a proof of an upper bound on the running time of a splitting algorithm
using these rules. As an example, we report the results of experiments with such a program for the SAT, MAXSAT, and (n, 3)-MAXSAT (the MAXSAT problem for the case where every variable in the formula appears at most three times) problems. Bibliography: 13 titles.
__________
Translated from Zapiski Nauchnykh Seminarov POMI, Vol. 316, 2004, pp. 111–128. 相似文献