This study proposes a novel optimal phasor measurement unit (PMU) placement method for dynamic vulnerability assessment with minimum number of PMUs. PMU measurements should reflect the change of ...power system status as earlier as possible when a contingency occurs. Therefore, those buses which are sensitive to the change of power system status have to be equipped with PMUs to monitor the fragile areas of power systems. First, a large power system is partitioned into several coherent clusters. Next, a probabilistic vulnerability index defined as the objective function and a binary quadratic programming model are proposed for this purpose. Finally, the proposed method is tested on IEEE 9-, 39-, and 145-bus systems. Results show that this method results in a PMU configuration with minimum number of devices and high vulnerability index. Such a PMU placement is able to estimate the vulnerability of power systems.
•We extend conventional single-objective unconstrained binary quadratic programming (UBQP) to the multiobjective case.•We define a flexible model to generate multiobjective UBQP problem instances ...with complementary features.•We propose a hybrid metaheuristic to identify an approximation of the Pareto set.•We experiment the performance of our algorithm on large-size multiobjective UBQP problem instances with two and three objectives.
The conventional unconstrained binary quadratic programming (UBQP) problem is known to be a unified modeling and solution framework for many combinatorial optimization problems. This paper extends the single-objective UBQP to the multiobjective case (mUBQP) where multiple objectives are to be optimized simultaneously. We propose a hybrid metaheuristic which combines an elitist evolutionary multiobjective optimization algorithm and a state-of-the-art single-objective tabu search procedure by using an achievement scalarizing function. Finally, we define a formal model to generate mUBQP instances and validate the performance of the proposed approach in obtaining competitive results on large-size mUBQP instances with two and three objectives.
We present and compare novel binary programs for linear ordering problems that involve the notion of asymmetric betweenness and expose relations to the quadratic linear ordering problem and its ...linearization. While two of the binary programs prove particularly superior from a computational point of view when many or all betweenness relations shall be modeled, the others arise as natural formulations that resemble important theoretical correspondences and provide a compact alternative for sparse problem instances. A reasoning for the strengths and weaknesses of the different formulations is derived by means of polyhedral considerations with respect to their continuous relaxations.
•Compact and effective mathematical programming formulations for asymmetric betweenness problems that straightforwardly generalize classical linear ordering problems and that address both dense as well as sparse contexts.•Polyhedral results that help to explain the strength of the proposed formulations and reveal important relations to the quadratic linear ordering problem.•Structural insights when regarding the asymmetric betweenness problem as a binary quadratic (linear ordering) program from a linearization perspective.•A computational study that compares the relative performance of the presented formulations when passed to a professional solver.
The goal of this paper is to investigate the curves intersected by a vertical plane with the surfaces based on certain NCP functions. The convexity and differentiability of these curves are studied ...as well. In most cases, the inflection points of the curves cannot be expressed exactly. Therefore, we instead estimate the interval where the curves are convex under this situation. Then, with the help of differentiability and convexity, we obtain the local minimum or maximum of the curves accordingly. The study of these curves is very useful to binary quadratic programming.
Celotno besedilo
Dostopno za:
DOBA, IZUM, KILJ, NUK, PILJ, PNG, SAZU, UILJ, UKNU, UL, UM, UPUK
This paper presents a digital annealing engine capable of high-speed solving the Binary Quadratic Programming Problem (BQP) with equality and inequality constraints. While many Quadratic ...Unconstrained Binary Optimization (QUBO) solvers have been developed for combinatorial optimization problems, they are specialized for "unconstrained" BQP and struggle to solve "constrained" BQP at high speed. To address this issue, we developed a digital annealing engine on GPUs that leverages constraints to narrow the search space and directly evaluates inequality violations during Markov Chain Monte Carlo based searches. We evaluated the performance of the Digital Annealer (DA) system with the developed engine on benchmark problems with one-hot (a type of equality constraint) and inequality constraints. The results showed that the developed DA system achieved superior solving performance compared to the previous generation of DA. It also showed comparable performance to state-of-the-art dedicated solvers. Our results suggest that this digital annealing engine is a promising solution for high-speed solving constrained BQP.
This paper introduces to use semi-supervised learning for large scale image co segmentation. Different from traditional unsupervised cosegmentation that does not use any segmentation ground truth, ...semi-supervised cosegmentation exploits the similarity from both the very limited training image foregrounds, as well as the common object shared between the large number of unsegmented images. This would be a much practical way to effectively co segment a large number of related images simultaneously, where previous unsupervised co segmentation work poorly due to the large variances in appearance between different images and the lack of segmentation ground truth for guidance in co segmentation. For semi-supervised co segmentation in large scale, we propose an effective method by minimizing an energy function, which consists of the inter-image distance, the intra-image distance and the balance term. We also propose an iterative updating algorithm to efficiently solve this energy function, which decomposes the original energy minimization problem into sub-problems, and updates each image alternatively to reduce the number of variables in each sub-problem for computation efficiency. Experiment results on iCoseg and Pascal VOC datasets show that the proposed co segmentation method can effectively co segment hundreds of images in less than one minute. And our semi-supervised co segmentation is able to outperform both unsupervised co segmentation as well as fully supervised single image segmentation, especially when the training data is limited.
The global optimization of binary quadratic programming (BQP) has very important theory and wide application in various fields. Since BQP is a classic NP-hard problem, traditional algorithms will be ...very time-consuming when the dimension is very large. The neural network based algorithms have significant advantages in solving large scale optimization problems. However, directly applying neural network based algorithm cannot guarantee finding the global optimal solution of BQP. In this paper, we propose a neural network based algorithm for BQP by analyzing and utilizing geometric characteristics of the objective function isosurface and combining the advantages and properties of neural network as well as branch-and-bound method. Furthermore, the neural network algorithm is implemented with field-programmable gate array (FPGA) to take advantage of the parallel structure. System Generator which can be used to convert the design into HDL code automatically is adopted so that the calculation of upper and lower bounds can be deployed to FPGA. The numerical simulation illustrates the effectiveness and efficiency of the algorithm. Meanwhile, simulation results show the feasibility of applying the proposed algorithm to FPGA hardware.
A linearization technique for binary quadratic programs (BQPs) that comprise linear constraints is presented. The technique, called “inductive linearization”, extends concepts for BQPs with ...particular equation constraints, that have been referred to as “compact linearization” before, to the general case. Quadratic terms may occur in the objective function, in the set of constraints, or in both. For several relevant applications, the linear programming relaxations obtained from applying the technique are proven to be at least as strong as the one obtained with a well-known classical linearization. It is also shown how to obtain an inductive linearization automatically. This might be used, e.g., by general-purpose mixed-integer programming solvers.
The purpose of this paper is to provide strong reformulations for binary quadratic problems. We propose a first methodological analysis on a family of reformulations combining Dantzig–Wolfe and ...Quadratic Convex optimization principles. We show that a few reformulations of our family yield continuous relaxations that are strong in terms of dual bounds and computationally efficient to optimize. As a representative case study, we apply them to a cardinality constrained quadratic knapsack problem, providing extensive experimental insights. We report and analyze in depth a particular reformulation providing continuous relaxations whose solutions turn out to be integer optima in all our tests.
•We investigate two equity-concerned dispersion problems: max-minsum and min-diffsum.•We present ILP formulations and we discuss their strengthening.•We propose construction heuristics and a local ...search metaheuristic.•We investigate the key features of these algorithms.•We test our algorithms on publicly available benchmark instances up to 500 elements.
Given a set N, a pairwise distance function d and an integer number m, the Dispersion Problems (DPs) require to extract from N a subset M of cardinality m, so as to optimize a suitable function of the distances between the elements in M. Different functions give rise to a whole family of combinatorial optimization problems. In particular, the max-sum DP and the max-min DP have received strong attention in the literature. Other problems (e.g., the max-minsum DP and the min-diffsum DP) have been recently proposed with the aim to model the optimization of equity requirements, as opposed to that of more classical efficiency requirements. Building on the main ideas which underly some state-of-the-art methods for the max-sum DP and the max-min DP, this work proposes some constructive procedures and a Tabu Search algorithm for the new problems. In particular, we investigate the extension to the new context of key features such as initialization, tenure management and diversification mechanisms. The computational experiments show that the algorithms applying these ideas perform effectively on the publicly available benchmarks, but also that there are some interesting differences with respect to the DPs more studied in the literature. As a result of this investigation, we also provide optimal results and bounds as a useful reference for further studies.
PDF
