节点加权的Steiner树问题的降阶回溯算法

节点加权的Steiner树问题是组合优化中一个经典的NP-hard问题,现有算法研究该问题时存在时间复杂性高或无法得到最优解的缺点。针对现有算法的不足,提出了一个基于降阶技术的回溯算法。首先研究该问题的数学性质,利用数学性质对该问题进行降阶以缩小问题的规模;接着提出上界子算法和下界子算法,利用上下界子算法对该问题的解空间树进行剪枝,提高搜索效率;最后利用上下界子算法和数学性质设计了一个回溯算法求解该问题。示例分析以及实验的结果表明,该算法不仅时间复杂性较低而且可以得到问题的最优解。     

Branch‐and‐bound approach for optima localization in scheduling multiprocessor jobs

We consider multiprocessor task scheduling problems with dedicated processors. We determine the tight optima localization intervals for different subproblems of the basic problem. Based on the ideas of a computer‐aided technique developed by Sevastianov and Tchernykh for shop scheduling problems, we elaborate a similar method for the multiprocessor task scheduling problem. Our method allows us to find an upper bound for the length of the optimal schedule in terms of natural lower bound. As a byproduct of our results, a family of linear‐time approximation algorithms with a constant ratio performance guarantee is designed for the NP‐hard subproblems of the basic problem, and new polynomially solvable classes of problems are found.     

Partition-Based Lower Bound for Max-CSP

In this paper we address Max-CSP, a constraint optimization problem typically solved using a branch and bound scheme. It is well known that the efficiency of branch and bound greatly depends on the quality of the available lower bound. Previous approaches aggregate to the lower bound individual contributions of unassigned variables. In this paper, we augment this approach by adding global contributions of disjoint subsets of unassigned variables, which requires a partition of the set of unassigned variables. Using this idea, we introduce the partition-based lower bound. It improves previous approaches based on individual contributions in the sense that our method can be added up to previous bounds, possibly increasing their value. We demonstrate our method presenting two new algorithms, PFC-PRDAC and PFC-MPRDAC, which are the natural successors of PFC-RDAC and PFC-MRDAC augmented with our approach. We provide experimental evidence for the superiority of the new algorithms on random problems and real instances of weighted over-constrained problems.     

Solving the multidimensional knapsack problems with generalized upper bound constraints by the adaptive memory projection method

An adaptive memory projection (referred as AMP) method is developed for multidimensional knapsack problems (referred as the MKP) with generalized upper bound constraints. All the variables are divided into several generalized upper bound (referred as GUB) sets and at most one variable can be chosen from each of the GUB sets. The MKP with GUBs (referred as the GUBMKP) can be applied to many real-world problems, such as capital budgeting, resource allocation, cargo loading, and project selection. Due to the complexity of the GUBMKP, good metaheuristics are sought to tackle this problem.The AMP method keeps track of components of good solutions during the search and creates provisional solution by combining components of better solutions. The projection method, which can free the selected variables while fixing the others, is very useful for metaheuristics, especially when tackling large-scale combinatorial optimization. In this paper, the AMP method is implemented by iteratively using critical event tabu search as a search routine, and CPLEX in the referent optimization stage. Variables that are strongly determined, consistent, or attractive, are identified in the search process. Selected variables from this pool are fed into CPLEX as a small subproblem. In addition to the diversification effect within critical event tabu search, the pseudo-cut inequalities and an adjusted frequency penalty scalar are also applied to increase opportunities of exploring new regions.This study conducts a comprehensive sensitivity analysis on the parameters and strategies used in the proposed AMP method. The computational results show several variants of the AMP method outperforms the tight oscillation method in the literature of GUBMKP. On average, consistent variables tend to perform best as a pure strategy. A pure strategy equipped with local search can lead into even better results. Last but not least, testing different types of variables in the referent optimization stage before selecting just one of the pure strategies is found to be very helpful.     

一个新的极大独立集算法及独立数的界

最大独立集问题是图论中典型的组合优化问题,有着广泛的实际应用价值。分析了现有独立数的界公式后给出了新的上界公式,并通过分析贪婪算法和独立集自身的特征,给出了新的求解极大独立集的算法,并证明了其确定性。然后用实例验证了该算法的有效性。     

A 2-phase algorithm for solving the single allocation p-hub center problem

The single allocation p-hub center problem is an NP-hard location–allocation problem which consists of locating hub facilities in a network and allocating non-hub nodes to hub nodes such that the maximum distance/cost between origin–destination pairs is minimized. In this paper we present an exact 2-phase algorithm where in the first phase we compute a set of potential optimal hub combinations using a shortest path based branch and bound. This is followed by an allocation phase using a reduced sized formulation which returns the optimal solution. In order to get a good upper bound for the branch and bound we developed a heuristic for the single allocation p-hub center problem based on an ant colony optimization approach. Numerical results on benchmark instances show that the new solution approach is superior over traditional MIP-solver like CPLEX. As a result we are able to provide new optimal solutions for larger problems than those reported previously in literature. We are able to solve problems consisting of up to 400 nodes in reasonable time. To the best of our knowledge these are the largest problems solved in the literature to date.     

A Note on the Stopping Redundancy of Linear Codes

In this paper, we study the stopping sets, stopping distance and stopping redundancy for binary linear codes. Stopping redundancy is a new concept proposed by Schwartz and Vardy recently for evaluating the performance of a linear code under iterative decoding over a binary erasure channel （BEC）. Since the exact value of stopping redundancy is difficult to obtain in general, good lower and upper bounds are important. We obtain a new general upper bound on the stopping redundancy of binary linear codes which improves the corresponding results of Schwartz and Vardy.     

Solving constraint optimization problems from CLP-stylespecifications using heuristic search techniques

Presents a framework for efficiently solving logic formulations of combinatorial optimization problems using heuristic search techniques. In order to integrate cost, lower-bound and upper-bound specifications with conventional logic programming languages, we augment a constraint logic programming (CLP) language with embedded constructs for specifying the cost function and with a few higher-order predicates for specifying the lower and upper bound functions. We illustrate how this simple extension vastly enhances the ease with which optimization problems involving combinations of Min and Max can be specified in the extended language CLP* and we show that CSLDNF (Constraint SLD resolution with Negation as Failure) resolution schemes are not efficient for solving optimization problems specified in this language. Therefore, we describe how any problem specified using CLP* can be converted into an implicit AND/OR graph, and present an algorithm called GenSolve which can branch-and-bound using upper and lower bound estimates, thus exploiting the full pruning power of heuristic search techniques. A technical analysis of GenSolve is provided. We also provide experimental results comparing various control strategies for solving CLP* programs     

On some fundamental properties of structural topology optimization problems

We study some fundamental mathematical properties of discretized structural topology optimization problems. Either compliance is minimized with an upper bound on the volume of the structure, or volume is minimized with an upper bound on the compliance. The design variables are either continuous or 0–1. We show, by examples which can be solved by hand calculations, that the optimal solutions to the problems in general are not unique and that the discrete problems possibly have inactive volume or compliance constraints. These observations have immediate consequences on the theoretical convergence properties of penalization approaches based on material interpolation models. Furthermore, we illustrate that the optimal solutions to the considered problems in general are not symmetric even if the design domain, the external loads, and the boundary conditions are symmetric around an axis. The presented examples can be used as teaching material in graduate and undergraduate courses on structural topology optimization.     

Inner approximations of completely positive reformulations of mixed binary quadratic programs: a unified analysis

Every quadratic programming problem with a mix of continuous and binary variables can be equivalently reformulated as a completely positive optimization problem, that is, a linear optimization problem over the convex but computationally intractable cone of completely positive matrices. In this paper, we focus on general inner approximations of the cone of completely positive matrices on instances of completely positive optimization problems that arise from the reformulation of mixed binary quadratic programming problems. We provide a characterization of the feasibility of such an inner approximation as well as the optimal value of a feasible inner approximation. In particular, our results imply that polyhedral inner approximations are equivalent to a finite discretization of the feasible region of the original completely positive optimization problem. Our characterization yields, as a byproduct, an upper bound on the gap between the optimal value of an inner approximation and that of the original instance. We discuss the implications of this error bound for standard and box-constrained quadratic programs as well as general mixed binary quadratic programs with a bounded feasible region.     

A linear programming approach to max-sum problem: a review

The max-sum labeling problem, defined as maximizing a sum of binary (i.e., pairwise) functions of discrete variables, is a general NP-hard optimization problem with many applications, such as computing the MAP configuration of a Markov random field. We review a not widely known approach to the problem, developed by Ukrainian researchers Schlesinger et al. in 1976, and show how it contributes to recent results, most importantly, those on the convex combination of trees and tree-reweighted max-product. In particular, we review Schlesinger et al.'s upper bound on the max-sum criterion, its minimization by equivalent transformations, its relation to the constraint satisfaction problem, the fact that this minimization is dual to a linear programming relaxation of the original problem, and the three kinds of consistency necessary for optimality of the upper bound. We revisit problems with Boolean variables and supermodular problems. We describe two algorithms for decreasing the upper bound. We present an example application for structural image analysis.     

Decision problems for lower/upper bound parametric timed automata

We investigate a class of parametric timed automata, called lower bound/upper bound (L/U) automata, where each parameter occurs in the timing constraints either as a lower bound or as an upper bound. For such automata, we show that basic decision problems, such as emptiness, finiteness and universality of the set of parameter valuations for which there is a corresponding infinite accepting run of the automaton, is Pspace-complete. We extend these results by allowing the specification of constraints on parameters as a linear system. We show that the considered decision problems are still Pspace-complete, if the lower bound parameters are not compared with the upper bound parameters in the linear system, and are undecidable in general. Finally, we consider a parametric extension of MITL\mathsf{MITL} _0,∞, and prove that the related satisfiability and model checking (w.r.t. L/U automata) problems are Pspace-complete.     

Branch and bound algorithm for computing the minimum stability degree of parameter-dependent linear systems

We consider linear systems with unspecified parameters that lie between given upper and lower bounds. Except for a few special cases, the computation of many quantities of interest for such systems can be performed only through an exhaustive search in parameter space. We present a general branch and bound algorithm that implements this search in a systematic manner and apply it to computing the minimum stability degree.     

A lower bound for the Node,Edge, and Arc Routing Problem

The Node, Edge, and Arc Routing Problem (NEARP) was defined by Prins and Bouchenoua in 2004, although similar problems have been studied before. This problem, also called the Mixed Capacitated General Routing Problem (MCGRP), generalizes the classical Capacitated Vehicle Routing Problem (CVRP), the Capacitated Arc Routing Problem (CARP), and the General Routing Problem. It captures important aspects of real-life routing problems that were not adequately modeled in previous Vehicle Routing Problem (VRP) variants. The authors also proposed a memetic algorithm procedure and defined a set of test instances called the CBMix benchmark. The NEARP definition and investigation contribute to the development of rich VRPs. In this paper we present the first lower bound procedure for the NEARP. It is a further development of lower bounds for the CARP. We also define two novel sets of test instances to complement the CBMix benchmark. The first is based on well-known CARP instances; the second consists of real life cases of newspaper delivery routing. We provide numerical results in the form of lower and best known upper bounds for all instances of all three benchmarks. For three of the instances, the gap between the upper and lower bound is closed. The average gap is 25.1%. As the lower bound procedure is based on a high quality lower bound procedure for the CARP, and there has been limited work on approximate solution methods for the NEARP, we suspect that a main reason for the rather large gaps is the quality of the upper bound. This fact, and the high industrial relevance of the NEARP, should motivate more research on approximate and exact methods for this important problem.     

不确定噪声方差定常系统保性能鲁棒Kalman滤波器

对带不确定噪声方差线性定常系统鲁棒Kalman滤波,提出一般的统一的保性能鲁棒性概念.用Lyapunov方程方法,提出两类保性能极大极小鲁棒稳态Kalman滤波器.一类是寻求不确定噪声方差最大扰动域(鲁棒域),使得对于扰动域内的所有扰动,确保系统滤波精度偏差的最大下界是零,最小上界是所预置的精度偏差指标;另一类是在预置噪声方差有界扰动域内,寻求滤波精度偏差的最大下界和最小上界.通过引入不确定噪声方差扰动的参数化表示,问题转化为相应的非线性与线性最优化问题,可分别用Lagrange乘数法和线性规划(LP)方法求解.应用于跟踪系统的仿真例子验证了所提结果的正确性和有效性.     

Variable Sized Online Interval Coloring with Bandwidth

We consider online coloring of intervals with bandwidth in a setting where colors have variable capacities. Whenever the algorithm opens a new color, it must choose the capacity for that color and cannot change it later. A set of intervals can be assigned the same color a of capacity C _a if the sum of bandwidths of intervals at each point does not exceed C _a . The goal is to minimize the total capacity of all the colors used. We consider the bounded model, where all capacities must be chosen in the range (0,1], and the unbounded model, where the algorithm may use colors of any positive capacity. For the absolute competitive ratio, we give an upper bound of 14 and a lower bound of 4.59 for the bounded model, and an upper bound of 4 and a matching lower bound of 4 for the unbounded model. We also consider the offline version of these problems and show that whereas the unbounded model is polynomially solvable, the bounded model is NP-hard in the strong sense and admits a 3.6-approximation algorithm. A preliminary version of this paper has appeared in the Proceedings of the 10th Scandinavian Workshop on Algorithm Theory (SWAT 2006), Lecture Notes in Computer Science, Vol. 4059, pp. 29–40, Springer, 2006.     

面向不确定数据模式指标的通用界值估算方法

针对约束模式挖掘中模式指标的界值估算问题,提出了一种面向不确定数据模式指标的通用界值估算方法。根据带有权值的不确定型事务数据库的特点,首先设计了面向常用模式指标的通用界值估算框架,其次给出了在该框架下对模式指标上界值的快速估算方法,最后估计了两种典型模式指标的上界值以说明其可行性。实验中对比了PHUI-UP算法分别结合事务加权效用值、所提方法估算所得的上界值和实际上界值后的运行时间和内存占用情况,实验结果表明所提方法可以通过占用较小内存和运行时间来实现模式效用上界值的估算。     

Lower bounds for maximal and convex layers problems

In this paper we derive tight lower bounds for the maximal and convex layers problems in the plane. Our lower bound proofs for the maxima problem and convex hull problem are simpler than those previously known. We also obtain an (nlog n) lower bound for the maximal depth problem, and the convex depth problem, when the points are given in sorted order of their x-coordinates.     

最小费用充电站选址问题的分支定界算法

电动汽车的充电站选址问题是当前社会的热点问题,其实质是组合优化中经典的NP-hard问题。基于最小开设费用对充电站选址问题进行研究,首先对该问题进行了数学建模,进而研究了该问题的数学性质并给予相应的证明,利用这些性质减小问题的规模,从而降低问题的求解难度;然后设计了上下界子算法以及降阶子算法,基于这些子算法提出了一种可以快速缩小问题规模同时得到最优解的分支定界算法,降低了时间复杂度,同时可以对解空间进行大量剪枝加快求解速度;最后通过分析和求解一个示例来进一步阐述所提算法的原理和执行过程。