This paper explores the connections between the classical maximum clique problem and its edge-weighted generalization, the maximum edge weight clique (MEWC) problem. As a result, a new analytic upper bound on the clique number of a graph is obtained and an exact algorithm for solving the MEWC problem is developed. The bound on the clique number is derived using a Lagrangian relaxation of an integer (linear) programming formulation of the MEWC problem. Furthermore, coloring-based bounds on the clique number are used in a novel upper-bounding scheme for the MEWC problem. This scheme is employed within a combinatorial branch-and-bound framework, yielding an exact algorithm for the MEWC problem. Results of computational experiments demonstrate a superior performance of the proposed algorithm compared with existing approaches.

The Unit Commitment Problem (UCP) is a well-known combinatorial optimization problem in power systems. The main goal in the UCP is to schedule a subset of a given group of electrical power generating units and also to determine their production output in order to meet energy demands at minimum cost. In addition, a set of technological and operational constraints must be satisfied. A large variety of optimization methods addressing the UCP is available in the literature. This panoply of methods includes exact methods (such as dynamic programming, branch-and-bound) and heuristic methods (tabu search, simulated annealing, particle swarm, genetic algorithms). This paper proposes two non-traditional formulations. First, the UCP is formulated as a mixed-integer optimal control problem with both binary-valued control variables and real-valued control variables. Then, the problem is formulated as a switching time dynamic optimization problem involving only real-valued controls. Copyright

This research aims to help in establishing new legislative directives by testing their impact both on the company profits and on the life of city residents. A case study is developed and conducted in collaboration with the city hall and with eight companies (four freight transport companies and four retailer companies). The impacts are computed by simulating the companies operation under the new legislation and the new routes are used to analyze the impacts on the city traffic, noise, and congestion.

In this work we address the Singe-Source Uncapacitated Minimum Cost Network Flow Problem with concave cost functions. Given that this problem is of a combinatorial nature and also that the total costs are nonlinear, we propose a hybrid heuristic to solve it. In this type of algorithms one usually tries to manage two conflicting aspects of searching behaviour: exploration, the algorithm's ability to search broadly through the search space; and exploitation, the algorithm ability to search locally around good solutions that have been found previously. In our case, we use an Ant Colony Optimization algorithm to mainly deal with the exploration, and a Local Search algorithm to cope with the exploitation of the search space. Our method proves to be very efficient while solving both small and large size problem instances. The problems we have used to test the algorithm were previously solved by other authors using other population based heuristics and our algorithm was able to improve upon their results, both in terms of computing time and solution quality.

Abstract We address the single‐source uncapacitated minimum cost network flow problem with general concave cost functions. Exact methods to solve this class of problems in their full generality are only able to address small to medium size instances, since this class of problems is known to be NP‐Hard. Therefore, approximate methods are more suitable. In this work, we present a hybrid approach combining a genetic algorithm with a local search. Randomly generated test problems have been used to test the computational performance of the algorithm. The results obtained for these test problems are compared to optimal solutions obtained by a dynamic programming method for the smaller problem instances and to upper bounds obtained by a local search method for the larger problem instances. From the results reported it can be shown that the hybrid methodology improves upon previous approaches in terms of efficiency and also on the pure genetic algorithm, i.e., without using the local search procedure. © 2007 Wiley Periodicals, Inc. NETWORKS, Vol. 50(1), 67–76 2007

Abstract In this paper, we describe a heuristic algorithm based on local search for the Single‐Source Uncapacitated (SSU) concave Minimum‐Cost Network Flow Problem (MCNFP). We present a new technique for creating different and informed initial solutions to restart the local search, thereby improving the quality of the resulting feasible solutions (upper bounds). Computational results on different classes of test problems indicate the effectiveness of the proposed method in generating basic feasible solutions for the SSU concave MCNFP very near to a global optimum. A maximum upper bound percentage error of 0.07% is reported for all problem instances for which an optimal solution has been found by a branch‐and‐bound method. © 2003 Wiley Periodicals, Inc.