共查询到20条相似文献,搜索用时 15 毫秒
1.
In this paper, we consider the problem of computing an optimal branch decomposition of a graph. Branch decompositions and
branchwidth were introduced by Robertson and Seymour in their series of papers that proved the Graph Minors Theorem. Branch
decompositions have proven to be useful in solving many NP-hard problems, such as the traveling salesman, independent set,
and ring routing problems, by means of combinatorial algorithms that operate on branch decompositions. We develop an implicit
enumeration algorithm for the optimal branch decomposition problem and examine its performance on a set of classical graph
instances. 相似文献
2.
We propose a family of gradient algorithms for minimizing a quadratic function f(x)=(Ax,x)/2−(x,y) in ℝ
d
or a Hilbert space, with simple rules for choosing the step-size at each iteration. We show that when the step-sizes are
generated by a dynamical system with ergodic distribution having the arcsine density on a subinterval of the spectrum of A, the asymptotic rate of convergence of the algorithm can approach the (tight) bound on the rate of convergence of a conjugate
gradient algorithm stopped before d iterations, with d≤∞ the space dimension. 相似文献
3.
José Fernando Gonçalves Mauricio G. C. Resende Jorge J. M. Mendes 《Journal of Heuristics》2011,17(5):467-486
This paper presents a biased random-key genetic algorithm for the resource constrained project scheduling problem. The chromosome
representation of the problem is based on random keys. Active schedules are constructed using a priority-rule heuristic in
which the priorities of the activities are defined by the genetic algorithm. A forward-backward improvement procedure is applied
to all solutions. The chromosomes supplied by the genetic algorithm are adjusted to reflect the solutions obtained by the
improvement procedure. The heuristic is tested on a set of standard problems taken from the literature and compared with other
approaches. The computational results validate the effectiveness of the proposed algorithm. 相似文献
4.
The design of effective neighborhood structures is fundamentally important for creating better local search and metaheuristic algorithms for combinatorial optimization. Significant efforts have been made to develop larger and more powerful neighborhoods that are able to explore the solution space more effectively while keeping computation complexity within acceptable levels. The most important advances in this domain derive from dynamic and adaptive neighborhood constructions originating in ejection chain methods and a special form of a candidate list design that constitutes the core of the filter-and-fan method. The objective of this paper is to lay out the general framework of the ejection chain and filter-and-fan methods and present applications to a number of important combinatorial optimization problems. The features of the methods that make them effective in these applications are highlighted to provide insights into solving challenging problems in other settings. 相似文献
5.
Mingqiang Zhu Stephen J. Wright Tony F. Chan 《Computational Optimization and Applications》2010,47(3):377-400
Image restoration models based on total variation (TV) have become popular since their introduction by Rudin, Osher, and Fatemi (ROF) in 1992. The dual formulation of this model has a quadratic objective with separable constraints, making projections onto the feasible set easy to compute. This paper proposes application of gradient projection (GP) algorithms to the dual formulation. We test variants of GP with different step length selection and line search strategies, including techniques based on the Barzilai-Borwein method. Global convergence can in some cases be proved by appealing to existing theory. We also propose a sequential quadratic programming (SQP) approach that takes account of the curvature of the boundary of the dual feasible set. Computational experiments show that the proposed approaches perform well in a wide range of applications and that some are significantly faster than previously proposed methods, particularly when only modest accuracy in the solution is required. 相似文献
6.
In a two-stage robust covering problem, one of several possible scenarios will appear tomorrow and require to be covered, but costs are higher tomorrow than today. What should you anticipatorily buy today, so that the worst-case cost (summed over both days) is minimized? We consider the \(k\) -robust model where the possible scenarios tomorrow are given by all demand-subsets of size \(k\) . In this paper, we give the following simple and intuitive template for \(k\) -robust covering problems: having built some anticipatory solution, if there exists a single demand whose augmentation cost is larger than some threshold, augment the anticipatory solution to cover this demand as well, and repeat. We show that this template gives good approximation algorithms for \(k\) -robust versions of many standard covering problems: set cover, Steiner tree, Steiner forest, minimum-cut and multicut. Our \(k\) -robust approximation ratios nearly match the best bounds known for their deterministic counterparts. The main technical contribution lies in proving certain net-type properties for these covering problems, which are based on dual-rounding and primal–dual ideas; these properties might be of some independent interest. As a by-product of our techniques, we also get algorithms for max–min problems of the form: “given a covering problem instance, which \(k\) of the elements are costliest to cover?” For the problems mentioned above, we show that their \(k\) -max–min versions have performance guarantees similar to those for the \(k\) -robust problems. 相似文献
7.
Index-tracking is a low-cost alternative to active portfolio management. The implementation of a quantitative approach, however,
is a major challenge from an optimization perspective. The optimal selection of a group of assets that can replicate the index
of a much larger portfolio requires both to find the optimal subset of assets and to fine-tune their weights. The former is
a combinatorial, the latter a continuous numerical problem. Both problems need to be addressed simultaneously, because whether
or not a selection of assets is promising depends on the allocation weights and vice versa. Moreover, the problem is usually
of high dimension. Typically, an optimal subset of 30–150 positions out of 100–600 need to be selected and their weights determined.
Search heuristics can be a valuable alternative to traditional methods, which often cannot deal with the problem. In this
paper, we propose a new optimization method, which is partly based on Differential Evolution (DE) and on combinatorial search.
The main advantage of our method is that it can tackle the index-tracking problem as complex as it is, generating accurate
and robust results. 相似文献
8.
9.
In many practical applications, the task is to optimize a non-linear objective function over the vertices of a well-studied polytope as, e.g., the matching polytope or the travelling salesman polytope (TSP). Prominent examples are the quadratic assignment problem and the quadratic knapsack problem; further applications occur in various areas such as production planning or automatic graph drawing. In order to apply branch-and-cut methods for the exact solution of such problems, the objective function has to be linearized. However, the standard linearization usually leads to very weak relaxations. On the other hand, problem-specific polyhedral studies are often time-consuming. Our goal is the design of general separation routines that can replace detailed polyhedral studies of the resulting polytope and that can be used as a black box. As unconstrained binary quadratic optimization is equivalent to the maximum-cut problem, knowledge about cut polytopes can be used in our setting. Other separation routines are inspired by the local cuts that have been developed by Applegate, Bixby, Chvátal and Cook for faster solution of large-scale traveling salesman instances. Finally, we apply quadratic reformulations of the linear constraints as proposed by Helmberg, Rendl and Weismantel for the quadratic knapsack problem. By extensive experiments, we show that a suitable combination of these methods leads to a drastic speedup in the solution of constrained quadratic 0–1 problems. We also discuss possible generalizations of these methods to arbitrary non-linear objective functions. 相似文献
10.
11.
《Optimization》2012,61(1-2):75-90
In this paper, a kind of subgradient projection algorithms is established for minimizing a locally Lipschitz continuous function subject to nonlinearly smooth constraints, which is based on the idea to get a feasible and strictly descent direction by combining the ?-subgradient projection direction that attempts to satisfy the Kuhn-Tucker conditions with one corrected direction produced by a linear programming subproblem. The algorithm avoids the zigzagging phenomenon and converges to Kuhn-Tucker points, due to using the c.d.f. maps of Polak and Mayne (1985), ?active constraints and ?adjusted rules 相似文献
12.
Optimal sensor placement for modal identification of structures using genetic algorithms—a case study: the olympic stadium in Cali,Colombia 总被引:1,自引:0,他引:1
Adequate sensor placement plays a key role in such fields as system identification, structural control, damage detection and
structural health monitoring of flexible structures. In recent years, interest has increased in the development of methods
for determining an arrangement of sensors suitable for characterizing the dynamic behavior of a given structure. This paper
describes the implementation of genetic algorithms as a strategy for optimal placement of a predefined number of sensors.
The method is based on the maximization of a fitness function that evaluates sensor positions in terms of natural frequency
identification effectiveness and mode shape independence under various occupation and excitation scenarios using a custom
genetic algorithm. A finite element model of the stadium was used to evaluate modal parameters used in the fitness function,
and to simulate different occupation and excitation scenarios. The results obtained with the genetic algorithm strategy are
compared with those obtained from applying the Effective Independence and Modal Kinetic Energy sensor placement techniques.
The sensor distribution obtained from the proposed strategy will be used in a structural health monitoring system to be installed
in the stadium. 相似文献
13.
Ant colony optimization is a metaheuristic that has been applied to a variety of combinatorial optimization problems. In this
paper, an ant colony optimization approach is proposed to deal with the multidimensional knapsack problem. It is an extension
of Max Min Ant System which imposes lower and upper trail limits on pheromone values to avoid stagnation. In order to choose
the lower trail limit, we provide a new method which takes into account the influence of heuristic information. Furthermore,
a local search procedure is proposed to improve the solutions constructed by ants. Computational experiments on benchmark
problems are carried out. The results show that the proposed algorithm can compete efficiently with other promising approaches
to the problem. 相似文献
14.
Regina S. Burachik C. Yalçın Kaya Musa Mammadov 《Computational Optimization and Applications》2010,45(1):1-24
We propose and analyze an inexact version of the modified subgradient (MSG) algorithm, which we call the IMSG algorithm, for
nonsmooth and nonconvex optimization over a compact set. We prove that under an approximate, i.e. inexact, minimization of
the sharp augmented Lagrangian, the main convergence properties of the MSG algorithm are preserved for the IMSG algorithm.
Inexact minimization may allow to solve problems with less computational effort. We illustrate this through test problems,
including an optimal bang-bang control problem, under several different inexactness schemes. 相似文献
15.
16.
In this paper, we propose approximate and exact algorithms for the double constrained two-dimensional guillotine cutting stock
problem (DCTDC). The approximate algorithm is a two-stage procedure. The first stage attempts to produce a starting feasible
solution to DCTDC by solving a single constrained two dimensional cutting problem, CDTC. If the solution to CTDC is not feasible
to DCTDC, the second stage is used to eliminate non-feasibility. The exact algorithm is a branch-and-bound that uses efficient
lower and upper bounding schemes. It starts with a lower bound reached by the approximate two-stage algorithm. At each internal
node of the branching tree, a tailored upper bound is obtained by solving (relaxed) knapsack problems. To speed up the branch
and bound, we implement, in addition to ordered data structures of lists, symmetry, duplicate, and non-feasibility detection
strategies which fathom some unnecessary branches. We evaluate the performance of the algorithm on different problem instances
which can become benchmark problems for the cutting and packing literature. 相似文献
17.
Olivier Klopfenstein 《Computational Optimization and Applications》2010,45(3):607-638
The aim of this paper is to provide new efficient methods for solving general chance-constrained integer linear programs to
optimality. Valid linear inequalities are given for these problems. They are proved to characterize properly the set of solutions.
They are based on a specific scenario, whose definition impacts strongly on the quality of the linear relaxation built. A branch-and-cut
algorithm is described to solve chance-constrained combinatorial problems to optimality. Numerical tests validate the theoretical
analysis and illustrate the practical efficiency of the proposed approach. 相似文献
18.
Two kinds of MAX RES CUT problems, the MAX s?t CUT and the MAX s?t?v CUT, with limited unbalanced constraints are considered. Approximation algorithms used in Frieze and Jerrum (Integer Programming and Combinatorial Optimization, vol. 920, pp. 1–13, Springer, Berlin, 1995), Galbiati and Maffioli (Theor. Comput. Sci. 385:78–87, 2007), Han et al. (Math. Program. Ser. B 92:509–535, 2002) and Ye (Math. Programm. 90:101–111, 2001) are extended to the two MAX RES CUT problems. A special matrix P is constructed by which it can ensure that the given nodes s,t are feasible to equality constraints with probability one for the MAX s?t CUT and s,t,v are feasible to equality constraints with at least probability 0.912 for the MAX s?t?v CUT. A fussy greedy sizing-adjusted procedure is then proposed to confirm that the round solution is feasible for all constraints. We find these extensions are nontrivial and some interesting results about performance ratio are obtained for the MAX RES CUT problem with limited unbalanced constraints. 相似文献
19.
《European Journal of Operational Research》1999,114(3):580-588
In this paper, we propose interactive fuzzy programming for multi-level 0–1 programming problems through genetic algorithms. Our method is supposed to apply to hierarchical decision problems in which decision-making at each level is sequential from upper to lower level and decision makers are essentially cooperative. After determining the fuzzy goals of the decision makers at all levels, a satisfactory solution is derived efficiently by updating the satisfactory degrees of the decision makers at the upper level with considerations of overall satisfactory balance among all levels. An illustrative numerical example for three-level 0–1 programming problems is provided to demonstrate the feasibility of the proposed method. 相似文献
20.
《European Journal of Operational Research》1997,97(1):149-158
Recently, genetic algorithms (GAs), a new learning paradigm that models a natural evolution mechanism, have received a great deal of attention regarding their potential as optimization techniques for solving combinatorial optimization problems. In this paper, we focus on multiobjective 0–1 programming problems as a generalization of the traditional single objective ones. By considering the imprecise nature of human judgements, we assume that the decision maker may have fuzzy goal for each of the objective functions. After eliciting the linear membership functions through the interaction with the decision maker, we adopt the fuzzy decision of Bellman and Zadeh or minimum-operator for combining them. In order to investigate the applicability of the conventional GAs for the solution of the formulated problems, a lot of numerical simulations are performed by assuming several genetic operators. Then, instead of using the penalty function for treating the constraints, we propose three types of revised GAs which generate only feasible solutions. Illustrative numerical examples demonstrate both feasibility and efficiency of the proposed methods. 相似文献