combinatorial optimization

This paper discusses a special situation in project management in which an analyst wants to prioritize several independent activities to handle all them one after another, in such a way that there are no precedence relationships over the activities. As a novel idea, in this research, the notion is that the structure of prioritized activities is a linear arrangement, and therefore it could be taken into account as a combinatorial optimization problem. The paper formulates a mathematical model, develops a row-generation solving procedure, and reports the computational results for the problem instances of size up to 300 activities. The results demonstrate the applicability and efficiency of the proposed methodology.

Combinatorial optimization is the procedure of optimizing an objective function over the discrete configuration space. A genetic algorithm (GA) has been applied successfully to solve various NP-complete combinatorial optimization problems. One of the most challenging problems in applying GA is selecting mutation operators and associated probabilities for each situation. GA uses just one type of mutation operator with a specified probability in the basic form. The mutation operator is often selected randomly in improved GAs that leverage several mutation operators. While an effective GA search occurs when the mutation type for each chromosome is selected according to mutant genes and the problem landscape. This paper proposes an adaptive genetic algorithm that uses Q-learning to learn the best mutation strategy for each chromosome. In the proposed method, the success history of the mutant in solving the problem is utilized for specifying the best mutation type. For evaluating adaptive genetic algorithm, we adopted the traveling salesman problem (TSP) as a well-known problem in the field of optimization. The results of the adaptive genetic algorithm on five datasets show that this algorithm performs better than single mutation GAs up to 14% for average cases. It is also indicated that the proposed algorithm converges faster than single mutation GAs.

A combinatorial auction is an auction where the bidders have the choice to bid on bundles of items. The WDP in combinatorial auctions is the problem of finding winning bids that maximize the auctioneer’s revenue under the constraint that each item can be allocated to at most one bidder. The WDP is known as an NP-hard problem with practical applications like electronic commerce, production management, games theory, and resources allocation in multi-agent systems. This has motivated the quest for efficient approximate algorithms both in terms of solution quality and computational time. This paper proposes a hybrid Ant Colony Optimization with a novel Multi-Neighborhood Local Search (ACO-MNLS) algorithm for solving Winner Determination Problem (WDP) in combinatorial auctions. Our proposed MNLS algorithm uses the fact that using various neighborhoods in local search can generate different local optima for WDP and that the global optima of WDP is a local optima for a given its neighborhood. Therefore, proposed MNLS algorithm simultaneously explores a set of three different neighborhoods to get different local optima and to escape from local optima. The comparisons between ACO-MNLS, Genetic Algorithm (GA), Memetic Algorithm (MA), Stochastic Local Search (SLS), and Tabu Search (TS) on various benchmark problems confirm the efficiency of ACO-MNLS in the terms of solution quality and computational time.