Enhanced Compact Models for the Connected Subgraph Problem and for the Shortest Path Problem in Digraphs with Negative Cycles
Haouari, Mohamed . 2013
We investigate the minimum-weight connected subgraph problem. The importance of this problem stems from the fact that it constitutes the back bone of many network design problems having applications in several areas including telecommunication, energy, and distribution planning. Weshow that thisproblemis NP-hard, and we propose a new polynomial-size non linear mixed-integer programming model.We apply the Reformulation-LinearizationTechnique (RLT) to linearize the proposed model while keeping a polynomial number of variables and constraints. Furthermore, we show how similar modelling techniques enable an enhanced polynomial size formulation to be derived for the shortest elementary path. This latter problem is known to be intractable and has many applications (in particular, within the context of column generation).We report the results of extensive computational experiments on graphs with up to1000 nodes.These results at test to the efficacy of the
proposed compact formulations. In particular, we show that the proposed formulations consistently outperform compact formulations from the literature.
In this paper, we address a real-world optimization problem; the scheduling of a Bank Information Technologies (IT) staff. This problem can be defined as the process of constructing optimized work…
In this paper, we address the problem of minimizing the consumed electric energy for a personal rapid transit transportation system, in order to fulfil a planned list of trips, performed by a set…
We investigate the two-stage guillotine two-dimensional cutting stock problem. This problem commonly