A Linear Programming Based Approach to the Steiner Tree Problem with a Fixed Number of Terminals

We present a set of integer programs (IPs) for the Steiner tree problem with the property that the best solution obtained by solving all, provides an optimal Steiner tree. Each IP is polynomial in the size of the underlying graph and our main result is that the linear programming (LP) relaxation of each IP is … Read more

A specialized interior-point algorithm for huge minimum convex cost flows in bipartite networks

The computation of the Newton direction is the most time consuming step of interior-point methods. This direction was efficiently computed by a combination of Cholesky factorizations and conjugate gradients in a specialized interior-point method for block-angular structured problems. In this work we apply this algorithmic approach to solve very large instances of minimum cost flows … Read more

An Efficient Linear Programming Based Method for the Influence Maximization Problem in Social Networks

The influence maximization problem (IMP) aims to determine the most influential individuals within a social network. In this study first we develop a binary integer program that approximates the original problem by Monte Carlo sampling. Next, to solve IMP efficiently, we propose a linear programming relaxation based method with a provable worst case bound that … Read more

Structural Properties of Feasible Bookings in the European Entry-Exit Gas Market System

In this work we analyze the structural properties of the set of feasible bookings in the European entry-exit gas market system. We present formal definitions of feasible bookings and then analyze properties that are important if one wants to optimize over them. Thus, we study whether the sets of feasible nominations and bookings are bounded, … Read more

An Iterative Re-optimization Framework for the Dynamic Vehicle Routing Problem with Roaming Delivery Locations

Branch-and-price has established itself as an effective solution methodology for a wide variety of planning problems. We investigate its potential as a solution method- ology for solving operational problems. Specifically, we explore its potential in the context of a dynamic variant of the vehicle routing problem with roaming delivery locations, in which customer itineraries may … Read more

Efficient heuristic algorithm for identifying critical nodes in planar networks

This paper presents a new method for identifying critical nodes in planar networks. We propose an efficient method to evaluate the quality of solutions by using special properties of planar networks. It enables us to develop a computationally efficient heuristic algorithm for the problem. The proposed algorithm assisted on randomly generated planar networks. The experimental … Read more

A Critical Survey on the Network Optimization Algorithms for Evacuation Planning Problems

In the last decades, research on emergency traffic management has received high attention from the operations research community and many pioneer researchers have established it as one of the most fertile research areas. We consider the computationally hard flows over time problems from wider perspective including flow/time dependent attributes (dynamic flows), a possibility of flows … Read more

Efficient Algorithms for Flow over Time Evacuation Planning Problems with Lane Reversal Strategy

The contraflow techniques have widely been effective in evacuation planning research. We present effcient algorithms to solve the evacuation network flow problems, namely, the maximum, earliest arrival, quickest and lex-maximum dynamic contraflow problems having constant attributes and their generalizations with partial contraflow recon guration. Moreover, the contraflow models with inflow dependent and load dependent transit times … Read more

Fast robust shortest path computations

We develop a fast method to compute an optimal robust shortest path in large networks like road networks, a fundamental problem in traffic and logistics under uncertainty. In the robust shortest path problem we are given an $s$-$t$-graph $D(V,A)$ and for each arc a nominal length $c(a)$ and a maximal increase $d(a)$ of its length. … Read more