Search

We consider stochastic algorithms derived from methods for solving deterministic optimization problems, especially comparison-based algorithms derived from stochastic approximation algorithms with a constant step-size. We develop a methodology for proving geometric convergence of the parameter sequence { θ n } n ⩾ 0 of such algorithms. We employ the ordinary differential equation (ODE) method, which relates a stochastic algorithm to its mean ODE, along with a Lyapunov-like function Ψ such that the geometric convergence of Ψ (θ n) implies – in the case of an optimization algorithm – the geometric convergence of the expected distance between the optimum and the search point generated by the algorithm. We provide two sufficient conditions for Ψ (θ n) to decrease at a geometric rate: Ψ should decrease "exponentially" along the solution to the mean ODE, and the deviation between the stochastic algorithm and the ODE solution (measured by Ψ) should be bounded by Ψ (θ n) times a constant. We also provide practical conditions under which the two sufficient conditions may be verified easily without knowing the solution of the mean ODE. Our results are any-time bounds on Ψ (θ n) , so we can deduce not only the asymptotic upper bound on the convergence rate, but also the first hitting time of the algorithm. The main results are applied to a comparison-based stochastic algorithm with a constant step-size for optimization on continuous domains. [ABSTRACT FROM AUTHOR]

Abstract Nowadays, several crowdsourcing projects exploit social choice methods for computing an aggregate ranking of alternatives given individual rankings provided by workers. Motivated by such systems, we consider a setting where each worker is asked to rank a fixed (small) number of alternatives and, then, a positional scoring rule is used to compute the aggregate ranking. Among the apparently infinite such rules, what is the best one to use? To answer this question, we assume that we have partial access to an underlying true ranking. Then, the important optimization problem to be solved is to compute the positional scoring rule whose outcome, when applied to the profile of individual rankings, is as close as possible to the part of the underlying true ranking we know. We study this fundamental problem from a theoretical viewpoint and present positive and negative complexity results and, furthermore, complement our theoretical findings with experiments on real-world and synthetic data. [ABSTRACT FROM AUTHOR]

Highlights • Algorithm for calibration of car-following model for large-scale microscopic network models. • City-scale case study is carried out, the approach is shown to be computationally efficient and suitable for large-scale network models. • Compared to a traditional approach, it improves the objective function by two orders of magnitude and it improves the fit to link speeds by one order of magnitude. Abstract This paper proposes a simulation-based optimization methodology for the efficient calibration of microscopic traffic flow models (i.e., car-following models) of large-scale stochastic network simulators. The approach is a metamodel simulation-based optimization (SO) method. To improve computational efficiency of the SO algorithm, problem-specific and simulator-specific structural information is embedded into a metamodel. As a closed-form expression is sought, we propose adopting the steady-state solution of the car-following model as an approximation of its simulation-based input-output mapping. This general approach is applied for the calibration of the Gipps car-following model embedded in a microscopic traffic network simulator, on a large network. To this end, a novel formulation for the traffic stream models corresponding to the Gipps car-following law is provided. The proposed approach identifies points with good performance within few simulation runs. Comparing its performances to that of a traditional approach, which does not take advantage of the structural information, the objective function is improved by two orders of magnitude in most experiments. Moreover, this is achieved within tight computational budgets, i.e., few simulation runs. The solutions identified improve the fit to the field measurements by one order of magnitude, on average. The structural information provided to the metamodel is shown to enable the SO algorithm to become robust to both the quality of the initial points and the simulator stochasticity. [ABSTRACT FROM AUTHOR]

Abstract One of the most prevalent methods for enhanced oil recovery in heavy oil reservoirs is thermal techniques. Fast-SAGD process is an advance method of enhance oil recovery in which offset wells are drilled for cyclic steam injection and production. This leads to increasing the production efficiency. Optimization of this process was performed using various techniques including genetic algorithm (GA), imperialist competitive algorithm (ICA), and particle swarm optimization (PSO). Combination of recovery factor and cumulative steam to oil ratio was introduced as the objective function. This study represents a novel supplementary technique implemented in optimization algorithms to increase its speed, significantly. In this technique, effective parameters were defined using sensitivity analysis. Then they were converted to discrete variables. To discretize the selected parameters, three different functions including logarithmic, square, and linear were applied using Minitab 18. Moreover, repetition inhibitory algorithm (RIA) was implemented in optimization algorithms for the first time to prevent recalculation of duplicate states in optimization for the next generation, and to speed-up the optimization process. The results of sensitivity analysis indicated that maximum and minimum effective parameters were attributed to Fast-SAGD production well height and soak time, respectively. Results indicated that among various optimization algorithms, GA worked 6% better in comparison to other optimization techniques and linear discretization function resulted in better optimized point in a shorter time. Results indicated that optimization process using discrete variables and repetition inhibitory algorithm led to the optimized point 6.33 times faster than discrete optimization procedure without RIA. This was 16.46 times faster in comparison to continuous optimization algorithm. Moreover using RIA led to termination of optimization algorithm 9.67 times faster than continuous mode. Highlights • ICA, GA, and PSO algorithms were applied for Fast SAGD optimization. GA represented a medium speed with most accurate results and ICA displayed a high speed performance. • Linear, logarithmic and square functions were applied for discretization of optimization parameters among which linear function was more satisfactory. • Implementing the repetition inhibitory algorithm in optimization process, proved the importance of this innovative method for increasing the speed of optimization process in reservoir simulation studies. [ABSTRACT FROM AUTHOR]

The robustness of realistic infrastructure systems is a significant and long-term research question, which has gotten some constructive outcomes borrowing the framework of complex networks. In this paper, we further explore the method about utilizing optimization algorithms to enhance robustness of interdependent networks. Firstly, we propose a novel particle swarm optimization algorithm with an information feedback mechanism to achieve better performance on complex problems. Secondly, we analyze the solutions from initial loads and types of failed nodes resulted by our algorithm. Interestingly, relative to traditional setup, our algorithm indeed produces a robust resource allocation pattern for interdependent networks, where middle-degree nodes are assigned more tolerance. [ABSTRACT FROM AUTHOR]

Highlights • A Gaussian process based model is constructed to simulate a complex biological system. • Model accuracy and predictive capability is compared against the neural network model. • Dynamic optimisation under uncertainty is conducted to maximise algal lutein production. • A framework to build bioprocess models with Gaussian Processes is presented. Abstract Dynamic modeling is an important tool to gain better understanding of complex bioprocesses and to determine optimal operating conditions for process control. Currently, two modeling methodologies have been applied to biosystems: kinetic modeling, which necessitates deep mechanistic knowledge, and artificial neural networks (ANN), which in most cases cannot incorporate process uncertainty. The goal of this study is to introduce an alternative modeling strategy, namely Gaussian processes (GP), which incorporates uncertainty but does not require complicated kinetic information. To test the performance of this strategy, GPs were applied to model microalgae growth and lutein production based on existing experimental datasets and compared against the results of previous ANNs. Furthermore, a dynamic optimization under uncertainty is performed, avoiding over-optimistic optimization outside of the model's validity. The results show that GPs possess comparable prediction capabilities to ANNs for long-term dynamic bioprocess modeling, while accounting for model uncertainty. This strongly suggests their potential applications in bioprocess systems engineering. [ABSTRACT FROM AUTHOR]

Highlights • Dynamic RTO of distributed MPC systems using closed-loop prediction. • The interaction between distributed MPCs and plant dynamics is fully considered. • Approximation techniques are applied to improve computational efficiency. • Significant reduction in computation times achieved with little loss in performance. • The two-level control architecture is readily applicable to industrial processes. Abstract A dynamic real-time optimization (DRTO) strategy has recently been proposed for coordination of distributed MPC systems. The scheme utilizes a prediction model that accounts for the impact of the distributed controllers on the plant response. Two techniques are presented for approximating the closed-loop prediction within the DRTO formulation - a hybrid closed-loop and an input clipping formulation. The hybrid formulation generates closed-loop predictions for a limited number of time intervals along the DRTO prediction horizon, followed by an open-loop optimal control formulation for the rest of the horizon. The input clipping formulation utilizes an unconstrained MPC optimization formulation for each distributed MPC, coupled with an input saturation mechanism. The performance of the approximation techniques is evaluated through application to case studies based on linear and nonlinear dynamic plant models respectively. The approximation techniques are demonstrated to be more computationally efficient than the rigorous counterpart without significant loss in performance. [ABSTRACT FROM AUTHOR]

Highlights • An enhanced surrogate assisted framework for constrained global optimization is proposed. • Maximizing probability of improvement approach is used for selecting infill points. • Kriging meta-models of objective and constraints functions are updated in every iteration. • Meta-model of objective function is local optimized when it's sufficient mature. • Numerical results indicate that the framework is suitable for use in solving computationally expensive and constrained black-box optimization. Abstract An enhanced surrogate assisted framework, based on Probability of Improvement (PI) method, is proposed in this paper. We made some modifications to the original PI approach to enhance the performance of the modeling and optimization framework, leading to fewer rigorous simulations to find the optimal solution without loss of accuracy. We also extended the algorithm for handling general constraints using a fully probabilistic approach. The behavior of the proposed framework was investigated through a set of 9 Unconstrained Test Functions (UTF), 7 Constrained Optimization Problems (COP) and 3 Chemical Engineering Problems (CEP). The numerical results indicate that a lower number of rigorous model simulations were needed for optimizing UTF compared to the classic PI method and that the proposed framework was capable of achieving sustained near optimal solutions for COP and CEP. These results indicate that the proposed framework is suitable for solving computationally expensive constrained black-box optimization problems. [ABSTRACT FROM AUTHOR]

Highlights • Simulation study to economics optimizing control and robust multi-stage optimizing control. • Discussion of numerical aspects of optimizing control as well as the software realization using high-fidelity high-dimensional process models of complex chemical processes. • Control problem formulation for the dynamic product changeover in a multi-product process. • Robustification of economics optimizing control by multi-stage nonlinear model predictive control in case of the presence of model uncertainty. Abstract By the use of online optimization, the profitability of chemical processes can be enhanced while meeting process-related, environmental and ecological constraints. Two well-known techniques to achieve an economically optimal operation of chemical processes are repetitive stationary optimization (RTO) combined with advanced control and direct economics optimizing control on a receding horizon (also called one-layer approach or dynamic RTO). Direct economics optimizing control can react faster to disturbances and is better suited for the optimization of transients between different products. On the other hand it is computationally demanding and requires sufficiently accurate dynamic models. In this paper, we discuss economics optimizing control of a very complex process, a multi-product transesterification reaction that is realized in a reactive distillation process. The process model, the specification of the economics optimizing controller, the implementation of the dynamic optimization, and the robustification of the controller by a multi-stage approach are discussed using simulation studies. [ABSTRACT FROM AUTHOR]

Highlights • A novel piecewise state feedback controller is introduced. • The chemical process optimal control problem is formulated as an optimal control problem of switched dynamical systems. • A gradient-based parallel optimization algorithm is developed for solving the optimal control. • Convergence results indicate that the gradient-based parallel optimization algorithm is global convergent. • Three chemical process optimal control problems are given to illustrate the effectiveness of the proposed algorithm. Abstract This paper considers an optimal control problem of chemical processes with a novel piecewise state-feedback controller. Firstly, the chemical process optimal control problem is formulated as a switched dynamical system optimal control problem, which can be transformed into a parameter optimization problem. Next, to achieve rapid convergence from remote starting points, we propose a novel gradient-based optimization algorithm, which is suitable to a parallel implementation because the step is improved by updating its direction as well as its length simultaneously before moving to the next iteration, and the step computation involves only the inner products of vectors. Then, the convergent properties of the parameter optimization problem to the original optimal control problem are discussed. Finally, the numerical simulation results show that the gradient-based parallel optimization algorithm is an effective alternative method for solving the chemical process optimal control problems. [ABSTRACT FROM AUTHOR]

Highlights • A superstructure of methanation unit is proposed, and the topology of methanation unit is optimized for the coal-to-SNG process. • Simultaneous optimization and heat integration are performed along with the area targeting. • A sequential method is used to provide initial values for the simultaneous model. • Compared with industrial data, the exergy efficiency is improved by 0.77% and TAC can reduce by 10.36 MM$·a−1 for the coal-to-SNG process. Abstract The area of the heat recovery network has a significant impact on the economic performance of the coal-to-SNG process. This paper proposes a superstructure of the methanation unit, and the number of the methanator, recycle gas extraction position (RGEXP), as well as the operating conditions, are optimized. Simultaneous optimization and heat integration are performed along with the area targeting to weigh against the operating cost and capital cost of the coal-to-SNG process. Area cost is evaluated by assuming vertical heat transfer between cold and hot composite curves. A sequential method is used to provide initial values for the simultaneous model. Results show that Case7 (2) has the best economic performance, which has 7 methanators and recycled gas is extracted from the 2nd methanator. The total annual cost of Case7 (2) can be reduced by 10.36 MM$·a−1, and exergy efficiency can be also improved by 0.77% compared with an industrial plant. [ABSTRACT FROM AUTHOR]

Highlights • A novel Kriging-based adaptive sampling framework is proposed for the optimization of stochastically constrained black-box systems. • With an innovative feasibility-enhanced infill criterion, the proposed algorithm is more robust in maintaining feasibility while returning a near-optimal solution. • The efficacy of this algorithm is demonstrated with low-dimensional benchmark problems and a pharmaceutical case study. Abstract Stochastically constrained simulation optimization problems are challenging because the inherent noise terms to a black-box system lead to the need of considering the uncertainty at both the objective and the constraint function. To address this problem, we propose a Kriging-based optimization framework, which uses stochastic Kriging models to approximate the objective and the constraint functions and an adaptive sampling approach to sequentially search for the next point that is promising to have a better objective. The main contribution of this work is to incorporate a feasibility-enhanced term to the infill sampling criterion, which improves the Kriging-based algorithm's capabilities of returning a truly feasible near-optimal solution for stochastic systems. The efficacy of the Kriging-based algorithm is demonstrated with eight benchmark problems and a case study from the pharmaceutical manufacturing domain. [ABSTRACT FROM AUTHOR]

In the parallel k-stage flow-shops problem, we are given m identical k -stage flow-shops and a set of jobs. Each job can be processed by any one of the flow-shops but switching between flow-shops is not allowed. The objective is to minimize the makespan, which is the finishing time of the last job. This problem generalizes the classical parallel identical machine scheduling (where k = 1 ) and the classical flow-shop scheduling (where m = 1 ) problems, and thus it is NP-hard. We present a polynomial-time approximation scheme (PTAS) for the problem, when m and k are fixed constants. The key technique is to partition the jobs into big jobs and small jobs, enumerate over all feasible schedules for the big jobs, and handle the small jobs by solving a linear program and employing a “sliding” method. Such a technique has been used in the design of PTAS for several flow-shop scheduling variants. Our main contributions are the non-trivial application of this technique and a valid answer to the open question in the literature. [ABSTRACT FROM AUTHOR]

Phased mission systems (PMSs) have wide applications in engineering practices, especially in aerospace industry such as man-made satellite and spacecraft. To achieve high reliability in a PMS, certain critical parts in the system are designed to have a redundant architecture, such as cold standby (structural or functional). State-space models such as Markov processes have been widely used in previous studies to evaluate the reliabilities of these systems. But in practice, many real systems consist of mechanical components or mechatronics whose lifetime follow non-exponential distributions like the Weibull distribution. In this type of system, the Markov process is not capable of modeling the system behavior. In this paper, the SMP (Semi-Markov Process) is applied to solve the problem that the components’ lifetime in dynamic systems follows non-exponential distributions. An approximation algorithm for the SMP is proposed to assess the reliability of the PMSs consisting of non-exponential components. Furthermore, the accuracy and calculation efficiency of the approximation algorithm are explored. At last, the reliability assessment of a complex multi-phased altitude and orbit control system (AOCS) in a man-made satellite is presented to illustrate the method. [ABSTRACT FROM AUTHOR]

In this paper, we study the weighted two-stage stochastic fault-tolerant facility location problem. We present a deterministic LP-rounding 5-approximation algorithm by exploiting both of its stochastic and fault-tolerant structures. We further offer an improved randomized LP-rounding 3.8617-approximation algorithm along with the corresponding derandomized version with the same approximation ratio. [ABSTRACT FROM AUTHOR]

The geometric hitting set problem is one of the basic geometric combinatorial optimization problems: given a set P of points and a set D of geometric objects in the plane, the goal is to compute a small-sized subset of P that hits all objects in D . Recently Agarwal and Pan (2014) presented a near-linear time algorithm for the case where D consists of disks in the plane. The algorithm uses sophisticated geometric tools and data structures with large resulting constants. In this paper, we design a hitting-set algorithm for this case without the use of these data-structures, and present experimental evidence that our new algorithm has near-linear running time in practice, and computes hitting sets within 1.3-factor of the optimal hitting set. We further present dnet , a public source-code module that incorporates this improvement, enabling fast and efficient computation of small-sized hitting sets in practice. [ABSTRACT FROM AUTHOR]

Two most important evaluation parameters of any stereo matching algorithm are the execution speed and the accuracy of generated results. Commonly, reported real-time works provide fast depth calculation based on highly specialized hardware. Thus, algorithmic techniques for increasing the speed which can be employed on every general hardware, are more valuable. In this paper an efficient technique has been proposed in order to improve dynamic programming (dp) based dense stereo matching. The main idea is using a fast and efficient search space reduction algorithm and successively forcing dp based matching process to operate on this reduced search space (RSS). Effective ideas have been proposed to correct RSS and emphasize on more qualified candidates in RSS to facilitate and improve matching process in this space. Experimental results on standard stereo images show significant increasing of execution speed as well as error reduction for two traditional and basic versions of dp based matching algorithms. These simultaneous improvements in both speed and accuracy, considering their usual inverse relationship in other algorithms, seems to be very valuable. [ABSTRACT FROM AUTHOR]

The issue of integrating preference information into multi-objective optimization is considered, and a multi-objective framework based on decomposition and preference information, called indicator-based MOEA/D (IBMOEA/D), is presented in this study to handle the multi-objective optimization problems more effectively. The proposed algorithm uses a decomposition-based strategy for evolving its working population, where each individual represents a subproblem, and utilizes a binary quality indicator-based selection for maintaining the external population. Information obtained from the quality improvement of individuals is used to determine which subproblem should be invested at each generation by a power law distribution probability. Thus, the indicator-based selection and the decomposition strategy can complement each other. Through the experimental tests on seven many-objective optimization problems and one discrete combinatorial optimization problem, the proposed algorithm is revealed to perform better than several state-of-the-art multi-objective evolutionary algorithms. The effectiveness of the proposed algorithm is also analyzed in detail. [ABSTRACT FROM AUTHOR]

We study in this paper min max robust combinatorial optimization problems for an uncertainty polytope that is defined by knapsack constraints, either in the space of the optimization variables or in an extended space. We provide exact and approximation algorithms that extend the iterative algorithms proposed by Bertsimas and Sim (2003). We also study the limitation of the approach and point out NP -hard situations. Then, we approximate axis-parallel ellipsoids with knapsack constraints and provide an approximation scheme for the corresponding robust problem. The approximation scheme is also adapted to handle the intersection of an axis-parallel ellipsoid and a box. [ABSTRACT FROM AUTHOR]

We introduce a novel algorithm for approximating the logarithm of the determinant of a symmetric positive definite (SPD) matrix. The algorithm is randomized and approximates the traces of a small number of matrix powers of a specially constructed matrix, using the method of Avron and Toledo [1] . From a theoretical perspective, we present additive and relative error bounds for our algorithm. Our additive error bound works for any SPD matrix, whereas our relative error bound works for SPD matrices whose eigenvalues lie in the interval ( θ 1 , 1 ) , with 0 < θ 1 < 1 ; the latter setting was proposed in [16] . From an empirical perspective, we demonstrate that a C++ implementation of our algorithm can approximate the logarithm of the determinant of large matrices very accurately in a matter of seconds. [ABSTRACT FROM AUTHOR]

A new method is proposed for the steady-state optimization of biochemical systems described by Generalized Mass Action (GMA) models. In this method, a bi-level programming with a two-layer nested structure is established. In this bi-level problem, the upper-level objective is to maximize a flux or a metabolite concentration, and the lower-level objective is to minimize the total sum of metabolite concentrations of biochemical systems. The biological significance of the presented bi-level programming problem is to maximize the production rate or concentration of the desired product under a minimal metabolic cost to the biochemical system. To efficiently solve the above NP-hard, non-convex and nonlinear bi-level programming problem, we reformulate it into a single-level optimization problem by using appropriate transformation strategies. The proposed framework is applied to four case studies and has shown the tractability and effectiveness of the method. A comparison of our proposed method and other methods is also given. [ABSTRACT FROM AUTHOR]

We present a general technique for approximating bicriteria minimization problems with positive-valued, polynomially computable objective functions. Given 0 < ϵ ≤ 1 and a polynomial-time α -approximation algorithm for the corresponding weighted sum problem, we show how to obtain a bicriteria ( α ⋅ ( 1 + 2 ϵ ) , α ⋅ ( 1 + 2 ϵ ) ) -approximation algorithm for the budget-constrained problem whose running time is polynomial in the encoding length of the input and linear in 1 ϵ . Moreover, we show that our method can be extended to compute an ( α ⋅ ( 1 + 2 ϵ ) , α ⋅ ( 1 + 2 ϵ ) ) -approximate Pareto curve under the same assumptions. Our technique applies to many minimization problems to which most previous algorithms for computing approximate Pareto curves cannot be applied because the corresponding gap problem is NP -hard to solve. For maximization problems, however, we show that approximation results similar to the ones presented here for minimization problems are impossible to obtain in polynomial time unless P = NP . [ABSTRACT FROM AUTHOR]

In multi-channel wireless networks, a fundamental problem is to find node-disjoint paths minimising global cost or the maximum individual path cost, under the constraint that each path operates on a separate channel to maximise the fault tolerance and robustness against channel instability and malicious attacks. Meanwhile, the quality of service (QoS) requirement (e.g., in terms of end-to-end delay) needs to be satisfied on each path. In this paper, we provide a comprehensive formulation and analysis on this multi-path optimization problem by casting it to the problem k -disjoint path with different colours ( k -DPDC). We further formulate the Restricted MinSum k -DPDC and Restricted MinMax k -DPDC to denote the problems of finding multiple node- and channel-disjoint paths minimising the global cost and the maximum individual path cost under the QoS constraint on the path end-to-end delay. Given the NP-hardness of both problems, we focus on directed acyclic graphs and propose fully polynomial-time approximation algorithms for both problems. [ABSTRACT FROM AUTHOR]

This paper introduces a new algorithm named Elitist Stepped Distribution Algorithm (ESDA), which is inspired from the existing Cross Entropy Method (CEM) through the modification of elite sample based normal distribution used in CEM. Considering the natural behavior of normal distribution, ESDA is proposed to enhance the drawbacks of CEM through improving the efficiency in both exploration and exploitation processes when applying for complex function optimization problems. In ESDA, the elite sample percent defined in CEM is separated into two parts: (1) elite sample percent to calculate the mean value, and (2) elite sample percent to calculate standard deviation of normal distribution to construct an applicable balance between exploration and exploitation ability of the algorithm at a reasonable convergence speed. The elite sample percent parameter for the mean guides the algorithm to focus more on the better solutions and therefore improves the exploitation ability, whereas the elite sample percent parameter for the standard deviation controls the length of standard deviation to handle the exploration process more effectively. Performance of ESDA is investigated using unconstrained benchmark problems and compared with CEM, Simple Genetic Algorithm and Particle Swarm Optimization. The comparisons on unimodal and multi-modal functions confirm the efficiency of the algorithm in both exploration and exploitation process. In addition, the performance of ESDA is tested using constrained engineering problems commonly used in literature by comparing its performance with the other ones statistically. The results on engineering problems also prove that ESDA is perfectly applicable in real-world applications. [ABSTRACT FROM AUTHOR]

An edge-bicolored graph G = ( V , R ∪ B ) is called Red/Blue-split graph if there exists a partition I B and I R of V such that I B and I R are independent sets in ( V , B ) and ( V , R ) , respectively. Red/Blue-split graphs generalize several well studied graph classes including split graphs, bipartite graphs and König–Egerváry graphs. In this paper we consider the algorithmic complexity of various optimization problems like minimum edge (or vertex) deletion and maximum edge (or vertex) induced subgraph related to Red/Blue split graphs. All these problems are NP -hard and thus we look at them from algorithmic paradigms that are meant for coping with NP -hardness. We obtain various hardness as well as algorithmic results for these problems in the realm of approximation algorithms and parameterized complexity. The main tool we use to obtain all our results is polynomial time transformations between appropriate problems. On the way, we also resolve some problems related to inapproximability about certain optimization problems mentioned by Korach et al. (2006) [17] . [ABSTRACT FROM AUTHOR]

In this paper we consider the 2-dominating set problem (2MDS). We look for a smallest subset of vertices D ⊆ V with the property that every vertex in V ∖ D is adjacent to at least 2 vertices of D . We are interested in the distributed complexity of this problem in the local model, where the nodes have no identifiers but there is a port ordering available. We propose a distributed local (constant time) algorithm yielding a 6-approximation in the class of planar graphs. Earlier result shows that in this case, for any ϵ > 0 , there is no deterministic distributed local/constant-round algorithm providing a ( 5 − ϵ ) -approximation of the 2MDS. [ABSTRACT FROM AUTHOR]

Given a set P of n points in the plane, we consider the problem of covering P with a minimum number of unit disks. This problem is known to be NP-hard. We present a simple 4-approximation algorithm for this problem which runs in O ( n log ⁡ n ) -time. We also show how to extend this algorithm to other metrics, and to three dimensions. [ABSTRACT FROM AUTHOR]

This paper explores the use of data-driven approximation algorithms, often called surrogate modeling, in the early-stage design of structures. The use of surrogate models to rapidly evaluate design performance can lead to a more in-depth exploration of a design space and reduce computational time of optimization algorithms. While this approach has been widely developed and used in related disciplines such as aerospace engineering, there are few examples of its application in civil engineering. This paper focuses on the general use of surrogate modeling in the design of civil structures and examines six model types that span a wide range of characteristics. Original contributions include novel metrics and visualization techniques for understanding model error and a new robustness framework that accounts for variability in model comparison. These concepts are applied to a multi-objective case study of an airport terminal design that considers both structural material volume and operational energy consumption. [ABSTRACT FROM AUTHOR]

In the incremental version of the k -median problem, we find a sequence of facility sets F 1 ⊆ F 2 ⊆ ⋯ ⊆ F n , where each F k contains at most k facilities. This sequence is said to be δ - competitive if the cost of each F k is at most δ times the optimum cost of k facilities. The best deterministic (randomized) algorithm available for the metric space has a competitive ratio of 8 ( 7.656 ). The best one for the one-dimensional problem finds a 5.828 -competitive sequence. We give a 7.076 -competitive solution for the high-dimensional Euclidean space. [ABSTRACT FROM AUTHOR]

We consider the dynamic map labeling problem: given a set of rectangular labels on the map, the goal is to appropriately select visible ranges for all the labels such that no two consistent labels overlap at every scale and the sum of total visible ranges is maximized. This is also called the active range optimization (ARO) problem defined by Been et al. (2006) [2] . We propose approximation algorithms for several variants of this problem. For the simple ARO problem , we provide a 3 c log ⁡ n -approximation algorithm for unit-width rectangular labels if there is a c -approximation algorithm for the unit-width label placement problem in the plane; and a randomized polynomial-time O ( log ⁡ n log ⁡ log ⁡ n ) -approximation algorithm for arbitrary rectangular labels. For the general ARO problem , we prove that it remains NP-complete even for congruent square labels with equal selectable scale range. Moreover, we contribute 12-approximation algorithms for both arbitrary square labels and unit-width rectangular labels, and a 6-approximation algorithm for congruent square labels, and show that the bounds are tight. [ABSTRACT FROM AUTHOR]

The minimum vertex cover problem is a basic combinatorial optimization problem. Given an undirected graph the objective is to determine a subset of the vertices which covers all edges such that the number of the vertices in the subset is minimized. In the paper, based on Dijkstra algorithm, an approximation algorithm is obtained for the minimum vertex cover problem. In the process of getting a vertex cover, the maximum value of shortest paths is considered as a standard, and some criteria are defined. The time complex of the Algorithm is O ( n 3) where n is the number of vertices in a graph. In the end, an example is given to illustrate the process and the validity of the Algorithm. [ABSTRACT FROM AUTHOR]

Being the unbalanced version of the famous Min s – t Cut problem, the Min k -Size s – t Cut problem asks to find a k -size s – t cut with the minimum capacity, where a k -size s – t cut means an s – t cut with its s -side having size at most k . This problem is fundamental and has extensive applications, especially in community identification in social and information networks. It is known that the Min k -Size s – t Cut problem is NP-hard and can be approximated within O ( log ⁡ n ) , where n is the number of vertices in the input graph. In this paper, we give a new approximation algorithm for the Min k -Size s – t Cut problem based on the parametric flow technique. The algorithm is very simple and has only three lines to state. Its approximation ratio is k + 1 k + 1 − k ⁎ , where k ⁎ is the size of the s -side of an optimal solution. [ABSTRACT FROM AUTHOR]

For two positive integers m , k and a connected graph G = ( V , E ) with a nonnegative vertex weight function w , the balanced m -connected k -partition problem, denoted as BC m P k , is to find a partition of V into k disjoint nonempty vertex subsets ( V 1 , V 2 , … , V k ) such that each G [ V i ] (the subgraph of G induced by V i ) is m -connected, and min 1 ≤ i ≤ k ⁡ { w ( V i ) } is maximized. The optimal value of BC m P k on graph G is denoted as β m ⁎ ( G , k ) , that is, β m ⁎ ( G , k ) = max ⁡ min 1 ≤ i ≤ k ⁡ { w ( V i ) } , where the maximum is taken over all m -connected k -partition of G . In this paper, we study the BC 2 P k problem on interval graphs, and obtain the following results. (1) For k = 2 , a 4/3-approximation algorithm is given for BC 2 P 2 on 4-connected interval graphs. (2) In the case that there exists a vertex v with weight at least W / k , where W is the total weight of the graph, we prove that the BC 2 P k problem on a 2 k -connected interval graph G can be reduced to the BC 2 P k − 1 problem on the ( 2 k − 1 ) -connected interval graph G − v . In the case that every vertex has weight at most W / k , we prove a lower bound β 2 ⁎ ( G , k ) ≥ W / ( 2 k − 1 ) for 2 k -connected interval graph G . (3) Assuming that weight w is integral, a pseudo-polynomial time algorithm is obtained. Combining this pseudo-polynomial time algorithm with the above lower bound, a fully polynomial time approximation scheme (FPTAS) is obtained for the BC 2 P k problem on 2 k -connected interval graphs. [ABSTRACT FROM AUTHOR]

A new randomized algorithm is suggested, for extracting static-output-stabilizing-feedbacks, with approximately minimal-norm, for LTI systems. The algorithm has two similar stages, where in the first one the feasibility problem is solved, and in the second one the optimization problem is solved. The formulation is unified for the feasibility and for the optimization problems, as well as for continuous-time or discrete-time systems. The method is demonstrated by applying it to the hard (conjectured to be NP-hard) problem of the minimal-gain static-output-stabilizing-feedback, and to the hard (conjectured to be NP-hard) problem of regional pole-placement via static-output-feedback in non-convex or unconnected regions. A proof of convergence (in probability) that captures the two rounds of the algorithm is given, and complexity analysis is provided, under some mild assumptions. [ABSTRACT FROM AUTHOR]

This paper describes a fast optimization algorithm for Model Predictive Control (MPC) with soft constraints. The method relies on the Kreisselmeier–Steinhauser function to provide a smooth approximation of the penalty function for a soft constraint. This is analogous to the approximation of a hard constraint by a smooth logarithmic barrier function. By introducing this approximation directly into the objective of an interior point optimization, there is no need for additional slack variables to capture constraint violation. Simulation results show significant speed-up compared to using slack variables. [ABSTRACT FROM AUTHOR]

In this paper a class of combinatorial optimization problems with uncertain costs is discussed. The uncertainty is modeled by specifying a discrete scenario set containing K distinct cost scenarios. The Ordered Weighted Averaging (OWA for short) aggregation operator is applied to choose a solution. Some well known criteria used in decision making under uncertainty such as the maximum, minimum, average, Hurwicz and median are special cases of OWA. Furthermore, by using OWA, the traditional robust (min–max) approach to combinatorial optimization problems with uncertain costs can be generalized. The computational complexity and approximability of the problem of minimizing OWA for the considered class of problems are investigated and some new positive and negative results in this area are provided. These results remain valid for many basic problems, such as network or resource allocation problems. [ABSTRACT FROM AUTHOR]

The fully polynomial-time approximation scheme (FPTAS) is a class of approximation algorithms for optimisation problems that is able to deliver an approximate solution within any chosen ratio in polynomial time. By generalising Bird and de Moor's Thinning Theorem to a property between three orderings, we come up with a datatype-generic strategy for constructing fold-based FPTASs. Greedy, thinning, and approximation algorithms can thus be seen as a series of generalisations. Components needed in constructing an FPTAS are often natural extensions of those in the thinning algorithm. Design of complex FPTASs is thus made easier, and some of the resulting algorithms turn out to be simpler than those in previous works. [ABSTRACT FROM AUTHOR]

Flux balance analysis (FBA) is a linear programming-based framework widely used to predict the behavior, in terms of the resulting flux distribution, of cellular organisms in different media. FBA models are constructed using only stoichiometric information, and for this reason they sometimes fail in predicting fluxes precisely. In this work, we formally define the concept of hybrid FBA/kinetic models, in which kinetic information of key processes is used to tighten the search space of standalone FBA formulations, thereby enhancing their predictive capabilities. This approach leads to non-linear non-convex models that may exhibit multiple local optima. To solve them to global optimality, we use a customized outer-approximation algorithm that exploits the structure of the kinetic equations. Numerical results show that our method enhances the quality of standalone FBA models, providing more accurate predictions. [ABSTRACT FROM AUTHOR]

In this paper, we propose a novel algorithm for the rigorous design of distillation columns that integrates a process simulator in a generalized disjunctive programming formulation. The optimal distillation column, or column sequence, is obtained by selecting, for each column section, among a set of column sections with different number of theoretical trays. The selection of thermodynamic models, properties estimation, etc. is all in the simulation environment. All the numerical issues related to the convergence of distillation columns (or column sections) are also maintained in the simulation environment. The model is formulated as a Generalized Disjunctive Programming (GDP) problem and solved using the logic based outer approximation algorithm without MINLP reformulation. Some examples involving from a single column to thermally coupled sequence or extractive distillation shows the performance of the new algorithm. [ABSTRACT FROM AUTHOR]

Abstract: We study vertex selection in the presence of multiple graphs associated with a vertex set V representing an online community. First, we formulate a collection of Markov chains on the graph ensemble and describe the characteristics of the associated mean hitting times on V. Then, we design a branch and bound optimisation technique for computing the subset of vertices A that exhibits the smallest hitting time cost across the multi-graph, given a constraint on the volume of A. The complexity of the branch and bound technique limits its application to medium-size graphs. Thus, we formulate a greedy optimisation method for computing a close approximation to the optimal subset at lower complexity, which can be implemented in a decentralised way, for further complexity reduction. We prove that the objective function under consideration is supermodular and monotonic, which guarantees near-optimal solutions for the greedy method. This is verified in our numerical experiments that compare its performance to that of the branch and bound technique, on smaller size graphs. The experiments also examine the hitting-time trade-off across the multi-graph that our optimisation exhibits, governed by the sampling cost factors λ j associated with each graph layer G j . Relative to conventional community graph centrality methods for vertex selection, we demonstrate a substantially lower sampling (network) cost and higher data dissemination rate, on actual Facebook and Internet topology data. The generality of our framework allows for its application to information retrieval, from a collection of items represented by a multi-graph. Here, we demonstrate higher semantic consistency over state-of-the-art single-graph methods, on the popular DBLP data set. [Copyright &y& Elsevier]

The Quantum Circuit Compilation Problem (QCCP) is challenging to the Artificial Intelligence community. It was already tackled with temporal planning, constraint programming, greedy heuristics and other techniques. In this paper, QCCP is formulated as a scheduling problem and solved by a genetic algorithm. We focus on QCCP for Quantum Approximation Optimization Algorithms (QAOA) applied to the MaxCut problem and consider Noisy Intermediate Scale Quantum (NISQ) hardware architectures. Based on the fact that these algorithms apply a set of basic quantum operations repeatedly over a number of rounds, we propose a genetic algorithm approach, termed Decomposition Based Genetic Algorithm (DBGA), that in each round extends the partial solutions obtained for the previous ones. DBGA is compared to the state of the art across a set of conventional instances. The results of the experimental study provided interesting insight in the problem structure and showed that DBGA is quite competitive with the state of the art. In particular, DBGA outperformed the best current method on the largest instances and provided new best solutions to most of them. [ABSTRACT FROM AUTHOR]

Abstract: Parameterised approximation is a relatively new but growing field of interest. It merges two ways of dealing with NP-hard optimisation problems, namely polynomial approximation and exact parameterised (exponential-time) algorithms. We exemplify this idea by designing and analysing parameterised approximation algorithms for minimum vertex cover. More specifically, we provide a simple algorithm that works on any approximation ratio of the form , , and has complexity that outperforms previously published algorithms based on sophisticated exact parameterised algorithms. In particular, for (factor- approximation) our algorithm runs in time , where parameter , and is the size of a minimum vertex cover. Additionally, we present an improved polynomial-time approximation algorithm for graphs of average degree at most four and a limited number of vertices with degree less than two. [Copyright &y& Elsevier]

Abstract: We study the problem of leasing facilities over time, following the general infrastructure leasing problem framework introduced by Anthony and Gupta (2007). If there are different lease types, Anthony and Gupta give an -approximation algorithm for the problem. We are able to improve this to a 3-approximation algorithm by using a variant of the primal–dual facility location algorithm of Jain and Vazirani (2001). We also consider the online version of the facility leasing problem, in which the clients to be served arrive over time and are not known in advance. This problem generalizes both the online facility location problem (introduced by Meyerson, 2001) and the parking permit problem (also introduced by Meyerson, 2005). We give a deterministic algorithm for the problem that is -competitive. No previous result was known for this problem. To achieve our result, we modify an -competitive algorithm of Fotakis (2007) for the online facility location problem. We also reanalyze his algorithm via the dual-fitting technique to prove that it achieves the competitive ratio. [Copyright &y& Elsevier]

Abstract: Landscape constraints inevitably cause the irregularity of the shape or boundary of a wind farm, which was not fully considered in previous literature. In this paper, a single-boundary constraint model and a novel multi-boundary constraint model incorporated with ray intersection method are developed to quantify the irregular boundary constraint for wind farm micro-siting optimization. In order to obtain high-fidelity wind farm shape information, an edge detection algorithm is employed to extract wind farm contour data from digital maps, and an optimal polygonal approximation algorithm is applied to compress the contour data so as to make the computation of boundary constraints less time-consuming. Simulations of four commercial wind farms comprehensively demonstrate the effectiveness of the proposed boundary constraint models and the significance of irregular-shape wind farm micro-siting optimization. [Copyright &y& Elsevier]

Abstract: This paper revisits the problem of dictionary learning on several points although we still consider an alternating optimization scheme. Our first contribution consists in providing a simple proof of convergence for this numerical scheme for a large class of constraints and regularizers on the dictionary atoms. We also investigate the use of a well-known optimization method named alternating direction method of multipliers for solving each of the alternate step of the dictionary learning problem. We show that such an algorithm yields to several benefits. Indeed, it can be more efficient than other competing algorithms such as Iterative Shrinkage Thresholding approach and besides, it allows one to easily deal with mixed constraints or regularizers over the dictionary atoms or approximation coefficients. For instance, we have induced joint sparsity, positivity and smoothness on the dictionary atoms by means of some total variation and sparsity-inducing regularizers. Our experimental results prove that using these mixed constraints helps in achieving better learned dictionary elements especially when learning from noisy signals. [Copyright &y& Elsevier]