Search

Graph cuts are widely used in computer vision. To speed up the optimization process and improve the scalability for large graphs, Strandmark and Kahl introduced a splitting method to split a graph into multiple subgraphs for parallel computation in both shared and distributed memory models. However, this parallel algorithm (the parallel BK-algorithm) does not have a polynomial bound on the number of iterations and is found to be non-convergent in some cases due to the possible multiple optimal solutions of its sub-problems. To remedy this non-convergence problem, in this paper, we first introduce a merging method capable of merging any number of those adjacent sub-graphs that can hardly reach agreement on their overlapping regions in the parallel BK-algorithm. Based on the pseudo-boolean representations of graph cuts, our merging method is shown to be effectively reused all the computed flows in these sub-graphs. Through both splitting and merging, we further propose a dynamic parallel and distributed graph cuts algorithm with guaranteed convergence to the globally optimal solutions within a predefined number of iterations. In essence, this paper provides a general framework to allow more sophisticated splitting and merging strategies to be employed to further boost performance. Our dynamic parallel algorithm is validated with extensive experimental results. [ABSTRACT FROM PUBLISHER]

Time–cost trade-off analysis is addressed as an important aspect of any construction project planning and control. Nonexistence of a unique solution makes the time–cost trade-off problems very difficult to tackle. As a combinatorial optimization problem one may apply heuristics or mathematical programming techniques to solve time–cost trade-off problems. In this paper, a new multicolony ant algorithm is developed and used to solve the time–cost multiobjective optimization problem. Pareto archiving together with innovative solution exchange strategy are introduced which are highly efficient in developing the Pareto front and set of nondominated solutions in a time–cost optimization problem. An 18-activity time–cost problem is used to evaluate the performance of the proposed algorithm. Results show that the proposed algorithm outperforms the well-known weighted method to develop the nondominated solutions in a combinatorial optimization problem. The paper is more relevant to researchers who are interested in developing new quantitative methods and/or algorithms for managing construction projects. [ABSTRACT FROM AUTHOR]

To reduce field-programmable gate array power, Vdd programmability has been recently proposed to select the Vdd level for interconnects and power-gate unused interconnects. However, Vdd-level converters used in the existing Vdd-programmable method consume a large amount of leakage. This paper proposes two ways to avoid using level converters in interconnects, namely; 1) tree-based level converter insertion (TLC) and 2) dual-Vdd tree-based level converter insertion (dTLC). TLC enforces that there is only one Vdd level within each routing tree, while dTLC can have different Vdd levels within a routing tree, but no VddL switch drives VddH switches. Dual-Vdd assignment algorithms were developed considering chip-level time slack allocation for maximum power reduction. The algorithms include TLC-S and dTLC-S, two power sensitivity-based algorithms with implicit time slack allocation, and dTLC-LP, a linear programming (LP)-based algorithm with explicit time slack allocation. All allocate time slack first to interconnects with higher power sensitivity and assign low Vdd to them for more power reduction. Experiments show that dTLC-LP obtains the lowest power consumption. Compared to dTLC-LP, dTLC-S obtains a slightly higher power consumption but runs three times faster. Compared to the existing segment-based level converter insertion for dual Vdd, dTLC-LP reduces interconnect power by 52.90% without performance loss for Microelectronics Center of North Carolina benchmark circuits. [ABSTRACT FROM AUTHOR]

Random hypothesis generation is central to robust geometric model fitting in computer vision. The predominant technique is to randomly sample minimal subsets of the data, and hypothesize the geometric models from the selected subsets. While taking minimal subsets increases the chance of successively “hitting” inliers in a sample, hypotheses fitted on minimal subsets may be severely biased due to the influence of measurement noise, even if the minimal subsets contain purely inliers. In this paper we propose Random Cluster Models, a technique used to simulate coupled spin systems, to conduct hypothesis generation using subsets larger than minimal. We show how large clusters of data from genuine instances of the model can be efficiently harvested to produce accurate hypotheses that are less affected by the vagaries of fitting on minimal subsets. A second aspect of the problem is the optimization of the set of structures that best fit the data. We show how our novel hypothesis sampler can be integrated seamlessly with graph cuts under a simple annealing framework to optimize the fitting efficiently. Unlike previous methods that conduct hypothesis sampling and fitting optimization in two disjoint stages, our algorithm performs the two subtasks alternatingly and in a mutually reinforcing manner. Experimental results show clear improvements in overall efficiency. [ABSTRACT FROM PUBLISHER]

In this paper, we study Stochastic Composite Optimization (SCO) for sparse learning that aims to learn a sparse solution from a composite function. Most of the recent SCO algorithms have already reached the optimal expected convergence rate \mathcal O(1/\lambda T) , but they often fail to deliver sparse solutions at the end either due to the limited sparsity regularization during stochastic optimization (SO) or due to the limitation in online-to-batch conversion. Even when the objective function is strongly convex, their high probability bounds can only attain \mathcal O(\sqrt\log (1/\delta)/T) with $\delta$ is the failure probability, which is much worse than the expected convergence rate. To address these limitations, we propose a simple yet effective two-phase Stochastic Composite Optimization scheme by adding a novel powerful sparse online-to-batch conversion to the general Stochastic Optimization algorithms. We further develop three concrete algorithms, OptimalSL, LastSL and AverageSL, directly under our scheme to prove the effectiveness of the proposed scheme. Both the theoretical analysis and the experiment results show that our methods can really outperform the existing methods at the ability of sparse learning and at the meantime we can improve the high probability bound to approximately \mathcal {O}(\log (\log (T)/\delta)/\lambda T) . [ABSTRACT FROM AUTHOR]

This paper proposes an optimization algorithm, the dimension-down iterative algorithm (DDIA), for solving a mixed transportation network design problem (MNDP), which is generally expressed as a mathematical programming with equilibrium constraint (MPEC). The upper level of the MNDP aims to optimize the network performance via both the expansion of the existing links and the addition of new candidate links, whereas the lower level is a traditional Wardrop user equilibrium (UE) problem. The idea of the proposed solution algorithm (DDIA) is to reduce the dimensions of the problem. A group of variables (discrete/continuous) is fixed to optimize another group of variables (continuous/discrete) alternately; then, the problem is transformed into solving a series of CNDPs (continuous network design problems) and DNDPs (discrete network design problems) repeatedly until the problem converges to the optimal solution. The advantage of the proposed algorithm is that its solution process is very simple and easy to apply. Numerical examples show that for the MNDP without budget constraint, the optimal solution can be found within a few iterations with DDIA. For the MNDP with budget constraint, however, the result depends on the selection of initial values, which leads to different optimal solutions (i.e., different local optimal solutions). Some thoughts are given on how to derive meaningful initial values, such as by considering the budgets of new and reconstruction projects separately. [ABSTRACT FROM AUTHOR]

Phasor Measurement Units (PMUs) are the backbone of smart grids that are able to measure power system observability in real-time. The deployment of synchronized sensors in power networks opens up the advantage of real-time monitoring of the network state. An optimal number of PMUs must be installed to ensure system observability. For that reason, an objective function is minimized, reflecting the cost of PMU installation around the power grid. As a result, a minimization model is declared where the objective function is defined over an adequate number of constraints on a binary decision variable domain. To achieve maximum network observability, there is a need to find the best number of PMUs and put them in appropriate locations around the power grid. Hence, maximization models are declared in a decision-making way to obtain optimality satisfying a guaranteed stopping and optimality criteria. The best performance metrics are achieved using binary integer, semi-definite, and binary polynomial models to encounter the optimal number of PMUs with suitable PMU positioning sites. All optimization models are implemented with powerful optimization solvers in MATLAB to obtain the global solution point. [ABSTRACT FROM AUTHOR]

This work investigates the design of linear precoders in cooperative multi-cell MIMO downlink coverage for finite-alphabet source signals. Traditional design of multi-cell MIMO downlink precoder relies on Gaussian input assumption, which may lead to performance loss when true data inputs consist of discrete non-Gaussian symbols. This work presents optimized precoders for finite-alphabet input by maximizing the sum rate under per-base station power constraints. Specifically, we propose two distributed algorithms: a finite-alphabet signal Gaussian interference gradient projection algorithm and a block diagonalization alternating optimization algorithm while supporting interference cancellation. Our numerical results demonstrate considerable performance gain in terms of approximate transmission data rate as well as decoded bit error rate over precoding schemes designed by using the non-realistic Gaussian input assumption. [ABSTRACT FROM PUBLISHER]

The statistical nature of gate delays in current day technologies necessitates the use of measures, such as path criticality and node/edge criticality for timing optimization. Node criticalities are typically computed using the complementary path delay. An alternative approach to compute the criticality using the circuit delay has been recently proposed. In this paper, we discuss in detail, the use of circuit delay to compute node criticalities and show that the criticality thus found is not equal to the conventional measure found using complementary path delay. However, there is a monotonic relationship between them and the two measures can be used interchangeably. We derive new bounds for the global criticality and propose a pruning algorithm based on these bounds to improve the accuracy and speed of computation. The use of this pruning technique results in a significant speedup in criticality computations. We obtain an order of magnitude average speedup for ISCAS benchmarks. [ABSTRACT FROM PUBLISHER]

In this paper, we investigate the problem of fair resource allocation based on the Nash bargaining solution (NBS) over wireless amplify-and-forward (AF) relay networks in which variable-rate users and constant-rate users coexist. Via the dual decomposition method, a distributed algorithm, including relay selection, relay power allocation, and rate adaptation, is proposed. When the number of users is large and/or the rate constraints are stringent, the problem becomes infeasible, and admission control is necessary. We formulate the admission control and fair resource allocation problem as a two-stage optimization problem, aiming to first find the maximal number of users the network can support with guaranteed rates and then allocate resources based on NBS for the admitted users. Since the problem is combinatorially hard, we transform it into an equivalent one-stage optimization problem, which can be solved by existing methods but with a higher computational complexity. To further reduce the computational complexity, a suboptimal algorithm is then developed. Simulations verify the convergence and fairness of the distributed algorithm. Simulations also show that the suboptimal algorithm achieves an approximate optimal performance but with a significant running time reduction. [ABSTRACT FROM PUBLISHER]

This paper deals with establishing an optimum inspection schedule for systems that are subject to random failure and where the failure can be detected only through an inspection. The paper reviews 'classical' optimum checking policies. Two new optimization models are proposed to find the optimum sequence of inspection times. Theoretical analysis and numerical examples show that the optimum inspection time sequence derived from the proposed models is relatively accurate, robust, and computationally simple. [ABSTRACT FROM AUTHOR]

Many signal processing applications pose optimization problems with multimodal and nonsmooth cost functions. Gradient methods are ineffective in these situations, and optimization methods that require no gradient and can achieve a global optimal solution are highly desired to tackle these difficult problems. The paper proposes a guided global search optimization technique, referred to as the repeated weighted boosting search. The proposed optimization algorithm is extremely simple and easy to implement, involving a minimum programming effort. Heuristic explanation is given for the global search capability of this technique. Comparison is made with the two better known and widely used guided global search techniques, known as the genetic algorithm and adaptive simulated annealing, in terms of the requirements for algorithmic parameter tuning. The effectiveness of the proposed algorithm as a global optimizer are investigated through several application examples. [ABSTRACT FROM AUTHOR]

Practical optimization of infrastructure preservation works programming has always posed a computational challenge due to the complexity and scale of the problem. Critical to the process is formulations in which the identity of individual projects is preserved. This requirement leads to exponential growth of solution space, often resulting in an unmanageable process using traditional analytical optimization techniques. In this paper, we propose an evolutionary-based multiyear optimization procedure for solving network level infrastructure works programming problems using a relatively new concept known as the shuffled complex evolution algorithm. A case study problem is analyzed to illustrate the robustness of the technique. The findings show convergence characteristics of the solution and demonstrate that the algorithm is very efficient and consistent in simultaneous consideration of the trade-off among various infrastructure preservation strategies. It is concluded that the robust search capability of the shuffled complex evolution technique is well suited for solving the combinatorial problems in network level infrastructure preservation works programming. [ABSTRACT FROM AUTHOR]

Evolutionary Computation (EC) has attracted increasing attention in recent years, as powerful computational techniques, for solving many complex real-world problems. The Operations Research (OR)/Optimization community is divided on the acceptability of these techniques. One group accepts these techniques as potential heuristics for solving complex problems and the other rejects them on the basis of their weak mathematical foundations. In this paper, we discuss the reasons for using EC in optimization. A brief review of Evolutionary Algorithms (EAs) and their applications is provided. We also investigate the use of EAs for solving a two-stage transportation problem by designing a new algorithm. The computational results are analyzed and compared with conventional optimization techniques. [ABSTRACT FROM AUTHOR]

This paper investigates a new variation in the continuous single facility location problem. Specifically, we address the problem of locating a new facility on a plane with different distance norms on different sides of a boundary line. Special cases and extensions of the problem, where there are more than two regions are also discussed. Finally, by investigating the properties of the models, efficient solution procedures are proposed. [ABSTRACT FROM AUTHOR]

The classical deterministic scheduling problem of minimizing the makespan on unrelated parallel processors is known to be NP-hard in the strong sense. Given the mixed integer linear model with binary decision variables, this paper presents heuristic algorithms based on partial enumeration. Basically, they consist in the construction of mixed integer subproblems, considering the integrality of some subset of variables, formulated using the information obtained from the solution of the linear relaxed problem. Computational experiments are reported for a collection of test problems, showing that some of the proposed algorithms achieve better solutions than other relevant approximation algorithms published up to now. [ABSTRACT FROM AUTHOR]

Abstract: This paper presents dynamic programming algorithms for generating optimal guillotine-cutting patterns of equal rectangles. The algorithms are applicable for solving the unconstrained problem where the blank demand is unconstrained, the constrained problem where the demand is exact, the unconstrained problem with blade length constraint, and the constrained problem with blade length constraint. The algorithms are able to generate the simplest optimal patterns to simplify the cutting process. When the sheet length is longer than the blade length of the guillotine shear used, the dynamic programming algorithm is applied to generate optimal layouts on segments of lengths no longer than the blade length, and the knapsack algorithm is employed to find the optimal layout of the segments on the sheet. The computational results indicate that the algorithms presented are more efficient than the branch-and-bound algorithms, which are the best algorithms so far that can guarantee the simplest patterns. [Copyright &y& Elsevier]

Abstract: Trigeneration is a booming technology for efficient and clean provision of energy. It has potential for reducing pollution emissions dramatically. Similar to combined heat and power (CHP) production, cost-efficient operation of a trigeneration system can be planned using an optimization model based on hourly load forecasts. A long-term planning model decomposes into thousands of hourly models, which can be solved separately. In this paper, we model the hourly trigeneration problem as a linear programming (LP) model with a joint characteristic for three energy components to minimize simultaneously the production and purchase costs of three energy components, as well as CO2 emissions costs. Then we explore the structure of the problem and propose the specialized Tri-Commodity Simplex (TCS) algorithm that employs this structure efficiently. The speed of TCS is based on extremely fast basis inverse operations and reuse of old basic solutions from previously solved hourly models. We compare the performance of TCS with realistic models against an efficient sparse Simplex code using the product form of inverse. In test runs, TCS is from 36 to 58 times faster when starting from the initial basis and from 43 to 179 times faster when reusing the old basis. [Copyright &y& Elsevier]

The interconnection of vehicles in the future fifth generation (5G) wireless ecosystem forms the so-called Internet of Vehicles (IoV). IoV offers new kinds of applications requiring delay-sensitive, compute-intensive, and bandwidth-hungry services. Mobile edge computing (MEC) and network slicing are two of the key enabler technologies in 5G networks that can be used to optimize the allocation of the network resources and guarantee the diverse requirements of IoV applications. As traditional model-based optimization techniques generally end up with NP-hard and strongly non-convex and nonlinear mathematical programming formulations, in this article, we introduce a model-free approach based on deep reinforcement learning (DRL) to solve the resource allocation problem in MEC-enabled IoV networks based on network slicing. Furthermore, the solution uses non-orthogonal multiple access (NOMA) to enable better exploitation of the scarce channel resources. The considered problem addresses jointly the channel and power allocation, the slice selection, and the vehicle selection (vehicle grouping). We model the problem as a single-agent Markov decision process. Then we solve it using DRL with the well-known deep Q learning (DQL) algorithm. We show that our approach is robust and effective under different network conditions compared to benchmark solutions. [ABSTRACT FROM AUTHOR]

Generally, the probabilistic linguistic term set (PLTS) provides more accurate descriptive properties than the hesitant fuzzy linguistic term set does. The probabilistic linguistic preference relation (PLPR), which is applied to deal with complex decision-making problems, can be constructed for PLTSs. However, it is difficult for decision makers to provide the probabilities of occurrence for PLPR. To deal with this problem, we propose a definition of expected consistency for PLPR and establish a probability computing model to derive probabilities of occurrence in PLPR with priority weights for alternatives. A consistency-improving iterative algorithm is presented to examine whether or not the PLPR is at an acceptable consistency. Moreover, the consistency-improving iterative algorithm should obtain the satisfaction consistency level for the unacceptable consistency PLPR. Finally, a real-world employment-city selection is used to demonstrate the effectiveness of the proposed method of deriving priority weights from PLPR. [ABSTRACT FROM AUTHOR]

We present efficient graph cut algorithms for three problems: (1) finding a region in an image, so that the histogram (or distribution) of an image feature within the region most closely matches a given model; (2) co-segmentation of image pairs and (3) interactive image segmentation with a user-provided bounding box. Each algorithm seeks the optimum of a global cost function based on the Bhattacharyya measure, a convenient alternative to other matching measures such as the Kullback–Leibler divergence. Our functionals are not directly amenable to graph cut optimization as they contain non-linear functions of fractional terms, which make the ensuing optimization problems challenging. We first derive a family of parametric bounds of the Bhattacharyya measure by introducing an auxiliary labeling. Then, we show that these bounds are auxiliary functions of the Bhattacharyya measure, a result which allows us to solve each problem efficiently via graph cuts. We show that the proposed optimization procedures converge within very few graph cut iterations. Comprehensive and various experiments, including quantitative and comparative evaluations over two databases, demonstrate the advantages of the proposed algorithms over related works in regard to optimality, computational load, accuracy and flexibility. [ABSTRACT FROM AUTHOR]

We present a branch-and-bound algorithm for discretely-constrained mathematical programs with equilibrium constraints (DC-MPEC). This is a class of bilevel programs with an integer program in the upper-level and a complementarity problem in the lower-level. The algorithm builds on the work by Gabriel et al. (Journal of the Operational Research Society 61(9):1404-1419, ) and uses Benders decomposition to form a master problem and a subproblem. The new dynamic partition scheme that we present ensures that the algorithm converges to the global optimum. Partitioning is done to overcome the non-convexity of the Benders subproblem. In addition Lagrangean relaxation provides bounds that enable fathoming in the branching tree and warm-starting the Benders algorithm. Numerical tests show significantly reduced solution times compared to the original algorithm. When the lower level problem is stochastic our algorithm can easily be further decomposed using scenario decomposition. This is demonstrated on a realistic case. [ABSTRACT FROM AUTHOR]

Several pure binary integer optimization models are developed for clustering time periods by similarity for electricity utilities seeking assistance with pricing strategies. The models include alternative objectives for characterizing various notions of within-cluster distances, admit as feasible only clusters that are contiguous, and allow for circularity, where time periods at the beginning and end of the planning cycle may be in the same cluster. Restrictions upon cluster size may conveniently be included without the need of additional constraints. The models are populated with a real-world dataset of electricity usage for 93 buildings and solutions and run-times attained by conventional optimization software are compared with those by dynamic programming, or by a greedy algorithm applicable to one of the models, that run in polynomial time. The results provide time-of-use segments that an electricity utility may employ for selective pricing for peak and off-peak time periods to influence demand for the purpose of load leveling. [ABSTRACT FROM PUBLISHER]

In this correspondence, we present a new and fast design algorithm for perfect-reconstruction (PR), maximally decimated, uniform, cosine-modulated filter banks. Perfect reconstruction is obtained within arithmetic machine precision. The new design does not need numerical optimization routines and is significantly faster than a competing method based on second-order cone programming (SOCP). The proposed design algorithm finds the optimum solution by iteratively solving a quadratic programming problem with linear equality constraints. By a special modification of the basic algorithm, we obtain PR filter banks with high stopband attenuations. In addition, fast convergence is verified by designing PR filter banks with up to 128 channels. [ABSTRACT FROM PUBLISHER]

Classic bilevel programming deals with two level hierarchical optimization problems in which the leader attempts to optimize his/her objective, subject to a set of constraints and his/her follower’s solution. In modelling a real-world bilevel decision problem, some uncertain coefficients often appear in the objective functions and/or constraints of the leader and/or the follower. Also, the leader and the follower may have multiple conflicting objectives that should be optimized simultaneously. Furthermore, multiple followers may be involved in a decision problem and work cooperatively according to each of the possible decisions made by the leader, but with different objectives and/or constraints. Following our previous work, this study proposes a set of models to describe such fuzzy multi-objective, multi-follower (cooperative) bilevel programming problems. We then develop an approximation Kth-best algorithm to solve the problems. [ABSTRACT FROM AUTHOR]

Copyright of Canadian Journal of Civil Engineering is the property of Canadian Science Publishing and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)

We present a new method (MMSE-Threshold) for peak/average power reduction. This technique is derived from a constellation shaping algorithm, where the constellation points with lower average energy are selected from a larger set of points. There are multiple choices available to select the points with lower peak energy for a given sequence of data bits, and this flexibility is used to reduce the peak to average power ratio (PAPR). Subsequently, this selection algorithm, which is formulated in terms of a zero-one quadratic problem, is optimized by the semidefinite programming algorithm (SDPA). Simulation results show that the PAPR of SDPA is noticeably better than MMSE-Threshold, while the complexity of MMSE-Threshold is smaller than that of SDPA. MMSE-Threshold is compared with alternative techniques reported in the literature. We show that, while we obtain a PAPR that is similar or better than those of the compared techniques, the complexity of MMSE-Threshold is low. In addition, the MMSE-Threshold method results in about 1 dB shaping gain (reduction in the average energy) with less than 1% rate loss for PAPR reduction. [ABSTRACT FROM AUTHOR]