This work is focused on the resolution of a mixed model for the design of large-sized networks. An algorithm is introduced, whose initial outcomes are promising in terms of topological robustness regarding connectivity and reliability. The algorithm combines the network survivability and the network reliability approaches. The problem of the topological design has been modeled based on the generalized Steiner problem with node-connectivity constraints (GSPNC), which is NP-hard. The aim of this study is to heuristically solve the GSP-NC model by designing low-cost highly connected topologies and to measure the reliability of such solutions with respect to a certain prefixed lower threshold. This research introduces a greedy randomized algorithm for the construction of feasible solutions for the GSP-NC and a local search algorithm based on the variable neighborhood search (VNS) method, customized for the GSP-NC. In order to compute the built network reliabilities, this work adapts the recursive variance reduction (RVR) technique, as a simulation method since the exact evaluation of this measurement is also NP-hard. The experimental tests were performed over a wide set of testing cases, which contained heterogeneous topologies, including instances of more than 200 nodes. The computational results showed highly competitive execution times, achieving minimal local optimal solutions of good quality fulfilling the imposed survivability and reliability conditions.
In Market Basket Analysis, the goal is to understand the human behavior in order to maximize sales. An evident behavior is to buy correlated items. As a consequence, the determination of a set of items with a large correlation with others is a valuable tool for Market Basket Analysis. In this paper we address a combinatorial optimization problem that formalizes the previous application. Given a simple graph \(\mathcal {G}=(V,E)\) (where the nodes are items and links represent correlation), we want to find the clique \(\mathcal {C} \subseteq V\) such that the number of links shared between \(\mathcal {C}\) and \(V - \mathcal {C}\) is maximized. This problem is known in the literature as Max Cut-Clique (MCC). The contributions of this paper are three-fold. First, the computational complexity of the MCC is established. Second, a full GRASP/VND methodology enriched with a Tabu Search is here developed, where the main ingredients are novel local searches and a Restricted Candidate List that trades greediness for randomization in a multi-start fashion. A Tabu Search is also included in order to avoid locally optimum solutions. Finally, a fair comparison with respect to recent heuristics reveals that our proposal is competitive with state-of-the-art solutions.
29 April 2020 in International Transactions in Operational Research
Students from Master of Business Administration (MBA) programs are usually split into teams. In light of the generalistic nature of MBA programs, diversity within every team is desirable in terms of gender, major, age and other criteria. Many schools rotate the teams at the beginning of every term so that each student works with a different set of peers during every term, thus training his or her adaptation skills and expanding the peer network. Achieving diverse teams while avoiding–or minimizing—the repetition of student pairs is a complex and time-consuming task for MBA Directors. We introduce the Max-Diversity Orthogonal Regrouping (MDOR) problem to manage the challenge of splitting a group of people into teams several times, pursuing the goals of high diversity and few repetitions. We propose a hybrid Greedy Randomized Adaptive Search Procedure/Variable Neighborhood Descent (GRASP/VND) heuristic combined with tabu search and path relinking for its resolution, as well as an Integer Linear Programming (ILP) formulation. We compare both approaches through a set of real MBA cohorts, and the results show that, in all cases, the heuristic approach significantly outperforms the ILP and manually formed teams in terms of both diversity and repetition levels.