Shunting Minimal Rail Car Allocation

We consider the rail car management at industrial in-plant railroads. Demands for materials or empty cars are characterized by a track, a car type, and the desired quantity. If available, we assign cars from the stock, possibly substituting types, otherwise we rent additional cars. Transportation requests are fulfilled as a short sequence of pieces of … Read more

A hybrid heuristic for the P-median problem

Given N customers and a set F of M potential facilities, the P-median problem consists in finding a subset of F with P facilities such that the cost of serving all customers is minimized. This is a well-known NP-complete problem with important applications in location science and classification (clustering). We present a multistart hybrid heuristic … Read more

Faster Approximation Schemes for Fractional Multicommodity Flow Problems

We present fully polynomial approximation schemes for concurrent multicommodity flow problems that run in time of minimal dependency on the number of commodities k. We show that by modifying the algorithms by Garg & Konemann and Fleischer we can reduce their running time to a logarithmic dependence on k, and essentially match the running time … Read more

On Semidefinite Programming Relaxations for the Satisfiability Problem

This paper is concerned with the analysis and comparison of semidefinite programming (SDP) relaxations for the satisfiability (SAT) problem. Our presentation is focussed on the special case of 3-SAT, but the ideas presented can in principle be extended to any instance of SAT specified by a set of boolean variables and a propositional formula in … Read more

A hybrid genetic algorithm for the weight setting problem in OSPF/IS-IS routing

Intra-domain traffic engineering aims to make more efficient use of network resources within an autonomous system. Interior Gateway Protocols such as OSPF (Open Shortest Path First) and IS-IS (Intermediate System-Intermediate System) are commonly used to select the paths along which traffic is routed within an autonomous system. These routing protocols direct traffic based on link … Read more

Error bounds and limiting behavior of weighted paths associated with the SDP map ^{1/2}SX^{1/2}$

This paper studies the limiting behavior of weighted infeasible central paths for semidefinite programming obtained from centrality equations of the form $X^{1/2}S X^{1/2} = \nu W$, where $W$ is a fixed positive definite matrix and $\nu>0$ is a parameter, under the assumption that the problem has a strictly complementary primal-dual optimal solution. It is shown … Read more

A stochastic programming approach for supply chain network design under uncertainty

This paper proposes a stochastic programming model and solution algorithm for solving supply chain network design problems of a realistic scale. Existing approaches for these problems are either restricted to deterministic environments or can only address a modest number of scenarios for the uncertain problem parameters. Our solution methodology integrates a recently proposed sampling strategy, … Read more

Finding the projection of a point onto the intersection of convex sets via projections onto halfspaces

We present a modification of Dykstra’s algorithm which allows us to avoid projections onto general convex sets. Instead, we calculate projections onto either a halfspace or onto the intersection of two halfspaces. Convergence of the algorithm is established and special choices of the halfspaces are proposed. The option to project onto halfspaces instead of general … Read more

Sensitivity analysis of parameterized variational inequalities

We discuss in this paper continuity and differentiability properties of solutions of parameterized variational inequalities (generalized equations). To this end we use an approach of formulating variational inequalities in a form of optimization problems and applying a general theory of perturbation analysis of parameterized optimization problems. Citation School of Industrial and Systems Engineering, Georgia Institute … Read more

Genetic Algorithm for Solving Convex Quadratic Bilevel Programming Problem

This paper presents a genetic algorithm method for solving convex quadratic bilevel programming problem. Bilevel programming problems arise when one optimization problem, the upper problem, is constrained by another optimization, the lower problem. In this paper, the bilevel convex quadratic problem is transformed into a single level problem by applying Kuhn-Tucker conditions, and then an … Read more