Optimal power flow (OPF) is the central optimization problem in electric power grids. Although solved routinely in the course of power grid operations, it is known to be strongly NP-hard in general, and weakly NP-hard...
详细信息
Optimal power flow (OPF) is the central optimization problem in electric power grids. Although solved routinely in the course of power grid operations, it is known to be strongly NP-hard in general, and weakly NP-hard over tree networks. In this paper, we formulate the optimal power flow problem over tree networks as an inference problem over a tree-structured graphical model where the nodal variables are low-dimensional vectors. We adapt the standard dynamic programming algorithm for inference over a tree-structured graphical model to the OPF problem. Combining this with an interval discretization of the nodal variables, we develop an approximation algorithm for the OPF problem. Further, we use techniques from constraint programming (CP) to perform interval computations and adaptive bound propagation to obtain practically efficient algorithms. Compared to previous algorithms that solve OPF with optimality guarantees using convex relaxations, our approach is able to work for arbitrary tree-structured distribution networks and handle mixed-integer optimization problems. Further, it can be implemented in a distributed message-passing fashion that is scalable and is suitable for "smart grid" applications like control of distributed energy resources. Numerical evaluations on several benchmark networks show that practical OPF problems can be solved effectively using this approach.
This paper deals with the no-wait flow shop scheduling problem with due date constraints. In the no wait flow shop problem, waiting time is not allowed between successive operations of jobs. Moreover, the jobs should ...
详细信息
This paper deals with the no-wait flow shop scheduling problem with due date constraints. In the no wait flow shop problem, waiting time is not allowed between successive operations of jobs. Moreover, the jobs should be completed before their respective due dates;due date constraints are dealt with as hard constraints. The considered performance criterion is makespan. The problem is strongly NP-hard. This paper develops a number of distinct mathematical models for the problem based on different decision variables. Namely, a mixed integer programming model, two quadratic mixed integer programming models, and two constraint programming models are developed. Moreover, a novel graph representation is developed for the problem. This new modeling technique facilitates the investigation of some of the important characteristics of the problem;this results in a number of propositions to rule out a large number of infeasible solutions from the set of all possible permutations. Afterward, the new graph representation and the resulting propositions are incorporated into a new exact algorithm to solve the problem to optimality. To investigate the performance of the mathematical models and to compare them with the developed exact algorithm, a number of test problems are solved and the results are reported. Computational results demonstrate that the developed algorithm is significantly faster than the mathematical models. (C) 2016 Elsevier Ltd. All rights reserved.
This paper deals with the set inversion problem X = f(-1) (Y) in the case where the function f : R-n -> R-m and the set Y are both uncertain. The uncertainty is treated under the form of intervals. More precisely, ...
详细信息
This paper deals with the set inversion problem X = f(-1) (Y) in the case where the function f : R-n -> R-m and the set Y are both uncertain. The uncertainty is treated under the form of intervals. More precisely, for all x, f(x) is inside the box [f](x) and the uncertain set Y. is bracketed between an inner set Y-subset of and an outer set Y-superset of. The introduction of new tools such as thick intervals and thick boxes will allow us to propose an efficient algorithm that handles the uncertainty of sets in an elegant and efficient manner. Some elementary test cases that cannot be handled easily and properly by existing methods show the efficiency of the approach. (C) 2017 Elsevier B.V. All rights reserved.
Since their introduction, local search algorithms have consistently represented the state of the art in solution techniques for the classical job-shop scheduling problem. This dominance is despite the availability of ...
详细信息
Since their introduction, local search algorithms have consistently represented the state of the art in solution techniques for the classical job-shop scheduling problem. This dominance is despite the availability of powerful search and inference techniques for scheduling problems developed by the constraint programming community. In this paper, we introduce a simple hybrid algorithm for job-shop scheduling that leverages both the fast, broad search capabilities of modern tabu search algorithms and the scheduling-specific inference capabilities of constraint programming. The hybrid algorithm significantly improves the performance of a state-of-the-art tabu search algorithm for the job-shop problem and represents the first instance in which a constraint programming algorithm obtains performance competitive with the best local search algorithms. Furthermore, the variability in solution quality obtained by the hybrid is significantly lower than that of pure local search algorithms. Beyond performance demonstration, we perform a series of experiments that provide insights into the roles of the two component algorithms in the overall performance of the hybrid.
Soft constraint Logic programming is a natural and flexible declarative programming formalism, which allows to model and solve real-life problems involving constraints of different types. In this paper, after providin...
详细信息
constraint programming is used to model and solve complex combinatorial problems. The modeling task requires some expertise in constraint programming. This requirement is a bottleneck to the broader uptake of constrai...
详细信息
constraint programming is used to model and solve complex combinatorial problems. The modeling task requires some expertise in constraint programming. This requirement is a bottleneck to the broader uptake of constraint technology. Several approaches have been proposed to assist the non-expert user in the modeling task. This paper presents the basic architecture for acquiring constraint networks from examples classified by the user. The theoretical questions raised by constraint acquisition are stated and their complexity is given. We then propose CONACQ, a system that uses a concise representation of the learner's version space into a clausal formula. Based on this logical representation, our architecture uses strategies for eliciting constraint networks in both the passive acquisition context, where the learner is only provided a pool of examples, and the active acquisition context, where the learner is allowed to ask membership queries to the user. The computational properties of our strategies are analyzed and their practical effectiveness is experimentally evaluated. (C) 2015 Elsevier By. All rights reserved.
Algorithm selection (AS), selecting the algorithm best suited for a particular problem instance, is acknowledged to be a key issue to make the best out of algorithm portfolios. This paper presents a collaborative filt...
详细信息
Algorithm selection (AS), selecting the algorithm best suited for a particular problem instance, is acknowledged to be a key issue to make the best out of algorithm portfolios. This paper presents a collaborative filtering approach to AS. Collaborative filtering, popularized by the Netflix challenge, aims to recommend the items that a user will most probably like, based on the previous items she liked, and the items that have been liked by other users. As first noted by Stern et al. [47], algorithm selection can be formalized as a collaborative filtering problem, by considering that a problem instance "likes better" the algorithms that achieve better performance on this particular instance. Two merits of collaborative filtering (CF) compared to the mainstream algorithm selection (AS) approaches are the following. Firstly, mainstream AS requires extensive and computationally expensive experiments to learn a performance model, with all algorithms launched on all problem instances, whereas CF can exploit a sparse matrix, with a few algorithms launched on each problem instance. Secondly, AS learns a performance model as a function of the initial instance representation, whereas CF builds latent factors to describe algorithms and instances, and uses the associated latent metrics to recommend algorithms for a specific problem instance. A main contribution of the proposed algorithm recommender ALORS system is to handle the cold start problem emitting recommendations for a new problem instance - through the non-linear modeling of the latent factors based on the initial instance representation, extending the linear approach proposed by Stern et al. [47]. The merits and generality of ALORS are empirically demonstrated on the ASLib [6] and OpenML [53] benchmarks. (C) 2016 Elsevier B.V. All rights reserved.
One of the biggest challenges in the design of real-world decision support systems is coming up with a good combinatorial optimization model. Often enough, accurate predictive models (e.g. simulators) can be devised, ...
详细信息
One of the biggest challenges in the design of real-world decision support systems is coming up with a good combinatorial optimization model. Often enough, accurate predictive models (e.g. simulators) can be devised, but they are too complex or too slow to be employed in combinatorial optimization. In this paper, we propose a methodology called Empirical Model Learning (EML) that relies on Machine Learning for obtaining components of a prescriptive model, using data either extracted from a predictive model or harvested from a real system. In a way, EML can be considered as a technique to merge predictive and prescriptive analytics. All models introduce some form of approximation. Citing G.E.P. Box [1] "Essentially, all models are wrong, but some of them are useful". In EML, models are useful if they provide adequate accuracy, and if they can be effectively exploited by solvers for finding high-quality solutions. We show how to ground EML on a case study of thermal-aware workload dispatching. We use two learning methods, namely Artificial Neural Networks and Decision Trees and we show how to encapsulate the learned model in a number of optimization techniques, namely Local Search, constraint programming, Mixed Integer Non-Linear programming and SAT Modulo Theories. We demonstrate the effectiveness of the EML approach by comparing our results with those obtained using expert-designed models. (C) 2016 Elsevier B.V. All rights reserved.
Bike sharing systems have been installed in many cities around the world and are increasing in popularity. A major operational cost driver in these systems is rebalancing the bikes over time such that the appropriate ...
详细信息
Bike sharing systems have been installed in many cities around the world and are increasing in popularity. A major operational cost driver in these systems is rebalancing the bikes over time such that the appropriate number of bikes and open docks are available to users. We combine two aspects that have previously been handled separately in the literature: determining service level requirements at each bike sharing station, and designing (near-)optimal vehicle routes to rebalance the inventory. Since finding provably optimal solutions is practically intractable, we propose a new cluster-first route-second heuristic, in which a polynomial-size Clustering Problem simultaneously considers the service level feasibility and approximate routing costs. Extensive computational results on real-world data from Hubway (Boston, MA) and Capital Bikeshare (Washington, DC) are provided, which show that our heuristic outperforms a pure mixed-integer programming formulation and a constraint programming approach. (C) 2016 Elsevier B.V. All rights reserved.
We present a method, based on formulation symmetry, for generating Mixed-Integer Linear programming (MILP) relaxations with fewer variables than the original symmetric MILP. Our technique also extends to convex MINLP,...
详细信息
We present a method, based on formulation symmetry, for generating Mixed-Integer Linear programming (MILP) relaxations with fewer variables than the original symmetric MILP. Our technique also extends to convex MINLP, and some nonconvex MINLP with a special structure. We showcase the effectiveness of our relaxation when embedded in a decomposition method applied to two important applications (multi-activity shift scheduling and multiple knapsack problem), showing that it can improve CPU times by several orders of magnitude compared to pure MIP or CP approaches. (C) 2017 Elsevier B.V. All rights reserved.
暂无评论