Search

We give counterexamples for some statements of Borwein and sufficient conditions for the validity of these. [ABSTRACT FROM AUTHOR]

This paper presents a class of utility functions (class A[sub ∞]) that contains all of the utility functions commonly used for mathematical modeling: the class consisting of those utility functions whose derivatives alternate in sign. A simple representation via mixtures of exponential utilities is provided for this class which is both mathematically convenient and conducive to functional operations. A connection with Laplace transforms and the resultant implications for preference relations, aggregation and utility assessment are discussed. [ABSTRACT FROM AUTHOR]

This paper is concerned with a linear fractional problem of the form: max[sub x] min[sub y] F(X, Y) = (cX + dY + α)/(fX + gY + β), subject to AX + BY less than or equal to b; X, Y greater than or equal to O. This problem represents a generalization of a problem considered in the literature in which F(X, Y) is assumed to be linear. A number of results for the linear case are extended; and, in particular, it is shown that this fractional max-min problem is equivalent to a quasi-convex programming problem whose optimal solution lies at a vertex of the feasible region. Using these results, we develop an algorithm for solving this problem. The paper concludes with a numerical example. [ABSTRACT FROM AUTHOR]

Initially popularized by Amazon.com, recommendation technologies have become widespread over the past several years. However, the types of recommendations available to the users in these recommender systems are typically determined by the vendor and therefore are not flexible. In this paper, we address this problem by presenting the recommendation query language REQUEST that allows users to customize recommendations by formulating them in the ways satisfying personalized needs of the users. REQUEST is based on the multidimensional model of recommender systems that supports additional contextual dimensions besides traditional User and Item dimensions and also OLAP-type aggregation and filtering capabilities. This paper also presents the recommendation algebra RA, shows how REQUEST recommendations can be mapped into this algebra, and analyzes the expressive power of the query language and the algebra. This paper also shows how users can customize their recommendations using REQUEST queries through a series of examples. [ABSTRACT FROM AUTHOR]

Consider a system with N processors and two job types with one having preemptive priority over the other. Arrivals are Poisson and service times are exponential. We present two approaches for modeling the system. The difference between the two lies in the order with which we list the numbers of jobs of each type in the system in the state definition. Although both approaches yield matrix-geometric solutions, their implications for computation are significantly different. The first approach has attractive structural properties and an easily solvable rate matrix, but the system of equations at the boundary is most often prohibitively large. The second approach, while not amenable to any easy computation of its rate matrix, renders itself to an efficient solution at the boundary, and provides a basis for waiting time analysis for low priority jobs. In the paper, we present an efficient implementation of state reduction for solving the stationary probabilities associated with the boundary states. We give a numerical example to highlight various issues in the computer solution. [ABSTRACT FROM AUTHOR]

This paper presents a new framework for handling ill-structured decision problems. The framework derives from recent developments in the logic of argumentation. It shows how policy statements may under certain conditions be construed as the outcome of a complex process of argumentation. The framework is especially suited to ill-structured decision problems since it is capable of handling explicit contradictions and missing parts in an argument structure. It is also shown by means of a new concept -- plausibility -- how it is possible to locate the weakest links in a complex argument. A major consequence of the concept of plausibility is that it is possible under certain conditions to transform a problem in the logic of argumentation (i.e., symbolic logic) into one of algebra (i.e., linear programming). [ABSTRACT FROM AUTHOR]

This paper proves two properties of maximal network flows: (1) If there exist a maximal network flow with a given departure pattern at the sources and a maximal flow with a given arrival pattern at the sinks, then there exists a flow that has both this departure pattern at the sources nd this arrival pattern at the sinks. (2) There exists a maximal dynamic network flow that simultaneously has a latest (earliest) departure schedule at the sources and an earliest (latest) arrival schedule at the sinks. The paper modifies FORD AND FULKERSON'S maximal dynamic flow algorithm to construct a maximal dynamic network flow with a latest departure schedule and an earnest arrival schedule. [ABSTRACT FROM AUTHOR]

Certain jobs in large projects do not have a unique 'location' in the critical-path network; they may be moved into certain slack intervals, for example, or may even be divisible into smaller subtasks, and 'tucked in' at several locations. A previous paper gave an analysis of a model in which a single job can be divided up in any manner among an arbitrary number of locations; the resulting algorithm was of the optimal-network-flow type, which can be simply and efficiently solved using available computer codes. The first part of the present paper extends this model to multiple jobs of divisible type. The general approach is via the decomposition method of linear programming; however, the resulting algorithm is again fairly simple. Optimal cost-time solutions, possibly infinite (or optimal network flow solutions, possibly infeasible) are generated by known algorithms. The resulting schedules or cuts are then combined in a simple, special structure linear program whose dimensionality is equal to the number of divisible groups. Bounds on the nonintegrality of the final allocations can also be determined. When these special jobs can only be moved about the network in their entirety, or in certain indivisible modules, the problem takes on the form of an integer program. The second part of the paper gives a branch-and-bound procedure for the problem of movable activities, together with efficient heuristics for arbitrating and bounding these locations, using only the ordinary critical-path algorithm. Examples are given for both models. [ABSTRACT FROM AUTHOR]

This paper introduces a generalization of the frequently discussed problem of finding the optimum redundancy that maximizes the reliability of a network of components. Past work has restricted consideration to arrangements of redundant components called series-parallel networks. This paper allows a much broader class of arrangements called series-parallelseries networks. It is important to consider such arrangements for realistic situations in which components have more than one failure mode, or the combination of parallel paths introduces a failure probability. A dynamic programming algorithm is used to solve the more general problem for the case in which there are no constraints on the optimum solution. The algorithm is extended to handle multiple constraints using dominance and a variety of elimination methods to reduce the storage required in a compurer implementation of the algorithm. Problems with as many as 15 serial components and three constraints have been solved with reasonable digital computer computation times. [ABSTRACT FROM AUTHOR]

This paper gives general conditions for the convergence of a class of cutting-plane algorithms without requiring that the constraint sets for the subproblems be sequentially nested. Conditions are given under which inactive constraints may be dropped after each subproblem. Procedures for generating cutting-planes include those of KELLEY, CHENEY AND GOLDSTEIN, and a generalization of the one used by both ZOUTENDIJK and VEXNoTT. For algorithms with nested constraint sets, these conditions reduce to a special case of those of ZANGWILL for such problems and include as special cases the algorithms of Kelley, Cheney and Goldstein, and Veinott. Finally, the paper gives an arithmetic convergence rate. [ABSTRACT FROM AUTHOR]

The pickup and delivery problem with time windows (PDPTW) is a generalization of the vehicle routing problem with time windows. In the PDPTW, a set of identical vehicles located at a central depot must be optimally routed to service a set of transportation requests subject to capacity, time window, pairing, and precedence constraints. In this paper, we present a new exact algorithm for the PDPTW based on a set-partitioning-like integer formulation, and we describe a bounding procedure that finds a near-optimal dual solution of the LP-relaxation of the formulation by combining two dual ascent heuristics and a cut-and-column generation procedure. The final dual solution is used to generate a reduced problem containing only the routes whose reduced costs are smaller than the gap between a known upper bound and the lower bound achieved. If the resulting problem has moderate size, it is solved by an integer programming solver; otherwise, a branch-and-cut-and-price algorithm is used to close the integrality gap. Extensive computational results over the main instances from the literature show the effectiveness of the proposed exact method. [ABSTRACT FROM AUTHOR]

Multiplicity of equilibria is a prevalent problem in many economic models. Often equilibria are characterized as solutions to a system of polynomial equations. This paper gives an introduction to the application of Gröbner bases for finding all solutions of a polynomial system. The Shape Lemma, a key result from algebraic geometry, states under mild assumptions that a given equilibrium system has the same solution set as a much simpler triangular system. Essentially, the computation of all solutions then reduces to finding all roots of a single polynomial in a single unknown. The software package Singular computes the equivalent simple system. If all coefficients in the original equilibrium equations are rational numbers or parameters, then the Gröbner basis computations of Singular are exact. Thus, Gröbner basis methods cannot only be used for a numerical approximation of equilibria, but in fact may allow the proof of theoretical results for the underlying economic model. Three economic applications illustrate that without much prior knowledge of algebraic geometry, Gröbner basis methods can be easily applied to gain interesting insights into many modern economic models. [ABSTRACT FROM AUTHOR]

In this paper we present a polynomial-time procedure to find a low-rank solution for a system of linear matrix inequalities (LMI). The existence of such a low-rank solution was shown in the work of Au-Yeung and Poon and the work of Barvinok. In the approach of Au-Yeung and Poon an earlier unpublished manuscript of Bohnenblust played an essential role. Both proofs in the work of Au-Yeung and Poon and that of Barvinok are nonconstructive in nature. The aim of this paper is to provide a polynomial-time constructive procedure to find such a low-rank solution approximatively. Extensions of our new results and their relations to some of the known results in the literature are discussed. [ABSTRACT FROM AUTHOR]

Dynamic shortest-path algorithms update the shortest paths taking into account a change in an arc weight. This paper describes a new generic technique that allows the reduction of heap sizes used by several dynamic single-destination shortest-path algorithms. For unit weight changes, the updates can be done without heaps. These reductions almost always reduce the computational times for these algorithms. In computational testing, several dynamic shortest-path algorithms with and without the heap-reduction technique are compared. Speedups of up to a factor of 1.8 were observed using the heap-reduction technique on random weight changes and of over a factor of five on unit weight changes. We compare as well with Dijkstra's algorithm, which recomputes the paths from scratch. With respect to Dijkstra's algorithm, speedups of up to five orders of magnitude are observed. [ABSTRACT FROM AUTHOR]

In this paper we deal with the problem of finding the first K shortest paths from a single origin node to all other nodes of a directed graph. In particular, we define the necessary, and sufficient conditions for a set of distance label vectors, on the basis of which we propose a class of methods which can be viewed as an extension of the generic label-correcting method for solving the classical single-origin all-destinations shortest path problem. The data structure used is characterized by a set of K lists of candidate nodes, and the proposed methods differ in the strategy used to select the node to be extracted at each iteration. The computational results show that; 1. some label-correcting methods are generally much faster than the double sweep method of Shier (1979); 2. the most efficient node selection strategies, used for solving the classical single-origin all-destinations shortest path problem, have proved to be effective also in the case of the K shortest paths. [ABSTRACT FROM AUTHOR]

This paper focuses on how to optimally route transfer cranes in a container yard during loading operations of export containers at port terminals. Decision variables are the number of containers that a transfer crane picks up at each yard-bay and the sequence of yard-bays that a transfer crane visits during a loading operation. This routing problem is formulated as a mixed integer program. The objective function of the formulation is to minimize the total container handling time of a transfer crane, which includes setup time at each yard-bay and travel time between yard-bays. Based on the mixed integer program, an optimizing algorithm is developed. [ABSTRACT FROM AUTHOR]

Tree traversal algorithms are frequently used for ordering operations on sets. Thru paper describes a tree structure and traversal scheme which is applied to the computation of a reliability measure. The key to this variation is a particular labeling of the enumeration tree which locates supersets of a set S in one subtree of the node labeled with S. Exact computation by simple techniques is considerably more time-consuming than by the "branch and fathom" technique, which may also be useful in computing other functions on the power set of a set. [ABSTRACT FROM AUTHOR]

Elimination methods for the flow-shop problem have been investigated by several authors using special elimination conditions to construct a set of dominant schedules and then enumerate them in order to find an optimum. The few papers reporting computational experience with elimination algorithms indicate that the approach may be an efficient method for obtaining optimal schedules. This note builds a simple model in order to help provide some perspective on these computational results and to describe how elimination algorithms may behave in moderate-sized problems. [ABSTRACT FROM AUTHOR]

This paper describes an experimental comparison of flow-shop algorithms, motivated by the need to consolidate recent research on this topic. Using a set of test problems, it investigated various branch-and-bound and elimination strategies in a comparative study and then combined them to produce a new and efficient solution algorithm. [ABSTRACT FROM AUTHOR]

This paper develops dynamic-programming and other shortest-route algorithms for optimizing sequentially patterned questioning procedures, called diagnostic questionnaires. It uses graph-theoretic methods and solves certain combinatorial problems associated with the Catalan numbers. The paper obtains general properties of optimal questionnaires, including an ordering relation, a convexity result, and the determination of essentially complete classes of questionnaires. It explores a logarithmic charging scheme in detail and obtains a minimax result. Finally, the paper examines the relation with Huffman coding of information theory, and a simple method of Shannon efficiency. [ABSTRACT FROM AUTHOR]

This paper presents a simplex-based solution procedure for the multiple objective linear fractional programming problem. By (1) departing slightly from the traditional notion of efficiency and (2) augmenting the feasible region as in goal programming, the solution procedure solves for all weakly efficient vertices of the augmented feasible region. The article discusses the difficulties that must be addressed in multiple objective linear fractional programming and motivates the solution algorithm that is developed. [ABSTRACT FROM AUTHOR]

This paper compares solution concepts associated with three location problems on a network: (i) a single-facility distance minimization problem; (ii) a two-facility spatial competition problem; and (iii) a single-facility locational voting problem. It is shown that the three problems have a common global solution when the network exhibits a property of symmetry around a point. For more general networks, this ceases to be true for global solutions but an identity holds for local solutions. [ABSTRACT FROM AUTHOR]

In the "classical" network flow model. Flows are constrained by the capacities of individual arcs. In the "polymatroidal" network flow model introduced in this paper, flows are constrained by the capacities of sets of arcs. Yet the essential features of the classical model are retained: the augmenting path theorem, the integral flow theorem and the max flow min-cut theorem are all shown to yield to straightforward generalization. We describe a maximal flow algorithm which finds augmenting paths by labeling arcs instead of nodes, as in the case of the classical model. As a counterpart of a known result for the classical model, we prove that the number of augmentations required to achieve a maximal value flow is bounded by the cube of the number of arcs in the network, provided each successive augmentation is made along a shortest augmenting path, with ties between shortest paths broken by lexicography. [ABSTRACT FROM AUTHOR]

A mathematical programming problem P: minimize z=d[supT]x+e[supT]u+f[supT]v subject to Ax+Bu+Cv≥g, x, u, v≥0, u[supT]v=0, is called a complementary programming (CP) problem. The condition u[supT]v=0 distinguishes CP problems from ordinary LP problems. A variety of nonlinear programming problems can be formulated in this form, including absolute-value programming problems, 0-1 mixed-integer-programming problems, quadratic-programming problems, and so forth. This paper proposes a branch-and-bound algorithm for CP problems and reports some computational results. [ABSTRACT FROM AUTHOR]

The purpose of this paper is to present an algorithm for solving the quadratic binary programming problem. Although a problem with this structure may arise in many situations, it is particularly common in capital budgeting when a decision-maker is confronted with a set of investment proposals from which he must select a portfolio. If returns of proposals are intercorrelated random variables and if the decision-maker uses as his criterion for selection the mean μ and variance σ[sups] of portfolio returns, his decision requires prior identification of the (μ, σ²) efficient set. The algorithm developed to solve the problem and hence necessary to generate the efficient set is based on the concept of implicit enumeration recently introduced by EGON BALAS for solution of the binary linear programming problem. [ABSTRACT FROM AUTHOR]

One formulation of the machine sequencing problem is that of finding a minimaximal path in a disjunctive graph. This paper describes an implicit enumeration procedure that solves the problem by generating a sequence of circuit-free graphs and solving a slightly amended critical-path problem for each graph in the sequence. Each new term of the sequence is generated from an earlier one by complementing one disjunctive arc. The search tree is drastically cut down by the fact that the only disjunctive arcs that have to be considered for being complemented are those on a critical path. An evaluation of these candidates is used to direct the search at each stage, The procedure can start with any feasible schedule (like the one actually used in production, or generated by some heuristics), and gradually improve it. Thus one can possibly stop short of the optimum, with a reasonably 'good' feasible schedule. Storage requirements are limited to the data pertinent to the current node of the search tree. [ABSTRACT FROM AUTHOR]

Duality and symmetry of nonlinear programs are considered. The duality theorem of this paper assures that if the primal problem is solvable at a certain point of its domain of definition then the dual problem is also solvable at the same point and vice versa. [ABSTRACT FROM AUTHOR]

The parts requirements (or `explosion') problem is that of finding the total numbers of components, subassemblies, and assemblies needed to fulfill an order, given the individual requirements needed in each assembly. In this paper two methods are presented for solving the problem, together with the so-called `spare parts' and `netting' problems. The first method involves the use of the inverse of the matrix I-Q where Q is the quantity matrix. The second method is a generalization of the successive multiplication algorithm, first discussed in a special case by ELMALGHRABY. Mathematical proofs of the methods are presented, as is computational experience with small problems. [ABSTRACT FROM AUTHOR]

This paper describes an algorithm for the solution of mathematical programming problems having a linear objective function and non-linear constraints. The algorithm is basically an adaptation of the simplex method to the case of non-linear constraints. Certain complications are, however, introduced through non-linearity in the constraints, and it is shown how these can be overcome. [ABSTRACT FROM AUTHOR]

Subjective expected utility is the most widely used model to represent preferences under uncertainty (when objective probabilities of events may not be known). This paper presents a new behavioral characterization (preference axiomatization) of subjective expected utility. The latter is derived from a behavioral assumption of cardinal independence, also known as standard sequence invariance. This axiom requires that a standard sequence of outcomes (equally spaced in terms of utility) is independent of the conditional event. This axiom is a weaker version of the trade-off consistency condition of Wakker [Wakker PP (1984) Cardinal coordinate independence for expected utility. J. Math. Psych. 28:110-117]. The main representation theorem is derived both in the connected topology approach and the algebraic approach (when step-continuity is replaced with solvability and Archimedean axioms). [ABSTRACT FROM AUTHOR]

In the two-echelon capacitated vehicle routing problem (2E-CVRP), the delivery to customers from a depot uses intermediate depots, called satellites. The 2E-CVRP involves two levels of routing problems. The first level requires a design of the routes for a vehicle fleet located at the depot to transport the customer demands to a subset of the satellites. The second level concerns the routing of a vehicle fleet located at the satellites to serve all customers from the satellites supplied from the depot. The objective is to minimize the sum of routing and handling costs. This paper describes a new mathematical formulation of the 2E-CVRP used to derive valid lower bounds and an exact method that decomposes the 2E-CVRP into a limited set of multidepot capacitated vehicle routing problems with side constraints. Computational results on benchmark instances show that the new exact algorithm outperforms the state-of-the-art exact methods. [ABSTRACT FROM AUTHOR]

Given an undirected graph G = (V,E), the vertex coloring problem (VCP) requires to assign a color to each vertex in such a way that colors on adjacent vertices are different and the number of colors used is minimized. In this paper, we propose a metaheuristic approach for VCP that performs two phases: the first phase is based on an evolutionary algorithm, whereas the second one is a postoptimization phase based on the set covering formulation of the problem. Computational results on a set of DIMACS instances show that the overall algorithm is able to produce high-quality solutions in a reasonable amount of time. For four instances, the proposed algorithm is able to improve the best-known solution while for almost all the remaining instances, it finds the best-known solution in the literature. [ABSTRACT FROM AUTHOR]

In this paper, we study capacitated dynamic lot-sizing problems with or without backorders, under the assumption that production costs are linear, that is, there are no setup costs. These two dynamic lot-sizing problems (with or without backorders) are minimum-cost flow problems on an underlying network that possess a special structure. We show how the well-known successive shortest-path algorithm for the minimum-cost flow problem can be used to solve these problems in O(n²) time, where n is the number of periods in the dynamic lot-sizing problems, and how, with the use of dynamic trees, we can solve these problems in O(n log n) time. Our algorithm also extends to the dynamic lot-sizing problem with integer variables and convex production costs with running time O(n log n log U), where U is the largest demand value. [ABSTRACT FROM AUTHOR]

The main result of this paper is an O(n³) algorithm for the single-item lot-sizing problem with constant batch size and backlogging. We consider a general number of installable batches, i.e., in each time period t we may produce up to mt batches, where the mt are given and time-dependent. This generalizes earlier results as we consider backlogging and a general number of maximum batches. We also give faster algorithms for three special cases of this general problem. When backlogging is not allowed and the costs satisfy the Wagner-Whitin property, the problem is solvable in O(n² log n) time. When the production in each period is required to be either zero or equal to the installed capacity, it is possible to solve the problem with and without backlogging in O(n²) and O (n log n) time, respectively. [ABSTRACT FROM AUTHOR]

This paper considers the multimode resource-constrained project-scheduling problem (MRCPSP) with a minimum-makespan objective. An exact branch and cut algorithm is presented based on the integer linear programming (ILP) formulation of the problem. In the preprocessing stage, lower bounds on the distance between each pair of precedence-constrained activities are derived. These bounds are used to reduce the number of variables in the model and to generate cuts that tighten the linear programming relaxation. The solution process is accelerated by an adaptive branching scheme in conjunction with a bound-tightening scheme that is called iteratively after branching. To find good feasible solutions in the early stages of the computations, a high-level neighborhood search strategy known as local branching is included. Here, a neighborhood of a feasible solution is defined by the linear inequalities in the ILP model and is searched first. As implemented, the full algorithm is exact rather than heuristic in nature. Numerical results are reported for 20- and 30-activity benchmark problems. These are the largest instances available and are generally viewed to be notoriously difficult. Up until now, there were no confirmed optimal solutions for any of the 552 30-activity instances. We were able to find several better solutions and to show that at least 506 are optimal. [ABSTRACT FROM AUTHOR]

Generalizing the P-property of a matrix, Gowda et al. [Gowda, M. S., R. Sznajder, J. Tao. 2004. Some P-properties for linear transformations on Euclidean Jordan algebras. Linear Algebra Appl. 393 203-232] recently introduced and studied P- and globally uniquely solvable (GUS)-properties for linear transformations defined on Euclidean Jordan algebras. In this paper, we study the invariance of these properties under automorphisms of the algebra and of the symmetric cone. By means of these automorphisms and the concept of a principal subtransformation, we introduce and study ultra and super P-(GUS)-properties for a linear transformation on a Euclidean Jordan algebra. [ABSTRACT FROM AUTHOR]

We introduce a new approach to minimizing a function defined as the pointwise maximum over finitely many convex real functions (next referred to as the "component functions"), with the aim of working on the basis of "incomplete knowledge" of the objective function. A descent algorithm is proposed, which need not require at the current point the evaluation of the actual value of the objective function, namely, of all the component functions, thus extending to min-max problems the philosophy of the incremental approaches, widely adopted in the nonlinear least squares literature. Given the nonsmooth nature of the problem, we resort to the well-established machinery of "bundle methods." We provide global convergence analysis of our method, and in addition, we study a subgradient aggregation scheme aimed at simplifying the problem of finding a tentative step. This paper is completed by the numerical results obtained on a set of standard test problems. [ABSTRACT FROM AUTHOR]

In this paper, we introduce the notion of smoothed competitive analysis of online algorithms. Smoothed analysis has been proposed by Spielman and Teng to explain the behavior of algorithms that work well in practice while performing very poorly from a worst-case analysis point of view. We apply this notion to analyze the multilevel feedback algorithm (MLF) to minimize the total flow time on a sequence of jobs released over time when the processing time of a job is only known at time of completion. The initial processing times are integers in the range [1, 2K]. We use a partial bit randomization model, i.e., the initial processing times are smoothed by changing the k least significant bits under a quite general class of probability distributions. We show that MLF admits a smoothed competitive ratio of O((2k/σ)³ + (2k/σ)²2K-k) where σ denotes the standard deviation of the distribution. In particular, we obtain a competitive ratio of O(2K-k) if σ = Θ (2k). We also prove an Ω(2K-k) lower bound for any deterministic algorithm that is run on processing times smoothed according to the partial bit randomization model. For various other smoothing models, including the additive symmetric smoothing one, which is a variant of the model used by Spielman and Teng, we give a higher lower bound of Ω(2K). A direct consequence of our result is also the first average-case analysis of MLF. We show a constant expected ratio of the total flow time of MLF to the optimum under several distributions including the uniform one. [ABSTRACT FROM AUTHOR]

This paper deals with families of optimization problems defined over a common set of potential solutions. We consider several problems-solutions systems, and for each one, prove the existence of a small set of solutions that contains an optimal solution to every problem. These proofs are mostly algebraic in nature. The families of problems covered here mostly include separation problems, problems on graphs and hypergraphs, and SAT problems. [ABSTRACT FROM AUTHOR]

In this paper, we study polynomial time approximation schemes (PTASes) for the no-wait job shop scheduling problem with the makespan objective function. It is known that the problem is MaxSNP-hard in the case when each job is allowed to have three operations or more. We show that if each job has at most two operations, the problem admits a PTAS if the number of machines is a constant (i.e., not part of the input). If the number of machines is not a constant, we show that the problem is hard to approximate within a factor better than 5/4. [ABSTRACT FROM AUTHOR]

We examine the complexity of branch-and-cut proofs in the context of 0-1 integer programs. We establish an exponential lower bound on the length of branch-and-cut proofs that use 0-1 branching and lift-and-project cuts (called simple disjunctive cuts by some authors), Gomory-Chvátal cuts, and cuts arising from the N0 matrix-cut operator of Lovász and Schrijver. A consequence of the lower-bound result in this paper is that branch-and-cut methods of the type described above have exponential running time in the worst case. [ABSTRACT FROM AUTHOR]

In this paper we consider the problem of routing deterministic arriving jobs to parallel servers with deterministic (distinct)service times, where we assume that the arrival rate of the jobs is equal to the total service capacity of the servers. Our goal is to find routing policies that minimize the long-run average waiting time of the arriving jobs. We give lower and upper bounds for the minimal long-run average waiting time, and we present results on the structure of optimal policies. We derive mathematical programming problems that can be solved to obtain optimal routing policies, and for a single queue we have results on routing according to a regular sequence to that queue. Finally, we discuss several algorithms to obtain within reasonable time good but generally not optimal deterministic routing policies. [ABSTRACT FROM AUTHOR]

In this paper we discuss local uniqueness, continuity, and differentiability properties of solutions of parameterized variational inequalities (generalized equations). To this end we use two types of techniques. One approach consists in formulating variational inequalities in a form of optimization problem based on regularized gap functions, and applying a general theory of perturbation analysis of parameterized optimization problems. Another approach is based on a theory of contingent (outer graphical) derivatives and some results about differentiability properties of metric projections. [ABSTRACT FROM AUTHOR]

Column generation is a well-known and widely practiced technique for solving linear programs with too many variables or constraints to include in the initial formulation explicitly. Instead, the required column information is generated at each iteration of the simplex algorithm. This paper shows that, even if the number of variables is low enough for explicit inclusion in the model with the available technology, it may still be more efficient to resort to column generation for some class of problems. [ABSTRACT FROM AUTHOR]

Holding is one of the most commonly used real-time control strategies in transit operations. Given a transit network and its operations plan, the holding problem is to decide at a given time at a control station, which vehicle is to be held and for how long, such that the total passenger cost along the route is minimized over a time period. Previous research on the holding problem has always assumed no real-time information available. Such an assumption not only poses great difficulties in solving the problem, but also limits practical applications in a real-time, dynamic operations environment. In this paper we formulate the holding problem as a deterministic quadratic program in a rolling horizon scheme, and develop an efficient solution algorithm to solve it. Using headway data collected by an automated system, we tested the algorithm and evaluated the impact of the resulting holding policies. Important and interesting properties of the holding solution, obtained from both theoretical and computational analyses, are presented. [ABSTRACT FROM AUTHOR]

This paper introduces a strong valid inequality, the 2-path cut, to produce better lower bounds for the vehicle routing problem with time windows. It also develops an effective separation algorithm to find such inequalities. We next incorporate them as needed in the master problem of a Dantzig-Wolfe decomposition approach. In this enhanced optimization algorithm, the coupling constraints require that each customer be serviced. The subproblem is a shortest path problem with time window and capacity constraints. We apply branch and bound to obtain integer solutions. We first branch on the number of vehicles if this is fractional, and then on the flow variables. The algorithm has been implemented and tested on problems of up to 100 customers from the Solomon datasets. It has succeeded in solving to optimality several previously unsolved problems and a new 150-customer problem. In addition, the algorithm proved faster than algorithms previously considered in the literature. These computational results indicate the effectiveness of the valid inequalities we have developed. [ABSTRACT FROM AUTHOR]

The average time a driver has to wait before he can cross two major streams has been a major performance indicator for unsignalized intersections. The equations presented in this paper give an estimate of this average delay as a function of the average delay to isolated minor stream vehicles (Adams' delay) and the degree of saturation of the minor stream (minor stream entry flow/ maximum entry flow) and a form factor (which quantifies the effect of queueing in the minor stream). It was assumed that drivers were consistent and homogeneous and that headways in each major stream were independent of other headways in the same stream and in the other stream. Although the concepts were described in general terms, equations for the maximum minor stream entry flow and Adams' delay were developed assuming that the headways in the major stream to have a dichotomized distribution as given by R. J. Cowan in 1975. Tanner's equations can be used to calculate the form factor when there is a single major stream and when the minor stream headways are Poissonian. For other conditions, a computer simulation program was used to give estimates of the form factor which give satisfactory estimates of average delay for practical purposes. The discussion in this paper indicates that the degree of bunching in the major streams has a major effect of Adams' delay, average delay and the maximum minor stream entry flow. [ABSTRACT FROM AUTHOR]

This paper contains linear algorithms for finding the Jordan center, the weighted Jordan center and the path center of a tree. All of these algorithms take advantage of an efficient data structure for representing a tree called a canonical recursive representation. As a result, the first two algorithms are different from and faster than similar algorithms in the literature. This paper also defines a new parameter of a graph called the path center, and shows that the path center of a tree T consists of a unique subpath of T. [ABSTRACT FROM AUTHOR]

It is known that when the random variables being compared have a uniform probability measure, as is the case when using financial market data, the computation of efficient sets for first- and second-degree dominance can be greatly simplified if majorization conditions are used instead of the dominance definitions. This paper presents an equally efficient technique for third-degree dominance. [ABSTRACT FROM AUTHOR]

We consider nonlinear programming problem (P) with stochastic constraints. The Lagrangean corresponding to such problems has a stochastic part, which in this work is replaced by its certainty equivalent (in the sense of expected utility theory). It is shown that the deterministic surrogate problem (CE-P) thus obtained, contains a penalty function which penalizes violation of the constraints in the mean. The approach is related to several known methods in stochastic programming such as; chance constraints, stochastic goal programming, reliability programming and mean-variance analysis. The dual problem of (CE-P) is studied (for problems with stochastic righthand sides in the constraints) and a comprehensive duality theory is developed by introducing a new certainty equivalent (NCE) concept. Motivation for the NCE and its potential role in Decision Theory are discussed, as well as mean-variance approximations. [ABSTRACT FROM AUTHOR]