We investigate a challenging NP-hard variant of Network Design Problems called the Discrete Cost Multicommodity Network Design Problem (DCMNDP), which arises in a wide range of real-life situations such as telecommuni...
详细信息
ISBN:
(纸本)9781509067787
We investigate a challenging NP-hard variant of Network Design Problems called the Discrete Cost Multicommodity Network Design Problem (DCMNDP), which arises in a wide range of real-life situations such as telecommunication settings, multicast routing and aircraft assignment. In graph theory terms, the DCMNDP requires designing a minimum cost network by installing at most one facility on each edge while the installed capacities permit the routing of a prescribed multi-commodity flow value. We focus on investigating polynomial-sized mixedintegerlinearprogramming (MILP) formulations. Besides a basic arc-flow formulation, two new overflow and flow aggregation based formulations are proposed. To improve the performance of the proposed formulations, valid cuts/constraints are appended. Preliminary computational results are conducted on real-world networks and randomly generated instances using a general-purpose MIP solver.
Given a connected, undirected and m-partite complete graph G = (V-1 boolean OR V-2 boolean OR ... boolean OR V-m;E), the Generalized Minimum Spanning Tree Problem (GMSTP) consists in finding a tree with exactly m - 1 ...
详细信息
ISBN:
(数字)9783319961514
ISBN:
(纸本)9783319961514;9783319961507
Given a connected, undirected and m-partite complete graph G = (V-1 boolean OR V-2 boolean OR ... boolean OR V-m;E), the Generalized Minimum Spanning Tree Problem (GMSTP) consists in finding a tree with exactly m - 1 edges, connecting the m clusters V-1, V-2,..., V-m through the selection of a unique vertex in each cluster. GMSTP finds applications in network design, irrigation agriculture, smart cities, data science, among others. This paper presents a new multigraph mathematical formulation for GMSTP which is compared to existing formulations from the literature. The proposed model proves optimality for well-known GMSTP instances. In addition, this work opens new directions for future research to the development of sophisticated cutting plane and decomposition algorithms for related problems.
Over the last few decades, a number of mathematical models have been introduced for solving Multi-mode Resource Constrained Project Scheduling Problems (MRCPSPs). However the computational effort required in solving t...
详细信息
ISBN:
(纸本)9783662452370;9783662452363
Over the last few decades, a number of mathematical models have been introduced for solving Multi-mode Resource Constrained Project Scheduling Problems (MRCPSPs). However the computational effort required in solving those models depends on the number of variables. In this paper, we attempt to reduce the number of variables required in representing MRCPSPs by formulating two new event-based models. A comparative study was conducted by solving standard benchmark instances using a common objective function for the developed as well as the existing mathematical models. The study provided interesting insights about the problem characteristics, model sizes, solution quality, and computational effort of these approaches.
In this paper, we consider a linear bilevel programming problem where both the leader and the follower maximize their profits subject to budget constraints. Additionally, we impose a Hamiltonian cycle topology constra...
详细信息
ISBN:
(纸本)9789897582189
In this paper, we consider a linear bilevel programming problem where both the leader and the follower maximize their profits subject to budget constraints. Additionally, we impose a Hamiltonian cycle topology constraint in the leader problem. In particular, models of this type can be motivated by telecommunication companies when dealing with traffic network flows from one server to another one within a ring topology framework. We transform the bilevel programming problem into an equivalent single level optimization problem that we further linearize in order to derive mixedintegerlinearprogramming (MILP) formulations. This is achieved by replacing the follower problem with the equivalent Karush Kuhn Tucker conditions and with a linearization approach to deal with the complementarity constraints. The topology constraint is handled by the means of two compact formulations and an exponential one from the classic traveling salesman problem. Thus, we compute optimal solutions and upper bounds with linear programs. One of the compact models allows to solve instances with up to 250 nodes to optimality. Finally, we propose an iterative procedure that allows to compute optimal solutions in remarkably less computational effort when compared to the compact models.
暂无评论