bluuebunny/crossref_metadata_2025 huggingface dataset:
The Inventory Benefit of Shipment Coordination and Stock Rebalancing in a Supply Chain
Authors: Cheung Ki Ling , Lee Hau L.
Published: January 2003

In this paper, we examine two information-based supply-chain efforts that are often linked to Vendor-Managed Inventory (VMI) programs. Specifically, we consider a supplier serving multiple retailers located in a close proximity. The first effort uses information on the retailers' inventory positions to coordinate shipments from the supplier to enjoy economies of scale in shipments, such as full truckloads.The second effort uses the same information for eventual unloading of the shipments to the retailers to rebalance their stocking positions. How much benefit do we gain from such initiatives? What are the relative benefits of the two initiatives? What are the drivers of such benefits? This paper seeks answers to these questions.
Aggregate Social Discount Rate Derived from Individual Discount Rates
Authors: Reinschmidt Kenneth F.
Published: January 2003

In the economic evaluation of large public-sector projects, an aggregate social discount rate may be used in present worth comparison of alternatives. This paper uses the assumptions that individual discount rates are constant over time and approximately Normally distributed across the affected population, with mean μ and variance σ2, to derive an aggregate discount function that is exponential in form but with time-dependent aggregate discount rate ρ(t) = μ − σ2t/2, where t is the time of occurrence of the cost or benefit. This equation agrees with numerical simulations. If σ2 > 0, then the aggregate discount rate is less than the mean individual discount rate, and use of the time-dependent aggregate discount rate ρ(t) = μ − σ2t/2 instead of the constant discount factor ρ(t) = μ would result in larger discounted present values for public-sector projects for which the benefits lie far in the future. This could mean that public-sector investments that would be rejected under the assumption ρ(t) = μ might be justified using the time-dependent aggregate discount rate ρ(t) = μ − σ2t/2.
Fair Queuing and Other Probabilistic Allocation Methods
Authors: Moulin Hervé , Stong Richard
Published: January 2003

A server processes one job per unit of time and randomly schedules the jobs requested by a given set of users; each user may request a different number of jobs.

Fair queuing (Shenker 1989) schedules jobs in successive round-robin fashion, where each agent receives one unit in each round until his demand is met and the ordering is random in each round. Fair queuing*, the reverse scheduling of fair queuing, serves first (with uniform probability) one of the users with the largest remaining demand.

We characterize fair queuing* by the combination of lower composition—LC—(the scheduling sequence is history independent), demand monotonicity—DM—(increasing my demand cannot result in increased delay) and two equity axioms, equal treatment ex ante—ETEA (two identical demands give the same probability distribution of service) and equal treatment ex post—ETEP (two identical demands must be served in alternating fashion). The set of dual axioms (in which ETEA and ETEP are unchanged) characterizes fair queuing.

We also characterize the rich family of methods satisfying LC, DM, and the familiar consistency—CSY—axiom. They work by fixing a standard of comparison (preordering) between a demand of xi units by agent i and one of xj units by agent j. The first job scheduled is drawn from the agents whose demand has the highest standard.
Mean-Variance Portfolio Selection with Random Parameters in a Complete Market
Authors: Lim Andrew E. B. , Zhou Xun Yu
Published: January 2003

This paper concerns the continuous-time, mean-variance portfolio selection problem in a complete market with random interest rate, appreciation rates, and volatility coef.cients. The problem is tackled using the results of stochastic linear-quadratic (LQ) optimal control and backward stochastic differential equations (BSDEs), two theories that have been extensively studied and developed in recent years. Specifically, the mean-variance problem is formulated as a linearly constrained stochastic LQ control problem. Solvability of this LQ problem is reduced, in turn, to proving global solvability of a stochastic Riccati equation. The proof of existence and uniqueness of this Riccati equation, which is a fully nonlinear and singular BSDE with random coefficients, is interesting in its own right and relies heavily on the structural properties of the equation. Efficient investment strategies as well as the mean-variance efficient frontier are then analytically derived in terms of the solution of this equation. In particular, it is demonstrated that the efficient frontier in the mean-standard deviation diagram is still a straight line or, equivalently, risk-free investment is still possible, even when the interest rate is random. Finally, a version of the Mutual Fund Theorem is presented.
Parabolic ADI Methods for Pricing American Options on Two Stocks
Authors: Villeneuve Stephane , Zanette Antonino
Published: January 2003

We propose two numerical methods for pricing American options on two stocks based on the ADI algorithm of Peaceman and Rachford (1955). We prove the stability and convergence of these schemes and establish a comparative result.
Semismooth Matrix-Valued Functions
Authors: Sun Defeng , Sun Jie
Published: January 2003

Matrix-valued functions play an important role in the development of algorithms for semidefinite programming problems. This paper studies generalized differential properties of such functions related to nonsmooth-smoothing Newton methods. The first part of this paper discusses basic properties such as the generalized derivative, Rademacher's theorem, ℬ-derivative, directional derivative, and semismoothness. The second part shows that the matrix absolute-value function, the matrix semidefinite-projection function, and the matrix projective residual function are strongly semismooth.
Local Convergence of the Proximal Point Algorithm and Multiplier Methods Without Monotonicity
Authors: Pennanen Teemu
Published: January 2003

This paper studies the convergence of the classical proximal point algorithm without assuming monotonicity of the underlying mapping. Practical conditions are given that guarantee the local convergence of the iterates to a solution of T(x) ∋ 0, where T is an arbitrary set-valued mapping from a Hilbert space to itself. In particular, when the problem is “nonsingular” in the sense that T-1 has a Lipschitz localization around one of the solutions, local linear convergence is obtained. This kind of regularity property of variational inclusions has been extensively studied in the literature under the name of strong regularity, and it can be viewed as a natural generalization of classical constraint qualifications in nonlinear programming to more general problem classes. Combining the new convergence results with an abstract duality framework for variational inclusions, the author proves the local convergence of multiplier methods for a very general class of problems. This gives as special cases new convergence results for multiplier methods for nonmonotone variational inequalities and nonconvex nonlinear programming.
Risk-Sensitive Optimal Control for Markov Decision Processes with Monotone Cost
Authors: Borkar V. S. , Meyn S. P.
Published: January 2003

The existence of an optimal feedback law is established for the risk-sensitive optimal control problem with denumerable state space. The main assumptions imposed are irreducibility and a near monotonicity condition on the one-step cost function. A solution can be found constructively using either value iteration or policy iteration under suitable conditions on initial feedback law.
Facets of the Complementarity Knapsack Polytope
Authors: De Farias I. R. , Johnson E. L. , Nemhauser G. L.
Published: January 2003

We present a polyhedral study of the complementarity knapsack problem. Traditionally, complementarity constraints are modeled by introducing auxiliary binary variables and additional constraints, and the model is tightened by introducing strong inequalities valid for the resulting MIP. We use an alternative approach, in which we keep in the model only the continuous variables, and we tighten the model by introducing inequalities that define facets of the convex hull of the set of feasible solutions in the space of the continuous variables. To obtain the facet-defining inequalities, we extend the concepts of cover and cover inequality, commonly used in 0–1 programming, for this problem, and we show how to sequentially lift cover inequalities. We obtain tight bounds for the lifting coefficients, and we present two families of facet-de.ning inequalities that can be derived by lifting cover inequalities. We show that unlike 0–1 knapsack polytopes, in which different facet-defining inequalities can be derived by fixing variables at 0 or 1, and then sequentially lifting cover inequalities valid for the projected polytope, any sequentially lifted cover inequality for the complementarity knapsack polytope can be obtained by fixing variables at 0.
Subset Comparisons for Additive Linear Orders
Authors: Fishburn Peter C. , Pekeč Aleksandar , Reeds James A.
Published: January 2003

This paper investigates algebraic and combinatorial properties of the set of linear orders on the algebra of subsets of a finite set that are representable by positive measures. It is motivated by topics in decision theory and the theory of measurement, where an understanding of such properties can facilitate the design of strategies to elicit comparisons between subsets that, for example, determine an individual's preference order over subsets of objects or an individual's qualitative probability order over subsets of states of the world. We introduce a notion of critical pairs of binary comparisons for such orders and prove that (i) each order is uniquely characterized by its set of critical pairs and (ii) the smallest set of binary comparisons that determines an order is a subset of its set of critical pairs. The paper then focuses on the minimum number of on-line binary-comparison queries between subsets that suffice to determine any representable order for a set of given cardinality n. It is observed that, for small n, the minimum is attained by first determining the ordering of singleton subsets. We also consider query procedures with fixed numbers of stages, in each stage of which a number of queries for the next stage are formulated.
Packing Random Rectangles of Given Volume
Authors: Rhee Wansoo T.
Published: January 2003

A packing of a collection of rectangles is a disjoint subcollection. In a recent paper, Coffman et al. (1999) prove that the cardinality of a maximum packing of a family of n random rectangles in [0, 1]2 is of order n1/2. We obtain tight bounds on the same quantity when the random rectangles are of a specified volume.
A Necessary and Sufficient Condition for Approachability
Authors: Spinat Xavier
Published: January 2003

In the framework of two-person repeated games with vector payoffs, Blackwell defined the property of approachability and introduced a sufficient condition for it. He also proved that this condition is necessary in the case of convex sets.

We generalize this result: A set is approachable if and only if it contains a set that satisfies Blackwell's condition.
Optimal Offer Construction in Electricity Markets
Authors: Anderson E. J. , Philpott A. B.
Published: January 2003

In this paper we study strategies for generators making offers into electricity markets in circumstances where both the demand for electricity and the behaviour of competing generators is unknown but can be represented by a probability distribution. Given this probability distribution, we derive necessary optimality conditions for a broad class of supply offer curves. We show how these conditions can be used to construct an optimal solution for a simple example. We also consider the case in which a generator is restricted in the number of prices at which power can be offered.
Approximating Martingales for Variance Reduction in Markov Process Simulation
Authors: Henderson Shane G. , Glynn Peter W.
Published: January 2003

“Knowledge of either analytical or numerical approximations should enable more efficient simulation estimators to be constructed.” This principle seems intuitively plausible and certainly attractive, yet no completely satisfactory general methodology has been developed to exploit it. The authors present a new approach for obtaining variance reduction in Markov process simulation that is applicable to a vast array of different performance measures. The approach relies on the construction of a martingale that is then used as an internal control variate.
On Deciding Stability of Constrained Homogeneous Random Walks and Queueing Systems
Authors: Gamarnik David
Published: January 2003

We investigate stability of scheduling policies in queueing systems. To this day no algorithmic characterization exists for checking stability of a given policy in a given queueing system. In this paper we introduce a certain generalized priority policy and prove that the stability of this policy is algorithmically undecidable. We also prove that stability of a homogeneous random walk in 𝒵d+ is undecidable. Finally, we show that the problem of computing a fluid limit of a queueing system or of a constrained homogeneous random walk is undecidable. To the best of our knowledge these are the first undecidability results in the area of stability of queueing systems and random walks in 𝒵d+. We conjecture that stability of common policies like First-In-First-Out and priority policy is also an undecidable problem.
Q-Learning for Risk-Sensitive Control
Authors: Borkar V. S.
Published: January 2003

We propose for risk-sensitive control of finite Markov chains a counterpart of the popular Q-learning algorithm for classical Markov decision processes. The algorithm is shown to converge with probability one to the desired solution. The proof technique is an adaptation of the o.d.e. approach for the analysis of stochastic approximation algorithms, with most of the work involved used for the analysis of the specific o.d.e.s that arise.
A Combinatorial, Graph-Based Solution Method for a Class of Continuous-Time Optimal Control Problems
Authors: Khmelnitsky Eugene
Published: January 2003

The paper addresses a class of continuous-time, optimal control problems whose solutions are typically characterized by both bang-bang and "singular" control regimes. Analytical study and numerical computation of such solutions are very difficult and far from complete when only techniques from control theory are used. This paper solves optimal control problems by reducing them to the combinatorial search for the shortest path in a specially constructed graph. Since the nodes of the graph are weighted in a sequence-dependent manner, we extend the classical, shortest-path algorithm to our case. The proposed solution method is currently limited to single-state problems with multiple control functions. A production planning problem and a train operation problem are optimally solved to illustrate the method.
Relationship Between Strong Monotonicity Property, P2-Property, and the Gus-Property in Semidefinite Linear Complementarity Problems
Authors: Parthasarathy T. , Raman D. Sampangi , Sriparna B.
Published: January 2003

In a recent paper on semidefinite linear complementarity problems, Gowda and Song (2000) introduced and studied the P-property, P2-property, GUS-property, and strong monotonicity property for linear transformation L: Sn → Sn, where Sn is the space of all symmetric and real n × n matrices. In an attempt to characterize the P2-property, they raised the following two questions: (i) Does the strong monotonicity imply the P2-property? (ii) Does the GUS-property imply the P2-property? In this paper, we show that the strong monotonicity property implies the P2-property for any linear transformation and describe an equivalence between these two properties for Lyapunov and other transformations. We show by means of an example that the GUS-property need not imply the P2-property, even for Lyapunov transformations.
An Analytic Center Cutting Plane Method for Semidefinite Feasibility Problems
Authors: Sun Jie , Toh Kim-Chuan , Zhao Gongyun
Published: January 2003

Semidefinite feasibility problems arise in many areas of operations research. The abstract form of these problems can be described as finding a point in a nonempty bounded convex body Γ in the cone of symmetric positive semidefinite matrices. Assume that Γ is defined by an oracle, which for any given m × m symmetric positive semidefinite matrix Ŷ either confirms that Ŷ ∈ Γ or returns a cut, i.e., a symmetric matrix A such that Γ is in the half-space {Y : A · Y ≤ A · Ŷ}. We study an analytic center cutting plane algorithm for this problem. At each iteration, the algorithm computes an approximate analytic center of a working set defined by the cutting plane system generated in the previous iterations. If this approximate analytic center is a solution, then the algorithm terminates; otherwise the new cutting plane returned by the oracle is added into the system. As the number of iterations increases, the working set shrinks and the algorithm eventually finds a solution to the problem. All iterates generated by the algorithm are positive definite matrices. The algorithm has a worst-case complexity of O*(m3/ε2) on the total number of cuts to be used, where ε is the maximum radius of a ball contained by Γ.
Semidefinite Programming vs. LP Relaxations for Polynomial Programming
Authors: Lasserre Jean B.
Published: January 2003

We consider the global minimization of a multivariate polynomial on a semi-algebraic set Ω defined with polynomial inequalities. We then compare two hierarchies of relaxations, namely, LP relaxations based on products of the original constraints, in the spirit of the RLT procedure of Sherali and Adams (1990), and recent semidefinite programming (SDP) relaxations introduced by the author. The comparison is analyzed in light of recent results in real algebraic geometry on various representations of polynomials, positive on a compact semi-algebraic set.
Node-Capacitated Ring Routing
Authors: Frank András , Shepherd Bruce , Tandon Vivek , Végh Zoltán
Published: January 2003

We consider the node-capacitated routing problem in an undirected ring network along with its fractional relaxation, the node-capacitated multicommodity flow problem. For the feasibility problem, Farkas' lemma provides a characterization for general undirected graphs, asserting roughly that there exists such a flow if and only if the so-called distance inequality holds for every choice of distance functions arising from nonnegative node weights. For rings, this (straightforward) result will be improved in two ways. We prove that, independent of the integrality of node capacities, it suffices to require the distance inequality only for distances arising from (0-1-2)-valued node weights, a requirement that will be called the double-cut condition. Moreover, for integer-valued node capacities, the double-cut condition implies the existence of a half-integral multicommodity flow. In this case there is even an integer-valued multicommodity flow that violates each node capacity by at most one.

Our approach gives rise to a combinatorial, strongly polynomial algorithm to compute either a violating double-cut or a node-capacitated multicommodity flow. A relation of the problem to its edge-capacitated counterpart will also be explained.
Computing Stationary Nash Equilibria of Undiscounted Single-Controller Stochastic Games
Authors: Raghavan T. E. S. , Syed Zamir
Published: January 2003

Given a two-person, nonzero-sum stochastic game where the second player controls the transitions, we formulate a linear complementarity problem LCP(q, M) whose solution gives a Nash equilibrium pair of stationary strategies under the limiting average payoff criterion. The matrix M constructed is of the copositive class so that Lemke's algorithm will process it. We will also do the same for a special class of N-person stochastic games called polymatrix stochastic games.
A Polynomial Combinatorial Algorithm for Generalized Minimum Cost Flow
Authors: Wayne Kevin D.
Published: January 2003

We propose the first combinatorial solution to the generalized minimum cost flow problem (flow with losses and gains). Despite a rich history dating back to Kantorovich and Dantzig, until now, the only known way to solve the problem in polynomial-time was via general-purpose linear programming techniques. Polynomial combinatorial algorithms were previously known only for the version of our problem without costs. We design the first such algorithms for the version with costs. Our algorithms also find provably good solutions faster than optimal ones, providing the first strongly polynomial approximation schemes for the problem.

Our techniques extend to optimize linear programs with two variables per inequality. Polynomial combinatorial algorithms were previously developed for testing the feasibility of such linear programs. We propose the first such methods for the optimization version.
A Generalization of the Perfect Graph Theorem Under the Disjunctive Index
Authors: Aguilera Néstor E. , Escalante Mariana S. , Nasini Graciela L.
Published: January 2003

In this paper, we relate antiblocker duality between polyhedra, graph theory, and the disjunctive procedure. In particular, we analyze the behavior of the disjunctive procedure over the clique relaxation, 𝒦(G), of the stable set polytope in a graph G, and the one associated to its complementary graph, 𝒦(Ḡ). We obtain a generalization of the Perfect Graph Theorem, proving that the disjunctive indices of 𝒦(G) and 𝒦(Ḡ) always coincide.
Combining Problem Structure with Basis Reduction to Solve a Class of Hard Integer Programs
Authors: Louveaux Quentin , Wolsey Laurence A.
Published: January 2003

Recently Aardal et al. (2000) have successfully solved some small, difficult, equality-constrained integer programs by using basis reduction to reformulate the problems as inequality-constrained integer programs in a different space. Here, we adapt their method to solve integer programs that are larger but have special structure. The practical problem motivating this work is a variant of the market share problem. More formally, the problem can be viewed as finding a matrix X ∈ ℤmn+ satisfying XA = C, BX = D, where A, B, C, D are matrices of compatible dimensions, and the approach requires us to find a reduced basis of the lattice ℒ = {X ∈ ℤm×n: XA = 0, BX = 0}.

The main topic of this paper is a study of the lattice ℒ. It is shown that an integer basis of ℒ can be obtained by taking the Kronecker product of vectors from integer bases of two much smaller lattices. Furthermore, the resulting basis is a reduced basis if the integer bases of the two small lattices are reduced bases and a suitable ordering is chosen.

Finally, some limited computational results are presented showing the benefits of making use of the problem structure.
The Stable Allocation (or Ordinal Transportation) Problem
Authors: Baïou Mourad , Balinski Michel
Published: January 2003

The stable allocation problem generalizes the 0,1 stable matching problems (one-to-one, one-to-many, and many-to-many) to the allocation of real valued hours or quantities. A strongly polynomial algorithm proves the existence of “stable allocations.”

The set of stable allocations is shown to be a distributive lattice in general, but in the “nondegenerate” case it is a complete linear order. Indeed, in the generic case, when a problem is “strongly nondegenerate,” there exists a single stable allocation.

A simple algorithm finds “row-optimal” and “column-optimal” stable allocations, given any stable allocation. When a problem is nondegenerate it finds all stable allocations.
Project Scheduling in AND–OR Graphs: A Generalization of Dijkstra's Algorithm
Authors: Adelson-Velsky George M. , Levner Eugene
Published: January 2003

The paper considers a project scheduling problem in weighted directed graphs in which arcs represent operations while nodes are identified with starting and finishing endpoints of the operations; arc lengths represent operation durations. The graphs have two types of nodes—AND-nodes and OR-nodes. The problem is to find the earliest starting times for all operations. This problem generalizes the shortest path problem and the critical path problem. The complexity of the suggested algorithm is O(p′ p) where p′ is the number of arcs entering the AND-nodes and p is the total number of arcs.
Minimizing Service and Operation Costs of Periodic Scheduling
Authors: Bar-Noy Amotz , Bhatia Randeep , Naor Joseph (Seffi) , Schieber Baruch
Published: January 2003

We study the problem of scheduling activities of several types under the constraint that, at most, a fixed number of activities can be scheduled in any single time slot. Any given activity type is associated with a service cost and an operating cost that increases linearly with the number of time slots since the last service of this type. The problem is to find an optimal schedule that minimizes the long-run average cost per time slot. Applications of such a model are the scheduling of maintenance service to machines, multi-item replenishment of stock, and minimizing the mean response time in Broadcast Disks. Broadcast Disks recently gained a lot of attention because they were used to model backbone communications in wireless systems, Teletext systems, and Web caching in satellite systems.

The first contribution of this paper is the definition of a general model that combines into one several important previous models. We prove that an optimal cyclic schedule for the general problem exists, and we establish the NP-hardness of the problem. Next, we formulate a nonlinear program that relaxes the optimal schedule and serves as a lower bound on the cost of an optimal schedule. We present an efficient algorithm for finding a near-optimal solution to the nonlinear program. We use this solution to obtain several approximation algorithms.

(1) A 9/8 approximation for a variant of the problem that models the Broadcast Disks application. The algorithm uses some properties of “Fibonacci sequences.” Using this sequence, we present a 1.57-approximation algorithm for the general problem.

(2) A simple randomized algorithm and a simple deterministic greedy algorithm for the problem. We prove that both achieve approximation factor of 2. To the best of our knowledge this is the first worst-case analysis of a widely used greedy heuristic for this problem.
Approximating Subdifferentials by Random Sampling of Gradients
Authors: Burke J. V. , Lewis A. S. , Overton M. L.
Published: January 2003

Many interesting real functions on Euclidean space are differentiable almost everywhere. All Lipschitz functions have this property, but so, for example, does the spectral abscissa of a matrix (a non-Lipschitz function). In practice, the gradient is often easy to compute. We investigate to what extent we can approximate the Clarke subdifferential of such a function at some point by calculating the convex hull of some gradients sampled at random nearby points.
Computing Equilibria in Finance Economies
Authors: Herings P. Jean-Jacques , Kubler Felix
Published: January 2003

The general equilibrium model with incomplete asset markets is ideally suited for the study of problems in cross-sectional asset pricing and portfolio theory. In this paper, we develop a homotopy algorithm to approximate equilibria in these models. Since the algorithm is tailor made for so-called finance economies, the number of nonlinear equations that has to be solved for, and therefore the computing time, is an order of magnitude smaller than that of existing general-purpose algorithms. The algorithm is shown to be generically convergent. We implement the algorithm using HOMPACK. To illustrate its performance, we present various numerical examples and report running times.
Cost Allocation for a Tree Network with Heterogeneous Customers
Authors: Granot Daniel , Kuipers Jeroen , Chopra Sunil
Published: January 2003

We analyze a cost allocation problem which could naturally arise from a situation wherein a tree network T = (N ∪ {0}, E), serving heterogeneous customers, has to be constructed. The customers, located at N, require some service from a central supplier, located at vertex 0. The customers have heterogeneous preferences for the level or quality of service received from the central supplier.

We formulate the above cost allocation problem as a cooperative game, referred to as an extended tree game. The extended tree game is a proper extension of Megiddo's (1978) tree game, wherein all the customers have identical preferences regarding the level of service received. We prove that an extended tree game is convex, and we show that its Shapley value can be computed in 𝒪(p|N|) time, where p is the number of distinct preference levels. We further provide a complete facial description of the core polytope of an extended tree game, and demonstrate that even when there are only two classes of customers, the number of nonredundant core constraints could be exponential in |N|. Nevertheless, we are able to construct an 𝒪(p|N|) algorithm to check the core membership of an arbitrary cost allocation, which can be used to construct an 𝒪(p|N|3) combinatorial algorithm to compute the nucleolus of an extended tree game. Finally, we show that the complements of the facet-defining coalitions for the core are all connected in an auxiliary tree graph with node set N.
Erratum: The Stable Allocation (or Ordinal Transportation) Problem
Authors: Baïou Mourad , Balinski Michel
Published: January 2003

An incorrect version of this paper was printed in Mathematics of Operations Research, Vol. 27, No. 3, August 2002, pp. 485–503 . The paper is reprinted correctly below.

The stable allocation problem generalizes the 0,1 stable matching problems (one-to-one, one-to-many, and many-to-many) to the allocation of real valued hours or quantities. A strongly polynomial algorithm proves the existence of “stable allocations.”

The set of stable allocations is shown to be a distributive lattice in general, but in the “nondegenerate” case it is a complete linear order. Indeed, in the generic case, when a problem is “strongly nondegenerate,” there exists a single stable allocation.

A simple algorithm finds “row-optimal” and ”column-optimal” stable allocations, given any stable allocation. When a problem is nondegenerate it finds all stable allocations.
The Complexity of Generic Primal Algorithms for Solving General Integer Programs
Authors: Schulz Andreas S. , Weismantel Robert
Published: January 2003

Primal methods constitute a common approach to solving (combinatorial) optimization problems. Starting from a given feasible solution, they successively produce new feasible solutions with increasingly better objective function value until an optimal solution is reached. From an abstract point of view, an augmentation problem is solved in each iteration. That is, given a feasible point, these methods find an augmenting vector, if one exists. Usually, augmenting vectors with certain properties are sought to guarantee the polynomial running time of the overall algorithm.

In this paper, we show that one can solve every integer programming problem in polynomial time provided one can efficiently solve the directed augmentation problem. The directed augmentation problem arises from the ordinary augmentation problem by splitting each direction into its positive and its negative part and by considering linear objectives on these parts. Our main result states that in order to get a polynomial-time algorithm for optimization it is sufficient to efficiently find, for any linear objective function in the positive and negative part, an arbitrary augmenting vector.

This result also provides a general framework for the design of polynomial-time algorithms for specific combinatorial optimization problems. We demonstrate its applicability by considering the min-cost flow problem, by giving a novel algorithm for linear programming over unimodular spaces, and by providing a different proof that for 0/1-integer programming an efficient algorithm solving the ordinary augmentation problem suffices for efficient optimization. Our main result also implies that directed augmentation is at least as hard as optimization. In other words, for an NP-hard problem already the task of finding a directed augmenting vector in polynomial time is hopeless, unless P = NP. We illustrate this kind of consequence with the help of the knapsack problem.
Integral Polyhedra Related to Even-Cycle and Even-Cut Matroids
Authors: Guenin Bertrand
Published: January 2003

A family of sets ℋ is ideal if the polyhedron {x ≥ 0 : Σi∈Sxi ≥ 1, ∀S ∈ ℋ} is integral. Consider a graph G with vertices s, t. An odd st-walk is either an odd st-path or the union of an even st-path and an odd circuit that share, at most, one vertex. Let T be a subset of vertices of even cardinality. An st-T-cut is a cut of the form δ(U) where |U ∩ T| is odd and U contains exactly one of s or t. We give excluded minor characterizations for when the families of odd st-walks and st-T-cuts (represented as sets of edges) are ideal. As a corollary, we characterize which extensions and coextensions of graphic and cographic matroids are 1-flowing.
A Polyhedral Study of Integer Variable Upper Bounds
Authors: Klabjan Diego , Nemhauser George L.
Published: January 2003

We study the polyhedron of the single node capacitated network design model with integer variable upper bounds. We first give a characterization of valid inequalities that is useful in proving the validity of several classes of inequalities. Next we derive several classes of valid inequalities and we give conditions for them to be facet-defining. Sequence independent lifting is used to obtain additional facets. We conclude by reporting computational results with a branch-and-cut algorithm.
A Note on Clique-Web Facets for Multicut Polytopes
Authors: Sørensen Michael M.
Published: January 2003

In this note we provide a previously undiscovered necessary condition for the facet-defining property of clique-web inequalities for the multicut polytope. This condition imposes a minimum cardinality requirement on the node set of the clique, thus implying, in general, that clique-web inequalities associated with relatively small cliques are not facet-defining for multicut polytopes.
A Superlinearly Convergent Algorithm for the Monotone Nonlinear Complementarity Problem Without Uniqueness and Nondegeneracy Conditions
Authors: Dan Hiroshige , Yamashita Nobuo , Fukushima Masao
Published: January 2003

The purpose of this paper is to present an algorithm for solving the monotone nonlinear complementarity problem (NCP) that enjoys superlinear convergence in a genuine sense without the uniqueness and nondegeneracy conditions. Recently, Yamashita and Fukushima (2001) proposed a method based on the proximal point algorithm (PPA) for monotone NCP. The method has the favorable property that a generated sequence converges to the solution set of NCP superlinearly. However, when a generated sequence converges to a degenerate solution, the subproblems may become computationally expensive and the method does not have genuine superlinear convergence. More recently, Yamashita et al. (2001) presented a technique to identify whether a solution is degenerate or not. Using this technique, we construct a differentiable system of nonlinear equations in which the solution is a solution of the original NCP. Moreover, we propose a hybrid algorithm that is based on the PPA and uses this system. We show that the proposed algorithm has a genuine quadratic or superlinear rate of convergence even if it converges to a solution that is neither unique nor nondegenerate.
Stability in the Discretization of a Parametric Semi-Infinite Convex Inequality System
Authors: Cánovas María J. , López Marco A. , Parra Juan
Published: January 2003

In this paper, we consider a parametric family of convex inequality systems in the Euclidean space, with an arbitrary infinite index set, T, and convex constraints depending continuously on a parameter ranging in a separable metric space. No structure is assumed for T, and so the dependence of the constraints on the index has no particular property. In this context, the possibility of approaching the nominal system by means of sequences of finite subsystems associated to proximal parameters is analyzed. This possibility, of combining both approximation and discretization techniques, is formalized in terms of the lower semicontinuity of the feasible set mapping depending on a double parameter: The original one and the finite subset of indices (grid) itself. The paper characterizes this property in terms of the lower semicontiuity of the feasible set mapping depending only on the original parameter (and considering, then, all the constraints). Since in any approximation process we consider, as a last resort, a countable amount of constraints, the first step in this work consists of justifying the possibility of considering, without loss of generality, ℕ (set of all natural numbers) as the proper index set. Moreover, in order to be able to consider any subset of indices as a new parameter, a suitable metric is introduced in the set of all the nonempty subsets of ℕ, entailing desirable properties in relation to approximation strategies.
The Zero Duality Gap Property and Lower Semicontinuity of the Perturbation Function
Authors: Rubinov A. M. , Huang X. X. , Yang X. Q.
Published: January 2003

We examine the validity of the zero duality gap properties for two important dual schemes: a generalized augmented Lagrangian dual scheme and a nonlinear Lagrange-type dual scheme. The necessary and sufficient conditions for the zero duality gap property to hold are established in terms of the lower semicontinuity of the perturbation functions.
Quantitative Stability in Stochastic Programming: The Method of Probability Metrics
Authors: Rachev Svetlozar T. , Römisch Werner
Published: January 2003

Quantitative stability of optimal values and solution sets to stochastic programming problems is studied when the underlying probability distribution varies in some metric space of probability measures. We give conditions that imply that a stochastic program behaves stable with respect to a minimal information (m.i.) probability metric that is naturally associated with the data of the program. Canonical metrics bounding the m.i. metric are derived for specific models, namely for linear two-stage, mixed-integer two-stage and chance-constrained models. The corresponding quantitative stability results as well as some consequences for asymptotic properties of empirical approximations extend earlier results in this direction. In particular, rates of convergence in probability are derived under metric entropy conditions. Finally, we study stability properties of stable investment portfolios having minimal risk with respect to the spectral measure and stability index of the underlying stable probability distribution.
The Complexity of Decentralized Control of Markov Decision Processes
Authors: Bernstein Daniel S. , Givan Robert , Immerman Neil , Zilberstein Shlomo
Published: January 2003

We consider decentralized control of Markov decision processes and give complexity bounds on the worst-case running time for algorithms that find optimal solutions. Generalizations of both the fully observable case and the partially observable case that allow for decentralized control are described. For even two agents, the finite-horizon problems corresponding to both of these models are hard for nondeterministic exponential time. These complexity results illustrate a fundamental difference between centralized and decentralized control of Markov decision processes. In contrast to the problems involving centralized control, the problems we consider provably do not admit polynomial-time algorithms. Furthermore, assuming EXP ≠ NEXP, the problems require superexponential time to solve in the worst case.
The Circuit-Switched Network Design and Analysis Model: A Chronology of Its Development and Use
Authors: Barker Harry G. , Calabrese David A. , Fischer Martin J. , Garbin David A. , Knepley J. Edward , Swinsky Gregor W.
Published: January 2003

The Defense Information System Agency (DISA) has managerial and engineering responsibility for a circuit-switched network currently known as the Defense Information System Network—Voice. This network was originally implemented in the 1960s and was known as the Automatic Voice Network. Throughout this time, DISA has used a network design and analysis model to reconfigure the network. This model was developed in the early 1970s, has been continually enhanced, and is used on a weekly basis to engineer and manage the network. Since 1975, it has been used to save the United States (U.S.) government approximately $1,400,000,000.00. In this paper, we present a chronology of its development, enhancement, and use.
Rendezvous Search: A Personal Perspective
Authors: Alpern Steve
Published: January 2003

The rendezvous-search problem was posed by the author 25 years ago. In its basic form, it asks how two unit speed players can find each other in least expected time, when randomly placed in a known dark region. The problem received little attention until about 10 years ago. This article surveys the rapid progress that has been made since then, and also presents some new results.
On the Value of Binary Expansions for General Mixed-Integer Linear Programs
Authors: Owen Jonathan H. , Mehrotra Sanjay
Published: January 2003

We study the use of binary variables in reformulating general mixed-integer linear programs. We show that binary reformulations result in problems for which almost all the binary variables replacing a general integer variable need to be explored during branching. We also give computational results on the performance of such reformulations in solving the mixed-integer programs, which support our theoretical results.
Chessboard Distributions and Random Vectors with Specified Marginals and Covariance Matrix
Authors: Ghosh Soumyadip , Henderson Shane G.
Published: January 2003

There is a growing need for the ability to specify and generate correlated random variables as primitive inputs to stochastic models.Moti vated by this need, several authors have explored the generation of random vectors with specified marginals, together with a specified covariance matrix, through the use of a transformation of a multivariate normal random vector (the NORTA method).

A covariance matrix is said to be feasible for a given set of marginal distributions if a random vector exists with these characteristics. We develop a computational approach for establishing whether a given covariance matrix is feasible for a given set of marginals. The approach is used to rigorously establish that there are sets of marginals with feasible covariance matrix that the NORTA method cannot match. In such cases, we show how to modify the initialization phase of NORTA so that it will exactly match the marginals, and approximately match the desired covariance matrix.

An important feature of our analysis is that we show that for almost any covariance matrix (in a certain precise sense), our computational procedure either explicitly provides a construction of a random vector with the required properties, or establishes that no such random vector exists.
Exotic Options for Interruptible Electricity Supply Contracts
Authors: Kamat Rajnish , Oren Shmuel S.
Published: January 2003

This paper presents the design and pricing of financial contracts for the supply and procurement of interruptible electricity service. While the contract forms and pricing methodology have broader applications, the focus of this work is on electricity market applications, which motivate the contract structures and price process assumptions. In particular, we propose a new contract form that bundles simple forwards with exotic call options that have two exercise points with different strike prices. Such options allow hedging and valuation of supply curtailment risk, while explicitly accounting for the notification lead time before curtailment.

The proposed instruments are priced under the traditional GBM price process assumption and under the more realistic assumption (for electricity markets) of a mean reverting price process with jumps. The latter results employ state-of-the-art Fourier transforms techniques.
Modeling and Solving the Train Timetabling Problem
Authors: Caprara Alberto , Fischetti Matteo , Toth Paolo
Published: January 2003

The train timetabling problem aims at determining a periodic timetable for a set of trains that does not violate track capacities and satisfies some operational constraints. In particular, we concentrate on the problem of a single, one-way track linking two major stations, with a number of intermediate stations in between. Each train connects two given stations along the track (possibly different from the two major stations) and may have to stop for a minimum time in some of the intermediate stations. Trains can overtake each other only in correspondence of an intermediate station, and a minimum time interval between two consecutive departures and arrivals of trains in each station is specified.

In this paper, we propose a graph theoretic formulation for the problem using a directed multigraph in which nodes correspond to departures/arrivals at a certain station at a given time instant. This formulation is used to derive an integer linear programming model that is relaxed in a Lagrangian way. A novel feature of our model is that the variables in the relaxed constraints are associated only with nodes (as opposed to arcs) of the aforementioned graph. This allows a considerable speed-up in the solution of the relaxation. The relaxation is embedded within a heuristic algorithm which makes extensive use of the dual information associated with the Lagrangian multipliers. We report extensive computational results on real-world instances provided from Ferrovie dello Stato SpA, the Italian railway company, and from Ansaldo Segnalamento Ferroviario SpA.
A Multilevel Approach to the Travelling Salesman Problem
Authors: Walshaw Chris
Published: January 2003

We motivate, derive, and implement a multilevel approach to the travelling salesman problem. The resulting algorithm progressively coarsens the problem, initialises a tour, and then employs either the Lin-Kernighan (LK) or the Chained Lin-Kernighan (CLK) algorithm to refine the solution on each of the coarsened problems in reverse order. In experiments on a well-established test suite of 80 problem instances we found multilevel configurations that either improved the tour quality by over 25% as compared to the standard CLK algorithm using the same amount of execution time, or that achieved approximately the same tour quality over seven times more rapidly. Moreover, the multilevel variants seem to optimise far better the more clustered instances with which the LK and CLK algorithms have the most difficulties.