Search

In this paper, we study the knapsack problem with conflict pair constraints. After a thorough literature survey on the topic, our study focuses on the special case of bipartite conflict graphs. For complete bipartite (multipartite) conflict graphs, the problem is shown to be NP-hard but solvable in pseudo-polynomial time, and it admits an FPTAS. Extensions of these results to more general classes of graphs are also presented. Further, a class of integer programming models for the general knapsack problem with conflict pair constraints is presented, which generalizes and unifies the existing formulations. The strength of the LP relaxations of these formulations is analyzed, and we discuss different ways to tighten them. Experimental comparisons of these models are also presented to assess their relative strengths. This analysis disclosed various strong and weak points of different formulations of the problem and their relationships to different types of problem data. This information can be used in designing special purpose algorithms for KPCC involving a learning component. [ABSTRACT FROM AUTHOR]

The integration of different energy resources from traditional power systems presents new challenges for real-time implementation and operation. In the last decade, a way has been sought to optimize the operation of small microgrids (SMGs) that have a great variety of energy sources (PV (photovoltaic) prosumers, Genset CHP (combined heat and power), etc.) with uncertainty in energy production that results in different market prices. For this reason, metaheuristic methods have been used to optimize the decision-making process for multiple players in local and external markets. Players in this network include nine agents: three consumers, three prosumers (consumers with PV capabilities), and three CHP generators. This article deploys metaheuristic algorithms with the objective of maximizing power market transactions and clearing price. Since metaheuristic optimization algorithms do not guarantee global optima, an exhaustive search is deployed to find global optima points. The exhaustive search algorithm is implemented using a parallel computing architecture to reach feasible results in a short amount of time. The global optimal result is used as an indicator to evaluate the performance of the different metaheuristic algorithms. The paper presents results, discussion, comparison, and recommendations regarding the proposed set of algorithms and performance tests. [ABSTRACT FROM AUTHOR]