Clustering is probably the most extensively studied problem in unsupervised learning. Traditional clustering algorithms assign objects to clusters exclusively based on features of the objects. Constrained clustering i...
详细信息
ISBN:
(纸本)9781538672204
Clustering is probably the most extensively studied problem in unsupervised learning. Traditional clustering algorithms assign objects to clusters exclusively based on features of the objects. Constrained clustering is a generalization of traditional clustering where additional information about a dataset is given in the form of constraints. It has been shown that the clustering accuracy can be improved substantially by accounting for these constraints. We consider the constrained clustering problem where additional information is given in the form of must-link and cannot-link constraints for some pairs of objects. Various algorithms have been developed for this specific clustering problem. We propose a binary linear programming-based k-means approach that can consider must-link and cannot-link constraints. In a computational experiment, we compare the proposed algorithm to the DILSCC algorithm, which represents the state-of-the-art. Our results on 75 problem instances indicate that the proposed algorithm delivers better clusterings than the DILSCC algorithm in much shorter running time.
Nowadays, grid-connected photovoltaic (GCPV) system is known as a top leading technology among all resources. However, it still suffers from drastic investment costs. Detailed economic studies should be conducted in t...
详细信息
Nowadays, grid-connected photovoltaic (GCPV) system is known as a top leading technology among all resources. However, it still suffers from drastic investment costs. Detailed economic studies should be conducted in this regard to make this technology as gainful as possible. A practical approach is the "optimum economic design", trying to find an electrically possible layout, i.e. number of series modules and parallel strings as well as the inverter number with the highest profit. This problem is inherently an quadratic integer programming owing to the multiplication of two integer variables in its objective function and some technical constraints. This nonlinear problem should be solved by exhaustive search methods, including comparative and evolutionary algorithms (EAs) such as particle swarm optimization (PSO) and genetic algorithm (GA). In this paper, a new formulation based on the definition of new binary variables has been proposed to convert this problem to the binary linear programming (BLP). The provided method finds the global optimum solution in a scale of seconds while EAs have to be run numerous times in a scale of hours to reach a sufficiently good answer. Moreover, although current methodologies are rarely covered GCPV systems with multiple inverter types, this formulation can be easily developed for systems with several inverter types. The simulations of a 1.1 MW power plant system endorse that the output design provided by the proposed method assures 95,000 $ (1.94%) higher profit compared with those presented by GA. The sensitivity analysis, provided for the prototype system by the efficient new algorithm, also unveils it is economically viable for even 52% of the current feed-in tariff, 40% energy generation lower than the estimated value and 1.1 $/W price rise for the initial investment.
This paper proposes a new hybrid heuristic (SomAla) for the capacitated p-median problem (CPMP) which combines a self-organising map (SOM), integer linearprogramming, an alternating location-allocation algorithm (ALA...
详细信息
ISBN:
(纸本)9783937436654
This paper proposes a new hybrid heuristic (SomAla) for the capacitated p-median problem (CPMP) which combines a self-organising map (SOM), integer linearprogramming, an alternating location-allocation algorithm (ALA) and a partial neighbourhood optimisation. To improve the performance of the algorithm, the structure of the CPMP is exploited for several size-reduction methods and also for variable-fixing techniques. The capability of this algorithm to find good solutions in reasonable times for large problem instances has been tested on several benchmark instances.
The k-means algorithm is one of the most popular clustering algorithms in the machine learning community. Its simplicity and scalability make it the primary choice for many clustering applications. We introduce here a...
详细信息
ISBN:
(纸本)9781728138046
The k-means algorithm is one of the most popular clustering algorithms in the machine learning community. Its simplicity and scalability make it the primary choice for many clustering applications. We introduce here a variant of the k-means algorithm that can account for complex side constraints. The key idea is to use binary linear programming for assigning objects to clusters. Unlike existing extensions of the k-means algorithm that are designed for accommodating specific types of constraints, our approach can be applied to a wide range of constrained clustering problems with minor modifications. We demonstrate the effectiveness and efficiency of the proposed approach by comparing it to a state-of-the-art algorithm on a test set that comprises 18 instances of the capacitated centered clustering problem. The proposed approach performed particularly well on large-sized instances with more than 100 clusters. It even found new best-known solutions for the four largest instances in the test set.
Direct marketing has become a fundamental advertising method in many industries. In direct marketing, companies target specific customers with personalized product offers. By optimally assigning customers to direct ma...
详细信息
ISBN:
(纸本)9781728138046
Direct marketing has become a fundamental advertising method in many industries. In direct marketing, companies target specific customers with personalized product offers. By optimally assigning customers to direct marketing activities, the effectiveness of direct marketing campaigns can be greatly increased. In this paper, we study a real-world customer assignment problem of a leading telecommunications provider in Switzerland. The planning problem contains many business and customer-specific constraints that have not yet been covered in the literature. We propose a binary linear programming formulation that solves instances involving up to one million customers and over 100 direct marketing activities to optimality in short running time. The novel formulation delivers substantially better solutions in terms of expected profit than the current practice at the company.
The cost of energy consumed in the course of pumping water from its sources constitutes a considerable share of the total operating costs borne by a water company. In order to optimize the operation of a water pumping...
详细信息
ISBN:
(纸本)9783319644653;9783319644646
The cost of energy consumed in the course of pumping water from its sources constitutes a considerable share of the total operating costs borne by a water company. In order to optimize the operation of a water pumping station, it is essential to devise an appropriate pumps schedule. The aim of the work was to develop a smart tool which would facilitate decision-making by the operator of a water intake, including a group of wells, supplying actual municipal waterworks. The tool creates a real-time schedule for wells and pumps integrated with them, which constitutes a basis for a final decision made by the operator, related to the degree and period of their usage. The main criterion of facilitating the decision-making pertained to achieving the minimum energy consumption during pumping water from a well to a reservoir tank, while simultaneously keeping all the wells on full stand-by. The schedule was prepared by means of binary linear programming. In this method, both the function of the goal and the limiting functions are linear, whereas the particular variables belong to the set {0,1}.
This dissertation focuses on binary linear programming problems (BLP) affected by uncertainties preventing the implementation of the solutions exactly as prescribed. This type of uncertainty is termed implementation u...
详细信息
This dissertation focuses on binary linear programming problems (BLP) affected by uncertainties preventing the implementation of the solutions exactly as prescribed. This type of uncertainty is termed implementation uncertainty and occurs due to model *** dissertation presents a model of binary variables under implementation uncertainty and develops a methodology to solve BLPs under this type of uncertainty consisting in a robust formulation (RBIU). The RBIU identifies solutions that satisfy given levels of optimality and feasibility for any realizations of the uncertainty. A solution methodology of the RBIU consists of an equivalent linearprogramming *** solutions tend to be conservative in the sense that they sacrifice optimality to achieve the given level of feasibility. This dissertation presents two methodologies to control the conservatism of the RBIU solutions. The first method consists in controlling the feasibility relaxation level and selecting the solutions bounding the value of the objective function. The second method is an extension of a well-known method in the field of robust optimization and consists in the development of a cardinality-constrained robust BLP under implementation uncertainty (CBIU) that controls the conservatism by bounding the maximum number of variables under uncertainty with different implemented and prescribed values. The proposed concepts of robustness are applied to the knapsack problem, assignment problem and shortest path problem (SPP) under implementation uncertainty to identify their solutions immune to uncertainty and to show how particular problem structures permit to identify different important theoretical and practical properties. This work examines the properties of the robust counterparts including configurations of the control parameters, complexity and the development of solutions *** dissertation includes experimental studies to show how the proposed concepts of robustnes
This paper proposes a V2G charging scheduling scheme for energy invoice minimization of railway station parking lots hosting plug-in electric vehicles. Using a two layer optimization technique the daily load profile o...
详细信息
ISBN:
(纸本)9781467384636
This paper proposes a V2G charging scheduling scheme for energy invoice minimization of railway station parking lots hosting plug-in electric vehicles. Using a two layer optimization technique the daily load profile of the railway station is reduced in order to increase the load factor and minimizing the annual energy invoice (AEI) of the station. binary linear programming is used as second layer for charging/discharging scheduling problem. The final results shows interests of using the proposed approach conducting its impact on minimizing annual optimum subscribed power, maximum demand power and annual energy invoice.
The paper presents a technique for solving the binary linear programming model in polynomial time. The general binary linear programming problem is transformed into a convex quadratic programming problem. The convex q...
详细信息
The paper presents a technique for solving the binary linear programming model in polynomial time. The general binary linear programming problem is transformed into a convex quadratic programming problem. The convex quadratic programming problem is then solved by interior point algorithms. This settles one of the open problems of whether P = NP or not. The worst case complexity of interior point algorithms for the convex quadratic problem is polynomial. It can also be shown that every liner integer problem can be converted into binarylinear problem.
A coupled binary linear programming-differential evolution (BLP-DE) approach is proposed in this paper to optimize the design of water distribution systems (WDS). Three stages are involved in the proposed BLP-DE optim...
详细信息
A coupled binary linear programming-differential evolution (BLP-DE) approach is proposed in this paper to optimize the design of water distribution systems (WDS). Three stages are involved in the proposed BLP-DE optimization method. In the first stage, the WDS that is being optimized is decomposed into trees and the core using a graph algorithm. binary linear programming is then used to optimize the design of the trees during the second stage. In the third stage, a differential evolution (DE) algorithm is utilized to deal with the core design while incorporating the optimal solutions for the trees obtained in the second stage, thereby yielding near-optimal solutions for the original whole WDS. The proposed method takes advantage of both the BLP and DE algorithms: BLP is capable of providing a global optimal solution for the trees (no loops involved) with great efficiency, and a DE is able to efficiently generate good quality solutions for the core (loops involved) with a reduced search space compared to the original full network. Two benchmark WDS case studies and one real-world case study (with multiple demand loading cases) with a number of decision variables ranging from 21-96 are used to verify the effectiveness of the proposed BLP-DE optimization approach. Results show that the proposed BLP-DE algorithm significantly outperforms other optimization algorithms in terms of both solution quality and efficiency.
暂无评论