Probabilistische analyse von heuristiken der kombinatorischen optimierung – ein überbllck

To various problems of combinatorial optimization we consider the question how the value of the optimal solution resp. the values of some approximative solutions are predetermined with high probability to a given distribution. We present results to probabilistic analysis of heuristics. We consider the problems Traveling Salesman, Minimum Perfect Matching. Minimum Spanning Tree, Linear Optimization, Bin Packing, Multi-processor-Scheduling, Subset Sum and some problems to random graphs.     

TWO ALGORITHMS FOR LC~1 UNCONSTRAINED OPTIMIZATION

1. IntroductionThe LCI optimization problems exist extensively in various optimization problems.FOr example, the problems from nonlinear complementarity) variational inequality andCd nonlinear programming can be formed as LCI optimization problems. In addition,LCI optimization problems also arise from the extended linear-quadratic programmingproblems, nonlinear minimax problems, stochastic optimization problems and somesemi-infinite programs. See [6] [9] [11] [13] [14] [151 [17] [21].In t…     

Dual mean field annealing scheme for binary optimization under linear constraints

It is shown that certain general classes of constrained binary optimization tasks can be solved with increasing accuracy by a first order mean field approximation of the Boltzmann distribution of the associated Lagrangian as the instance size grows. The formalism is thoroughly analyzed for the quadratic and multidimensional knapsack models. In these cases analytical expressions for the convergence of the optimality gaps are given, which are experimentally verified.     

Permutatorial optimization via the permutahedron

A water company decides to expand its network with a set of water lines, but it cannot build them all at once. However, it starts reaping benefits from a partial expansion. In what order should the company build the lines? We formalize a class of permutatorial problems with combinatorial/continuous subproblems capturing applications of incremental deployment. We show that, for additive/linear objective functions, efficient polyhedral methods for the subproblems extend to the permutatorial problem. Our main technical ingredient is the permutahedron.     

A NEW FAMILY OF TRUST REGION ALGORITHMS FOR UNCONSTRAINED OPTIMIZATION

Trust region (TR) algorithms are a class of recently developed algorithms for nonlinear optimization. A new family of TR algorithms for unconstrained optimization, which is the extension of the usual TR method, is presented in this paper. When the objective function is bounded below and continuously, differentiable, and the norm of the Hesse approximations increases at most linearly with the iteration number, we prove the global convergence of the algorithms. Limited numerical results are reported, which indicate that our new TR algorithm is competitive.     

AN ITERATIVE MULTILEVEL APPROACH TO NATURAL RESOURCE OPTIMIZATION: A TEST CASE

Forest planners face a dilemma. On the one hand, they desire more detail than they currently have in their planning optimization models, and on the other hand, these models are already extremely large and complex. This sort of problem is common in other natural resource management situations as well. This paper investigates an iterative multilevel approach that would allow districts within the forest to have models approaching the size and complexity of current forest models, but still approximate a forest-level optimum. A specific procedure based on equating shadow prices across districts is developed and tested with a case example where a global optimum is determinable as a standard of comparison. The procedure shows promise, but difficulties in recognizing optimality are indicated.     

Multiobjective service restoration in electric distribution networks using a local search based heuristic

Contingency situations may cause emergency states in distribution systems; these states are defined as the interruption of power supply. Such situations should be avoided whenever possible in order to maintain certain quality limits related to frequency and duration of interruptions. The main objective of service restoration is to minimize the number of consumers affected by the fault, by transferring them to energized support feeders. Electrical and operational conditions, such as radial network configuration, equipment and voltage drop limits, must be respected. This paper presents a new multiobjective local search based heuristic for the restoration of service which considers the minimization of two conflicting criteria: the load not supplied and the number of switching operations involved. Computational experiments with three network systems have shown the flexibility and effectiveness of the proposed method.     

A primal-proximal heuristic applied to the French Unit-commitment problem

This paper is devoted to the numerical resolution of unit-commitment problems, with emphasis on the French model optimizing the daily production of electricity. The solution process has two phases. First a Lagrangian relaxation solves the dual to find a lower bound; it also gives a primal relaxed solution. We then propose to use the latter in the second phase, for a heuristic resolution based on a primal proximal algorithm. This second step comes as an alternative to an earlier approach, based on augmented Lagrangian (i.e. a dual proximal algorithm). We illustrate the method with some real-life numerical results. A companion paper is devoted to a theoretical study of the heuristic in the second phase.     

The combinatorics of pivoting for the maximum weight clique

In this paper we prove the equivalence between a pivoting-based heuristic (PBH) for the maximum weight clique problem and a combinatorial greedy heuristic. It is also proved that PBH always returns a local solution although this is not always guaranteed for Lemke's method, on which PBH is based.     

Ranking robustness and its application to evacuation planning

We present a new approach to handle uncertain combinatorial optimization problems that uses solution ranking procedures to determine the degree of robustness of a solution. Unlike classic concepts for robust optimization, our approach is not purely based on absolute quantitative performance, but also includes qualitative aspects that are of major importance for the decision maker.We discuss the two variants, solution ranking and objective ranking robustness, in more detail, presenting problem complexities and solution approaches. Using an uncertain shortest path problem as a computational example, the potential of our approach is demonstrated in the context of evacuation planning due to river flooding.     

一类正则化参数自由的线性约束凸优化问题的预测-校正算法

我们对文章的结构做这样的安排:第二节给出本文需要的预备知识;第三节简述单个目标函数问题(1.1)的己有算法和求解可能遇到的困难,第四节给出解决问题的预测-校正方法;第五节和第六节对问题(1.2)分别陈述己有方法的固有困难和我们提出的解决方案.最后,在第七节中,我们为提出的方法给出统一的算法框架,证明这类算法的收敛性和遍历意义下的收敛速率,同时给出我们的一些结论.     

Solving the 2-rooted mini-max spanning forest problem by branch-and-bound

The 2-rooted mini-max spanning forest problem is to find a spanning forest with two given root nodes on an undirected graph, such that the maximum tree cost in this forest is minimized. We introduce a branch-and-bound algorithm based on selecting nodes. On test instances up to 50 nodes the algorithm gives much better computational results than a known algorithm that is based on selecting edges. Furthermore the new algorithm can easily solve problem instances up to 80 nodes.     

基于混沌集群智能优化算法的多目标粗糙集属性约减

针对管理实践及大数据处理过程中具有多决策属性的粗糙集属性约减问题,将条件属性依赖度与知识分辨度进行结合构建属性权重,分别建立针对不同决策属性的约减目标函数,引入帕累托最优思想,将基于多决策属性的粗糙集属性约减问题转化为离散多目标优化问题。针对该问题的结构设计了具有集群智能优化思想的元胞自动机求解算法,在算法中引入基于个体的非支配解集平衡局部最优与全局最优的关系,引入混沌遗传算子增加种群多样性。以某铁路局设备安全风险处理数据为案例构建多决策属性粗糙集决策表进行优化计算并进行管理决策分析。研究发现:(1)相对于传统的NSGA-II与MO-cell算法,本文提出的算法具有更强的多目标属性挖掘性能;(2)帕累托最优思想可以较好地解释多决策属性粗糙集在管理实践中的意义。     

Reinforcement learning enhanced multi-neighborhood tabu search for the max-mean dispersion problem

This paper presents a highly effective reinforcement learning enhancement of multi-neighborhood tabu search for the max-mean dispersion problem. The reinforcement learning component uses the Q-learning mechanism that incorporates the accumulated feedback information collected from the actions performed during the search to guide the generation of diversified solutions. The tabu search component employs 1-flip and reduced 2-flip neighborhoods to collaboratively perform the neighborhood exploration for attaining high-quality local optima. A learning automata method is integrated in tabu search to adaptively determine the probability of selecting each neighborhood. Computational experiments on 80 challenging benchmark instances demonstrate that the proposed algorithm is favorably competitive with the state-of-the-art algorithms in the literature, by finding new lower bounds for 3 instances and matching the best known results for the other instances. Key elements and properties are also analyzed to disclose the source of the benefits of our integration of learning mechanisms and tabu search.     

粒子群优化与差分进化混合算法的综述与分类

优化算法的性能改进长期以来一直是算法研究者们追求的一个重要目标,对不同算法进行混合以期利用算法的互补优势来获得性能更优异的算法代表了一类典型的设计思想.针对两类基于群体演化的优化算法——粒子群优化(PSO)与差分进化(DE)算法,对基于二者的各种混合算法(DEPSO)进行了系统而全面的综述,并在此基础上提出了一种混合策...     

Forest management models and combinatorial algorithms: analysis of state of the art

Linear Programming and Mixed Integer Linear Programs have been used for forest planning since the 60's to support decision making on forest harvesting and management. In particular, during the last two decades of forest management there has been an increased interest in spatial issues. Further, new environmental concerns, such as resource sustainability and wildlife protection, impose that increased attention be paid to activities carried out on the ground. Road building needed for access also requires spatial definiton. As a result, more complex models must be used. We discuss the issues which have led to the combinatorial nature of some main forest management problems and the solution algorithms that have been proposed for these problems, including local search heuristics, random search approaches, strengthening of mixed integer model formulations and Lagrangian relaxation. In this survey, we discuss which of the proposed approaches have been used succesfully, the advantages and shortcomings of each and what are still open research problems. This revised version was published online in June 2006 with corrections to the Cover Date.     

Branch and bound algorithm for a transfer line design problem: Stations with sequentially activated multi-spindle heads

In this paper, a new transfer line balancing problem is considered. The main difference from the simple assembly line balancing problem is that the operations are grouped into blocks (batches). All the operations of the same block are carried out simultaneously by one piece of equipment (multi-spindle head). Nevertheless, the blocks assigned to the same workstation are executed in series. The line cost consists of the sum of block and workstation costs. At the considered line design stage, the set of all available blocks is given. The aim is to find a subset from the given set of available blocks and to find a partition of this subset to workstations such that each operation is executed once and the line cost is minimal while all the precedence, cycle time, and compatibility (operation inclusion and block exclusion) constraints are respected. A new lower bound based on solving a special set partitioning problem is presented and a branch and bound algorithm is developed. The experimental results prove the quality of the lower bound and applicability of the suggested branch and bound algorithm for medium sized industrial cases.     

Domination analysis for minimum multiprocessor scheduling

Let P be a combinatorial optimization problem, and let A be an approximation algorithm for P. The domination ratio domr(A,s) is the maximal real q such that the solution x(I) obtained by A for any instance I of P of size s is not worse than at least the fraction q of the feasible solutions of I. We say that P admits an asymptotic domination ratio one (ADRO) algorithm if there is a polynomial time approximation algorithm A for P such that . Alon, Gutin and Krivelevich [Algorithms with large domination ratio, J. Algorithms 50 (2004) 118-131] proved that the partition problem admits an ADRO algorithm. We extend their result to the minimum multiprocessor scheduling problem.     

The biobjective travelling purchaser problem

The purpose of this article is to present and solve the Biobjective Travelling Purchaser Problem, which consists in determining a route through a subset of markets in order to collect a set of products, minimizing the travel distance and the purchasing cost simultaneously. The most convenient purchase of the product in the visited markets is easily computed once the route has been determined. Therefore, this problem contains a finite set of solutions (one for each route) and the problem belongs to the field of the Biobjective Combinatorial Optimization. It is here formulated as a Biobjective Mixed Integer Linear Programming model with an exponential number of valid inequalities, and this model is used within a cutting plane algorithm to generate the set of all supported and non-supported efficient points in the objective space. A variant of the algorithm computes only supported efficient points. For each efficient point in the objective space exactly one Pareto optimal solution in the decision space is computed by solving a single-objective problem. Each of these single-objective problems, in turn, is solved by a specific branch-and-cut approach. A heuristic improvement based on saving previously generated cuts in a common cut-pool structure has also been developed with the aim of speeding up the algorithm performance. Results based on benchmark instances from literature show that the common cut-pool heuristic is very useful, and that the proposed algorithm manages to solve instances containing up to 100 markets and 200 different products. The general procedure can be extended to address other biobjective combinatorial optimization problems whenever a branch-and-cut algorithm is available to solve a single-objective linear combination of these criteria.