This paper presents a hybrid BRKGA (Q-HBRKGA) that combines BRKGA with Q-learning and a Local Branching technique to solve the Knapsack Problem with Forfeits(KPF). The aim is to tackle this problem, a vari-ant of the 0–1 Knapsack Problem, where a penalty cost is imposed when both items of a forfeit pair are included in the solution. Notably, Q-HBRKGA achieves superior results compared to existing approaches, establishing a valid strategy for KPF problem-solving. Computational experiments, utilizing benchmark instances, demonstrate the efficacy of Q-HBRKGA by outperforming state-of-the-art methods documented in the literature.

A formulation, a heuristic, and branch-and-cut algorithms are investigated for the chordless cycle problem. This is the problem of finding a largest simple cycle for a given graph so that no edge between nonimmediately subsequent cycle vertices is contained in the graph. Leaving aside procedures based on complete enumeration, no previous exact solution algorithm appears to exist for the problem, which is relevant both in theoretical and practical terms. Extensive computational results are reported here for randomly generated graphs and for graphs originating from the literature. Under acceptable CPU times, certified optimal solutions are presented for graphs with as many as 100 vertices. Summary of Contribution: Finding chordless cycles of a graph, also known as holes, is relevant, among others, to graph theory, to the design of polyhedral based exact solution algorithms to integer programming (IP) problems, and to the practical applications that benefit from these algorithms. For instance, perfect graphs do not contain odd holes. Additionally, odd hole inequalities are valid for strengthening the formulations to numerous problems that are directly defined over graphs. Furthermore, these inequalites, in association with applicable conflict graphs, are used by all modern IP solvers to preprocess and strengthen virtually any IP formulation submitted to them.

Abstract Scheduling by Edge Reversal provides an order of operation for nodes in a graph, but maximizing or minimizing the resulting concurrency is hard. In this paper, we discuss a series of real‐world applications for this technique and propose algorithms for both problems. For maximum concurrency, we prove its general inapproximability and introduce approximation algorithms for classes of graphs. For minimum concurrency, we use hardness and inapproximability results to establish its relation to longest cycles, while also introducing a novel application for assembling musical phrases.

A Service-Level Agreement (SLA) usually refers to computational services (e.g., cloud/web services), indicating contract goals and expected Quality of Service (QoS), recently extended for transportation problems called Logistics SLA. Transportation problems are being systematically studied for Smart City (SC) applications due to its huge importance: public transportation services, drone delivery services, battery recharging for electric vehicles, and also transportation for private companies considering real-time traffic information. Many of these transportations problems involve not only one-way deliveries, but also pickups, forming a set of routes with desired QoS such as maximum route length/time, delivery/pickup sequences and time-windows. In order to achieve all desired QoS, while minimizing routing distances, this problem can be seen as an extension of the challenging Vehicle Routing Problem (VRP), which is known to be NP-Hard. Computational intelligence strategies such as metaheuristics are often employed to find near-optimal solutions in short computational times. In this paper, we deal with a practical industrial problem involving employees transportation to a workplace in a Brazilian metropolis, involving minimization of operational costs, achievement of QoS requirements and visualization of the routes.

Given a connected and undirected graph G, the degree preserving spanning tree problem (DPSTP) asks for a spanning tree of G with the maximum number of vertices having the same degree in the tree and in G. These are called full degree vertices. We introduce integer programming formulations, valid inequalities and four exact solution approaches based on different formulations. Two branch‐and‐bound procedures, a branch‐and‐cut (BC) algorithm and an iterative probing combinatorial Benders decomposition method are introduced here. The problem of optimally lifting one of the classes of valid inequalities proposed here is equivalent to solving a DPSTP instance, for a conveniently defined subgraph of G. We thus apply one of the proposed methods to optimally lift these cuts, within the other solution methods. In doing so, two additional algorithms, a hybrid Benders decomposition and a hybrid BC are proposed. Extensive computational experiments are conducted with the solution algorithms introduced in this study. © 2015 Wiley Periodicals, Inc. NETWORKS, Vol. 65(4), 329–343 2015

Due to the constant development of society, increasing quantities of commodities have to be transported in large urban centers. Therefore, network planning problems arise as tools to support decision-making, aiming to meet the need of finding efficient ways to perform such transportations. This paper review a bi-level formulation, an one level formulation obtained by applying the complementary slackness theorem, Bellman's optimality conditions and presents an improved Relax-and-Fix heuristic, through combining a randomized constructive algorithm with a Relax-and-Fix heuristic, so high quality solutions could be found. Besides that, our computational results are compared with the results found by an one-level formulation and other heuristics found in the literature, showing the efficiency of the proposed method.

We present exact algorithms for solving the minimum connected dominating set problem in an undirected graph. The algorithms are based on two approaches: a Benders decomposition algorithm and a branch-and-cut method. We also develop a hybrid algorithm that combines these two approaches. Two variants of each of the three resulting algorithms are considered: a stand-alone version and an iterative probing variant. The latter variant is based on a simple property of the problem, which states that if no connected dominating set of a given cardinality exists, then there are no connected dominating sets of lower cardinality. We present computational results on a large set of instances from the literature.

Abstract The hop‐constrained survivable network design problem consists of finding a minimum cost subgraph containing K edge‐disjoint paths with length at most H joining each pair of vertices in a given demand set. When all demands have a common vertex, the instance is said to be rooted. We propose a new extended formulation for the rooted case, called hop‐level multicommodity flow (MCF), that can be significantly stronger than the previously known formulations, at the expense of having a larger number of variables and constraints, growing linearly with the number of edges and demands and quadratically with H . However, for the particular case where H = 2, it can be specialized into a very compact and efficient formulation. Even when H = 3, hop‐level‐MCF can still be quite efficient and it has solved several instances from the literature for the first time. © 2012 Wiley Periodicals, Inc. NETWORKS, 2013