Thomas L. Magnanti

A Unifying Geometric Solution Framework and Complexity Analysis for Variational Inequalities (1996)

In this paper, we propose a concept of polynomiality for variational inequality problems and show how to find a near optimal solution of variational inequality problems in a polynomial number of...

A decomposition algorithm for local access telecommunications network expansion planning (1995)

In this paper, we propose a concept of polynomiality for variational inequality problems and show how to find a near optimal solution of variational inequality problems in a polynomial number of...

Anantaram Balakrishnan, Anantaram Balakrishnan, Thomas L. Magnanti, Thomas L. Magnanti, Richard T. Wong, Richard T. Wong

Growing demand, increasing diversity of services, and advances in transmission and switching technologies are prompting telecommunication companies to rapidly expand and modernize their networks....

Optimizing constrained subtrees of trees (1995)

El Houssaine Aghezzaf, El Houssaine Aghezzaf, Thomas L. Magnanti, Thomas L. Magnanti, Laurence A. Wolsey, Laurence A. Wolsey

Given a tree G = (V, E) and a weight function defined on subsets of its nodes, we consider two associated problems. The first, called the "rooted subtree problem", is to find a...

Applications of Network Optimization (1995)

Ravindra K. Ahuja, Thomas L. Magnanti, James B. Orlin, M.R. Reddy

Network optimization has always been a core problem domain in operations research, as well as in computer science, applied mathematics, and many fields of engineering and management. Network...

Applications of Network Optimization (1995)

R. Ahuja, T. L. Magnanti, J. B. Orlin, Ravindra K. Ahuja, Thomas L. Magnanti, James B. Orlin, ...

I

Doubling or Splitting: Strategies for Modeling and Analyzing Survivable Network Design Problems (1994)

Balakrishnan, Anantaram, Magnanti, Thomas L., Mirchandani, Prakash

Survivability is becoming an increasingly important criterion in network design. This paper studies formulations, heuristic worst-case performance, and linear programming relaxations for two classes...

Averaging Schemes for Solving Fived Point and Variational Inequality Problems (1994)

Averaging Schemes for Solving Fived Point and Variational Inequality Problems (1994)

We develop and study averaging schemes for solving fixed point and variational inequality problems. Typically, researchers have established convergence results for solution methods for these problems...

Doubling or Splitting: Strategies for Modeling and Analyzing Survivable Network Design Problems (1994)

We develop and study averaging schemes for solving fixed point and variational inequality problems. Typically, researchers have established convergence results for solution methods for these problems...

Balakrishnan, Anantaram, Magnanti, Thomas L., Mirchandani, Prakash

Survivability is becoming an increasingly important criterion in network design. This paper studies formulations, heuristic worst-case performance, and linear programming relaxations for two classes...

Optimal Trees (1994)

Magnanti, Thomas L., Wolsey, Laurence A.

Not Available

Optimal Trees (1994)

Magnanti, Thomas L., Wolsey, Laurence A.

Not Available

Designing Hierarchical Survivable Networks (1994)

Balakrishnan, Anantaram, Magnanti, Thomas L., Mirchandani, Prakash

As the computer, communication, and entertainment industries begin to integrate phone, cable, and video services and to invest in new technologies such as fiber optic cables, interruptions in service...

Heuristics, LPs, and Trees on Trees: Network Design Analyses (1994)

Balakrishnan, Anantaram, Magnanti, Thomas L., Mirchandani, Prakash

We study a class of models, known as overlay optimization problems, with a "base" subproblem and an "overlay" subproblem, linked by the requirement that the overlay solution be contained in the base...

Heuristics, LPs, and Trees on Trees: Network Design Analyses (1994)

Balakrishnan, Anantaram, Magnanti, Thomas L., Mirchandani, Prakash

We study a class of models, known as overlay optimization problems, with a "base" subproblem and an "overlay" subproblem, linked by the requirement that the overlay solution be contained in the base...

Designing Hierarchical Survivable Networks (1994)

Balakrishnan, Anantaram, Magnanti, Thomas L., Mirchandani, Prakash

As the computer, communication, and entertainment industries begin to integrate phone, cable, and video services and to invest in new technologies such as fiber optic cables, interruptions in service...

-. · It-I--- I P Optimal Trees *t (1994)

Thomas L. Magnanti, Laurence A. Wolsey

Convergence Conditions for Variational Inequality Algorithms (1993)

Convergence Conditions for Variational Inequality Algorithms (1993)

Within the extensive variational inequality literature, researchers have developed many algorithms. Depending upon the problem setting, these algorithms ensure the convergence of (i) the entire...

On the Convergence of Classical Variational Inequality Algorithms (1993)

Within the extensive variational inequality literature, researchers have developed many algorithms. Depending upon the problem setting, these algorithms ensure the convergence of (i) the entire...

On the Convergence of Classical Variational Inequality Algorithms (1993)

In this paper, we establish global convergence results for projection and relaxation algorithms for solving variational inequality problems, and for the Frank-Wolfe algorithm for solving convex...

Heuristics, LPs, and Generalizations of Trees on Trees (1993)

In this paper, we establish global convergence results for projection and relaxation algorithms for solving variational inequality problems, and for the Frank-Wolfe algorithm for solving convex...

Balakrishnan, Anantaram, Magnanti, Thomas L., Mirchandani, Prakash

We study a class of models, known as overlay optimization problems, with a "base" subproblem and an "overlay" subproblem, linked by the requirement that the overlay solution be contained in the base...

Heuristics, LPs, and Generalizations of Trees on Trees (1993)

Balakrishnan, Anantaram, Magnanti, Thomas L., Mirchandani, Prakash

We study a class of models, known as overlay optimization problems, with a "base" subproblem and an "overlay" subproblem, linked by the requirement that the overlay solution be contained in the base...

The convex hull of two core capacitated network design problems (1993)

Prakash Mirch, Thomas L. Magnanti, Thomas L. Magnanti, Prakash Mirchandani, Rita Vachani, Rita Vachani

The network loading problem (NLP) is a specialized capacitated network design problem in which prescribed point-to-point demand between various pairs of nodes of a network must be met by installing...

Optimizing Constrained Subtrees of Trees (1992)

Aghezzaf, El Houssaine, Magnanti, Thomas L., Wolsey, Laurence A.

Given a tree G = (V, E) and a weight function defined on subsets of its nodes, we consider two associated problems. The first, called the "rooted subtree problem", is to find a maximum weight...

Optimizing Constrained Subtrees of Trees (1992)

Aghezzaf, El Houssaine, Magnanti, Thomas L., Wolsey, Laurence A.

Given a tree G = (V, E) and a weight function defined on subsets of its nodes, we consider two associated problems. The first, called the "rooted subtree problem", is to find a maximum weight...

The Multi-Network Design Problem (1991)

Balakrishnan, Anantaram, Magnanti, Thomas L., Mirchandani, Prakash

This paper studies a new multi-facility network synthesis problem, called the Multi-level Network Design (MLND) problem, that arises in the topological design of hierarchical communication,...

A Dual-Based Algorithm for Multi-Level Network Design (1991)

Balakrishnan, Anantaram, Magnanti, Thomas L., Mirchandani, Prakash

Given an undirected network with L possible facility types for each edge, and a partition of the nodes into L levels, the Multi-level Network Design (MLND) problem seeks a fixed cost minimizing...

A Dual-Based Algorithm for Multi-Level Network Design (1991)

Balakrishnan, Anantaram, Magnanti, Thomas L., Mirchandani, Prakash

Given an undirected network with L possible facility types for each edge, and a partition of the nodes into L levels, the Multi-level Network Design (MLND) problem seeks a fixed cost minimizing...

The Multi-Network Design Problem (1991)

Balakrishnan, Anantaram, Magnanti, Thomas L., Mirchandani, Prakash

This paper studies a new multi-facility network synthesis problem, called the Multi-level Network Design (MLND) problem, that arises in the topological design of hierarchical communication,...

Modeling and Solving the Capacitated Network Loading Problem (1991)

Magnanti, Thomas L., Mirchandani, Prakash, Vachani, Rita

This paper studies a topical and economically significant capacitated network design problem that arises in the telecommunications industry. In this problem, given point-topoint demand between...

Modeling and Solving the Capacitated Network Loading Problem (1991)

Magnanti, Thomas L., Mirchandani, Prakash, Vachani, Rita

This paper studies a topical and economically significant capacitated network design problem that arises in the telecommunications industry. In this problem, given point-topoint demand between...

Capacitated Trees, Capacitated Routing, and Associated Polyhedra (1990)

Araque, Jésus Rafael, Hall, Leslie A., Magnanti, Thomas L.

We study the polyhedral structure of two related core combinatorial problems: the subtree cardinalityconstrained minimal spanning tree problem and the identical customer vehicle routing problem. For...

Capacitated Trees, Capacitated Routing, and Associated Polyhedra (1990)

Araque, Jésus Rafael, Hall, Leslie A., Magnanti, Thomas L.

We study the polyhedral structure of two related core combinatorial problems: the subtree cardinalityconstrained minimal spanning tree problem and the identical customer vehicle routing problem. For...

The Convex Hull of Two Core Capacitated Network Design Problems (1990)

Magnanti, Thomas L., Mirchandani, Prakash, Vachani, Rita

The network loading problem (NLP) is a specialized capacitated network design problem in which prescribed point-to-point demand between various pairs of nodes of a network must be met by installing...

The Convex Hull of Two Core Capacitated Network Design Problems (1990)

Magnanti, Thomas L., Mirchandani, Prakash, Vachani, Rita

The network loading problem (NLP) is a specialized capacitated network design problem in which prescribed point-to-point demand between various pairs of nodes of a network must be met by installing...

Shortest Paths, Network Design and Associated Polyhedra (1990)

Magnanti, Thomas L., Mirchandani, Prakash

We study a specialized version of network design problems that arise in telecommunication, transportation and other industries. The problem, a generalization of the shortest path problem, is defined...

Shortest Paths, Network Design and Associated Polyhedra (1990)

Magnanti, Thomas L., Mirchandani, Prakash

We study a specialized version of network design problems that arise in telecommunication, transportation and other industries. The problem, a generalization of the shortest path problem, is defined...

Capacitated Trees, Capacitated Routing, and Associated Polyhedra (1990)

L. A. Hall, T. L. Magnanti, Leslie A. Hall, ...

We study the polyhedral structure of two related core combinatorial problems: the subtree cardinality-constrained minimal spanning tree problem and the identical customer vehicle routing problem. For...

A Polyhedral Intersection Theorem for Capacitated Spanning Trees (1989)

Hall, Leslie A., Magnanti, Thomas L.

In a two-capacitated spanning tree of a complete graph with a distinguished root vertex v, every component of the induced subgraph on V\{v} has at most two vertices. We give a complete,non-redundant...

A Polyhedral Intersection Theorem for Capacitated Spanning Trees (1989)

Hall, Leslie A., Magnanti, Thomas L.

In a two-capacitated spanning tree of a complete graph with a distinguished root vertex v, every component of the induced subgraph on V\{v} has at most two vertices. We give a complete,non-redundant...

Some Recent Advances in Network Flows (1989)

Some Recent Advances in Network Flows (1989)

The literature on network flow problems is extensive, and over the past 40 years researchers have made continuous improvements to algorithms for solving several classes of problems. However, the...

Valid inequalities and facets of the capacitated plant location problem (1989)

The literature on network flow problems is extensive, and over the past 40 years researchers have made continuous improvements to algorithms for solving several classes of problems. However, the...

Thomas L. Magnanti

Recently, several successful applications of strong cutting plane methods to combinatorial optimization problems have renewed interest in cutting plane methods, and polyhedral characterizations, of...

Not Available

Not Available

Routing in Point-to-Point Delivery Systems (1988)

Leung, Janny M. Y., Magnanti, Thomas L., Singhal, Vijay

This paper was also printed as a Working Paper at the Yale School of Organization and Management, Series B, No. 103.

Routing in Point-to-Point Delivery Systems (1988)

Leung, Janny M. Y., Magnanti, Thomas L., Singhal, Vijay

This paper was also printed as a Working Paper at the Yale School of Organization and Management, Series B, No. 103.

Network flows (1988)

Ahuja, Ravindra K., Magnanti, Thomas L., Orlin, James B.

"August 1988. Revised: December, 1988."

A Strong Cutting Plane Algorithm for Production Scheduling with Changeover Costs (1987)

Magnanti, Thomas L., Vachani, Rita

Changeover costs (and times) are central to numerous manufacturing operations. These costs arise whenever work centers capable of processing only one product at a time switch from the manufacture of...

Facets and Algorithms for Capacitated Lot Sizing (1987)

Leung, Janny M. Y., Magnanti, Thomas L., Vachani, Rita

The dynamic economic lot sizing model, which lies at the core of numerous production planning applications, is one of the most highly studied models in all of operations research. And yet,...

Facets and Algorithms for Capacitated Lot Sizing (1987)

Leung, Janny M. Y., Magnanti, Thomas L., Vachani, Rita

The dynamic economic lot sizing model, which lies at the core of numerous production planning applications, is one of the most highly studied models in all of operations research. And yet,...

A Strong Cutting Plane Algorithm for Production Scheduling with Changeover Costs (1987)

Magnanti, Thomas L., Vachani, Rita

Changeover costs (and times) are central to numerous manufacturing operations. These costs arise whenever work centers capable of processing only one product at a time switch from the manufacture of...

A Dual Ascent Procedure for Large Scale Uncapacitated Network Design (1987)

Balakrishnan, Anantaram, Magnanti, Thomas L., Wong, Richard T.

The fixed-charge network design problem arises in a variety of problem contexts including transportation, communication, and production scheduling.We develop a family of dual ascent algorithms for...

A Dual Ascent Procedure for Large Scale Uncapacitated Network Design (1987)

Balakrishnan, Anantaram, Magnanti, Thomas L., Wong, Richard T.

The fixed-charge network design problem arises in a variety of problem contexts including transportation, communication, and production scheduling.We develop a family of dual ascent algorithms for...

Designing Satellite Communication Networks by Zero-One Quadratic Programming (1987)

Helme, Marcia P., Magnanti, Thomas L.

In satellite communications networks, distinctive facilities called homing stations perform special transmission functions. Local demand nodes clustered around each homing station communicate with...

Designing Satellite Communication Networks by Zero-One Quadratic Programming (1987)

Helme, Marcia P., Magnanti, Thomas L.

In satellite communications networks, distinctive facilities called homing stations perform special transmission functions. Local demand nodes clustered around each homing station communicate with...

Routing and Scheduling on a Shoreline with Release Times (1986)

Psaraftis, Harilaos N., Solomon, Marius M., Magnanti, Thomas L., Kim, Tai-Up

In this paper we examine computational complexity issues and develop algorithms for a class of "shoreline" single-vehicle routing and scheduling problems with release time constraints. Problems in...

Routing and Scheduling on a Shoreline with Release Times (1986)

Psaraftis, Harilaos N., Solomon, Marius M., Magnanti, Thomas L., Kim, Tai-Up

In this paper we examine computational complexity issues and develop algorithms for a class of "shoreline" single-vehicle routing and scheduling problems with release time constraints. Problems in...

Valid Inequalities and Facets of the Capacitated Plant Location Problem (1986)

Leung, Janny M. Y., Magnanti, Thomas L.

Recently, several successful applications of strong cutting plane methods to combinatorial optimization problems have renewed interest in cutting plane methods, and polyhedral characterizations, of...

Valid Inequalities and Facets of the Capacitated Plant Location Problem (1986)

Leung, Janny M. Y., Magnanti, Thomas L.

Recently, several successful applications of strong cutting plane methods to combinatorial optimization problems have renewed interest in cutting plane methods, and polyhedral characterizations, of...

Parametric Linear Programming and Anti-Cycling Pivoting Rules (1985)

Parametric Linear Programming and Anti-Cycling Pivoting Rules (1985)

The traditional perturbution (or lexicographic) methods for resolving degeneracy in linear programming impose decision rules that eliminate ties in the simplex ratio rule and, therefore,restrict the...

Generalized Descent Methods for Asymmetric Systems of Equations and Variational Inequalities (1985)

The traditional perturbution (or lexicographic) methods for resolving degeneracy in linear programming impose decision rules that eliminate ties in the simplex ratio rule and, therefore,restrict the...

Hammond, Janice H., Magnanti, Thomas L.

We consider generalizations of the steepest descent algorithm for solving asymmetric systems of equations. We first show that if the system is linear and is defined by a matrix M, then the method...

Generalized Descent Methods for Asymmetric Systems of Equations and Variational Inequalities (1985)

Hammond, Janice H., Magnanti, Thomas L.

We consider generalizations of the steepest descent algorithm for solving asymmetric systems of equations. We first show that if the system is linear and is defined by a matrix M, then the method...

Location Games and Bounds for Median Problems (1985)

Extremum Properties of Hexagonal Partitioning and the Uniform Distribution in Euclidean Location (1985)

We consider a two-person zero-sum game in which the maximizer selects a point in a given bounded planar region, the minimizer selects K points in that region,.and the payoff is the distance from the...

Extremum Properties of Hexagonal Partitioning and the Uniform Distribution in Euclidean Location (1985)

Location Games and Bounds for Median Problems (1985)

A Combined Trip Generation, Trip Distribution, Modal Split and Traffic Assignment Model (1982)

We consider a two-person zero-sum game in which the maximizer selects a point in a given bounded planar region, the minimizer selects K points in that region,.and the payoff is the distance from the...

Safwat, K. N. A., Magnanti, Thomas L.

Revised and submitted to Transportation Science February 1985.

Analysis of the Uncapacitated Dynamic Lot Size Problem (1982)

Britan, Gabriel R., Magnanti, Thomas L., Yanasse, Horacio H.

In this paper we provide worst case error bounds for several heuristics for the uncapacitated dynamic lot size problem. We propose two managerially oriented procedures and show that they have a...

Analysis of the Uncapacitated Dynamic Lot Size Problem (1982)

Britan, Gabriel R., Magnanti, Thomas L., Yanasse, Horacio H.

In this paper we provide worst case error bounds for several heuristics for the uncapacitated dynamic lot size problem. We propose two managerially oriented procedures and show that they have a...

A Combined Trip Generation, Trip Distribution, Modal Split and Traffic Assignment Model (1982)

Safwat, K. N. A., Magnanti, Thomas L.

Revised and submitted to Transportation Science February 1985.

VEHICLE FLEET PLANNING: PERSPECTIVES AND PROSPECTS by (1981)

Thomas L. Magnanti

X X; tf f w r kl ng 0 a po r f 0 'S W f

Duality Based Characterizations of Efficient Facets (1979)

Accelerating Benders' Decomposition: Algorithmic Enhancements and Model Selection Criteria (1979)

Most practical applications of multicriteria decision making can be formulated in terms of efficient points determined by preference cones with polyhedral closure. Using linear approximations and...

Magnanti, Thomas L., Wong, Richard T.

Not Available

Accelerating Benders' Decomposition: Algorithmic Enhancements and Model Selection Criteria (1979)

Magnanti, Thomas L., Wong, Richard T.

Not Available

Duality Based Characterizations of Efficient Facets (1979)

Duality and Sensitivity Analysis for Fractional Programs (REVISED) (1975)

Most practical applications of multicriteria decision making can be formulated in terms of efficient points determined by preference cones with polyhedral closure. Using linear approximations and...

Duality and Sensitivity Analysis for Fractional Programs (REVISED) (1975)

In this paper, we consider algorithms, duality and sensitivity analysis for optimization problems, called fractional, whose objective function is the ratio of two real valued functions. We discuss a...

Some Abstract Pivot Algorithms (REVISED) (1974)

In this paper, we consider algorithms, duality and sensitivity analysis for optimization problems, called fractional, whose objective function is the ratio of two real valued functions. We discuss a...

Some Abstract Pivot Algorithms (REVISED) (1974)

Several problems in the theory of combinatorial geometries (or matroids) are solved by means of algorithms which involve the notion of "abstract pivots". The main example is the Edmonds-Fulkerson...

Fenchel and Lagrange Duality are Equivalent (1974)

Several problems in the theory of combinatorial geometries (or matroids) are solved by means of algorithms which involve the notion of "abstract pivots". The main example is the Edmonds-Fulkerson...

Fenchel and Lagrange Duality are Equivalent (1974)

A basic result in ordinary (Lagrange) convex programming is the saddlepoint duality theorem concerning optimization problems with convex inequalities and linear-affine equalities satisfying a Slater...

Some Abstract Pivot Algorithms (1974)

A basic result in ordinary (Lagrange) convex programming is the saddlepoint duality theorem concerning optimization problems with convex inequalities and linear-affine equalities satisfying a Slater...

Some Abstract Pivot Algorithms (1974)

Several problems in the theory of combinatorial geometries (or matroids) are solved by means of algorithms which involve the notion of "abstract pivots". The main example is the Edmonds-Fulkerson...

Generalized Linear Programming Solves the Dual (1973)

Several problems in the theory of combinatorial geometries (or matroids) are solved by means of algorithms which involve the notion of "abstract pivots". The main example is the Edmonds-Fulkerson...

Magnanti, Thomas L., Wagner, Michael H.

The generalized linear programming algorithm allows an arbitrary mathematical programming minimization problem to be analyzed as a sequence of linear programming approximations. Under fairly general...

Generalized Linear Programming Solves the Dual (1973)

Magnanti, Thomas L., Wagner, Michael H.

The generalized linear programming algorithm allows an arbitrary mathematical programming minimization problem to be analyzed as a sequence of linear programming approximations. Under fairly general...

A Linear Approximation Approach to Duality in Nonlinear Programming (1973)

A Linear Approximation Approach to Duality in Nonlinear Programming (1973)

Linear approximation and linear programming duality theory are used as unifying tools to develop saddlepoint, Fenchel and local duality theory. Among results presented is a new and elementary proof...

Complementary Bases of a Matroid (1973)

Linear approximation and linear programming duality theory are used as unifying tools to develop saddlepoint, Fenchel and local duality theory. Among results presented is a new and elementary proof...

Complementary Bases of a Matroid (1973)