Search

In this paper, we study the quadratic assignment problem with a rank-one cost matrix (QAP-R1). Four integer-programming formulations are introduced of which three are assumed to have partial integer data. Unlike the standard quadratic assignment problem, some of our formulations can solve reasonably large instances of QAP-R1 with impressive running times and are faster than some metaheuristics. Pairwise relative strength of the LP relaxations of these formulations are also analyzed from theoretical and experimental points of view. Finally, we present a new metaheuristic algorithm to solve QAP-R1 along with its computational analysis. Our study offers the first systematic experimental analysis of integer-programming models and heuristics for QAP-R1. The benchmark instances with various characteristics generated for our study are made available to the public for future research work. Some new polynomially solvable special cases are also introduced. Summary of Contribution: This paper aims to advance our knowledge and ability in solving an important special case of the quadratic assignment problem. It shows how to exploit inherent properties of an optimization problem to achieve computational advantages, a strategy that was followed by researchers in model building and algorithm developments for decades. Our computational results attest to this time-tested general philosophy. The paper presents the first systematic computational study of the rank one quadratic assignment problem, along with new mathematical programming models and complexity analysis. We believe the theoretical and computational results of this paper will inspire further research on the topic and will be of significant value to practitioners using rank one quadratic assignment models. [ABSTRACT FROM AUTHOR]

Modeling of transportation systems must invariably balance behavioral richness and computational tractability. In this paper, we develop a transportation equilibrium model and an algorithm for the simultaneous prediction of trip generation, trip distribution, modal split, and trip assignment on large-scale networks. The model achieves a practical compromise between behavioral and computational aspects of modeling the problem. It is formulated as an equivalent convex optimization problem, yet it is behaviorally richer than other models that can be cast as equivalent convex programs. Although the model is not as behaviorally rich as the most general equilibrium models, it has computational advantages. The applications reported in this paper of the model to real systems, i.e., the intercity transport network of Egypt and the urban transportation network of Austin, Texas, illustrate the computational attractiveness of the approach. These results indicate that equivalent optimization formulations are not as restrictive as previously thought, and hence, the equivalent convex programming approach for modeling and predicting equilibrium on transportation systems remains a viable and fruitful avenue for future consideration. [ABSTRACT FROM AUTHOR]

The paper introduces a cutting-plane matheuristic for the design-balanced capacitated multicommodity network design problem, one of the premier formulations for the service network design problem with asset management concerns increasingly faced by carriers within their tactical planning processes. The matheuristic combines a cutting-plane procedure efficiently computing tight lower bounds and a variable-fixing procedure feeding a MIP solver. Learning mechanisms embedded into the cutting-plane procedure provide the means to identify promising variables and thus both reduce the dimension of the problem instance, making it addressable by a MIP solver, and guide the latter toward promising solution spaces. Extensive computational experiments show the efficiency of the proposed procedures in obtaining high-quality solutions, outperforming the current best methods from the literature. [ABSTRACT FROM AUTHOR]

This paper is concerned with the optimal constrained pruning of decision trees. We present a novel 0-1 programming model for pruning the tree to minimize some general penalty function based on the resulting leaf nodes, and show that this model possesses a totally unimodular structure that enables it to be solved as a shortest-path problem on an acyclic graph. Moreover, we prove that this problem can be solved in strongly polynomial time while incorporating an additional constraint on the number of residual leaf nodes. Furthermore, the framework of the proposed modeling approach renders it suitable to accommodate different (multiple) objective functions and side-constraints, and we identify various such modeling options that can be applied in practice. The developed methodology is illustrated using a numerical example to provide insights, and some computational results are presented to demonstrate the efficacy of solving generically constrained problems of this type. We also apply this technique to a large-scale transportation analysis and simulation system (TRANSIMS), and present related computational results using real data to exhibit the flexibility and effectiveness of the proposed approach. [ABSTRACT FROM AUTHOR]

The purpose of this paper is to describe in detail an implementation of a primal-dual interior point method for solving linear programming problems. Preliminary computational results indicate that this implementation compares favorably with a comparable implementation of a dual affine interior point method, and with MINOS 5.0, a state-of-the-art implementation of the simplex method. [ABSTRACT FROM AUTHOR]

Many transportation problems can be formulated as a linearly-constrained convex programming problem whose objective function consists of entropy functions and other cost-related terms. In this paper, we propose an unconstrained convex programming dual approach to solving these problems. In particular, we focus on a class of linearly-constrained entropy maximization problem with quadratic cost, study its Lagrangian dual, and provide a globally convergent algorithm with a quadratic rate of convergence. The theory and algorithm can be readily applied to the trip distribution problem with quadratic cost and many other entropy-based formulations, including the conventional trip distribution problem with linear cost, the entropy-based modal split model, and the decomposed problems of the combined problem of trip distribution and assignment. The efficiency and the robustness of this approach are confirmed by our computational experience. [ABSTRACT FROM AUTHOR]

Continuous location models generally use the Euclidean or rectangular norm to approximate travel in a transportation network. This paper considers a new and more accurate distance measure, termed the weighted one-two norm, which is a positive linear combination of the preceding norms. A directional bias function is introduced to show the equivalence of this distance measure to the well known l[sub p] norm. We then formulate a simple linear regression model to fit the parameters of our distance function to a given data set. Some novel applications based on standard statistical tests are derived which provide practical insights into the nature of networks with rectangular bias. The results are readily extended to other types of networks. [ABSTRACT FROM AUTHOR]

International shipping is a multibillon dollar business and shipping companies may expect large benefits from improving the routing and scheduling processes of their ships. In this paper, we describe a container-ship routing scenario in which a shipping company provides services to a network of ports. We formulate a mathematical programming model that maximizes total profit (i.e., revenue minus operating costs) for multiple ships and determines: (a) the optimal sequence of ports of call for each ship, (b) the number of trips each ship makes in a planning horizon, and (c) the amount of cargo transported between any two ports by each ship. The model contains discrete, 0-1 and continuous variables, and nonlinear complicating constraints. The multiple container ship model is quite different from those of vehicle routing and traveling salesman problems. We use a decomposition method for the model as well as for the network in order to solve the problem. Several problems on 10- to 20-port networks are solved and the results presented. [ABSTRACT FROM AUTHOR]

This paper discusses a model for the problem of locating garages in an urban mass transit system and the associated assignment of vehicles to garages for background and peak services of transit lines. The objective of this model is to minimize the sum of fixed site-related costs, variable vehicle costs, and crew relief costs. The model is solved by an iterative procedure involving a location interchange heuristic and a network flow-based algorithm. The implementation of the model is discussed through its various stages, from data preparation to the final policy recommendations. [ABSTRACT FROM AUTHOR]

We consider algorithms proposed for solving the fixed demand user optimized network equilibrium problem with asymmetric user costs. Because the Jacobian matrix for the costs is asymmetric, no known equivalent convex optimization problem exists and alternative solution methods to nonlinear programming techniques must be sought. The purpose of this paper is to compare the performance of several existing methods for determining the equilibrium network flows of a small realistic network model in which intersection controls are incorporated which lead to particularly asymmetric cost functions. [ABSTRACT FROM AUTHOR]