Search

In many statistical learning problems, it is desired that the optimal solution conform to an a priori known sparsity structure represented by a directed acyclic graph. Inducing such structures by means of convex regularizers requires nonsmooth penalty functions that exploit group overlapping. Our study focuses on evaluating the proximal operator of the latent overlapping group lasso developed by Jacob et al. in 2009. We implemented an alternating direction method of multiplier with a sharing scheme to solve large-scale instances of the underlying optimization problem efficiently. In the absence of strong convexity, global linear convergence of the algorithm is established using the error bound theory. More specifically, the paper contributes to establishing primal and dual error bounds when the nonsmooth component in the objective function does not have a polyhedral epigraph. We also investigate the effect of the graph structure on the speed of convergence of the algorithm. Detailed numerical simulation studies over different graph structures supporting the proposed algorithm and two applications in learning are provided. Summary of Contribution: The paper proposes a computationally efficient optimization algorithm to evaluate the proximal operator of a nonsmooth hierarchical sparsity-inducing regularizer and establishes its convergence properties. The computationally intensive subproblem of the proposed algorithm can be fully parallelized, which allows solving large-scale instances of the underlying problem. Comprehensive numerical simulation studies benchmarking the proposed algorithm against five other methods on the speed of convergence to optimality are provided. Furthermore, performance of the algorithm is demonstrated on two statistical learning applications related to topic modeling and breast cancer classification. The code along with the simulation studies and benchmarks are available on the corresponding author's GitHub website for evaluation and future use. [ABSTRACT FROM AUTHOR]

Algorithms for approximating the nondominated set of multiobjective optimization problems are reviewed. The approaches are categorized into general methods that are applicable under mild assumptions and, thus, to a wide range of problems, and into algorithms that are specifically tailored to structured problems. All in all, this survey covers 52 articles published within the last 41 years, that is, between 1979 and 2020. Summary of Contribution: In many problems in operations research, several conflicting objective functions have to be optimized simultaneously, and one is interested in finding Pareto optimal solutions. Because of the high complexity of finding Pareto optimal solutions and their usually very large number, however, the exact solution of such multiobjective problems is often very difficult, which motivates the study of approximation algorithms for multiobjective optimization problems. This research area uses techniques and methods from algorithmics and computing in order to efficiently determine approximate solutions to many well-known multiobjective problems from operations research. Even though approximation algorithms for multiobjective optimization problems have been investigated for more than 40 years and more than 50 research articles have been published on this topic, this paper provides the first survey of this important area at the intersection of computing and operations research. [ABSTRACT FROM AUTHOR]

This paper investigates a decomposition approach for binary optimization problems with nonlinear objectives and linear constraints. Our methodology relies on the partition of the objective function into separate low-dimensional dynamic programming (DP) models, each of which can be equivalently represented as a shortest-path problem in an underlying state-transition graph. We show that the associated transition graphs can be related by a mixed-integer linear program (MILP) so as to produce exact solutions to the original nonlinear problem. To address DPs with large state spaces, we present a general relaxation mechanism that dynamically aggregates states during the construction of the transition graphs. The resulting MILP provides both lower and upper bounds to the nonlinear function, and it may be embedded in branch-and-bound procedures to find provably optimal solutions. We describe how to specialize our technique for structured objectives (e.g., submodular functions) and consider three problems arising in revenue management, portfolio optimization, and healthcare. Numerical studies indicate that the proposed technique often outperforms state-of-the-art approaches by orders of magnitude in these applications. Data and the online appendix are available at https://doi.org/10.1287/mnsc.2017.2849. This paper was accepted by Yinyu Ye, optimization. [ABSTRACT FROM AUTHOR]

In this paper, we consider the so-called worst-case linear optimization (WCLO) with uncertainties on the right-hand side of the constraints. Such a problem often arises in applications such as in systemic risk estimation in finance and stochastic optimization. We first show that the WCLO problem with the uncertainty set corresponding to the l p-norm ((WCLOp)) is NP-hard for p ɛ (1,∞). Second, we combine several simple optimization techniques, such as the successive convex optimization method, quadratic convex relaxation, initialization, and branch-and-bound (B&B), to develop an algorithm for (WCLO2) that can find a globally optimal solution to (WCLO2) within a prespecified ε-tolerance. We establish the global convergence of the algorithm and estimate its complexity. We also develop a finite B&B algorithm for (WCLO∞) to identify a global optimal solution to the underlying problem, and establish the finite convergence of the algorithm. Numerical experiments are reported to illustrate the effectiveness of our proposed algorithms in finding globally optimal solutions to medium and large-scale WCLO instances. [ABSTRACT FROM AUTHOR]

With the emergence of ride-sharing companies that offer transportation on demand at a large scale and the increasing availability of corresponding demand data sets, new challenges arise to develop routing optimization algorithms that can solve massive problems in real time. In "Online Vehicle Routing: The Edge of Optimization in Large-Scale Applications," D. Bertsimas, P. Jaillet, and S. Martin present a novel and generalizable backbone algorithm that uses integer optimization to find high-quality solutions to large routing optimization problems. The algorithm, together with the real-time routing optimization software framework developed and shared by the authors, can dispatch thousands of taxis serving more than 25,000 customers per hour. An extensive study with historical simulations of Yellow Cabs in New York City is used to both show that the algorithm improves on the performance of existing heuristics and to provide insights on the optimization opportunities of a large ride-sharing fleet. With the emergence of ride-sharing companies that offer transportation on demand at a large scale and the increasing availability of corresponding demand data sets, new challenges arise to develop routing optimization algorithms that can solve massive problems in real time. In this paper, we develop an optimization framework, coupled with a novel and generalizable backbone algorithm, that allows us to dispatch in real time thousands of taxis serving more than 25,000 customers per hour. We provide evidence from historical simulations using New York City routing network and yellow cab data to show that our algorithms improve upon the performance of existing heuristics in such real-world settings. The online supplement is available at https://doi.org/10.1287/opre.2018.1763. [ABSTRACT FROM AUTHOR]

Unmanned aircraft systems (UASs) are a promising new mode of transportation for cargo delivery. Although control, navigation, and communication technologies are becoming available on individual flight units, system-level motion management for dense UAS traffic remains an open question. This paper presents a motion-planning model based on nonlinear optimization techniques to centrally coordinate paths for all vehicles traversing a shared two-dimensional (2D) space. An exact bound is derived to characterize the discrete-time separation constraints, and a set of new metrics is proposed to measure 2D traffic flow efficiency. The grand goal is to make all vehicles that come under dispatch reach their respective destinations quickly and efficiently while maintaining a safe intervehicle separation at all times. This infinite-horizon operational problem is formulated as a nonlinear nonconvex optimization model that must be solved in a progressive, receding-horizon fashion. To ensure feasibility and overcome path deadlocks attributed to local optima, a series of heuristic measures are developed. By pivoting on artfully coined intermediate feasibility, the algorithm is able to circumvent imminent deadlocks in a predictive manner and progressively construct the solution with guaranteed feasibility. Simulation experiments are performed at various traffic density levels to generate useful insights for airspace regulators and traffic managers. [ABSTRACT FROM AUTHOR]

We study a class of problems with both binary selection decisions and associated continuous choices that result in stochastic rewards and costs. The rewards are received based on the decision maker's selection, and the costs depend both on the decisions and realizations of the stochastic variables. We consider a family of risk-based objective functions that contains the traditional risk-neutral expected-value objective as a special case. A combination of rounding and sample average approximation is used to produce solutions that are guaranteed to be close to the optimal solution with high probability. We also provide an empirical comparison of the performance of the algorithms on a set of randomly generated instances of a supply chain example problem. The computational results illustrate the theoretical claims in the paper that, for this problem, high-quality solutions can be found with small computational effort. [ABSTRACT FROM AUTHOR]

In this paper, we use the penalty approach in order to study constrained minimization problems in infinite dimensional spaces. A penalty function is said to have the exact penalty property if there is a penalty coefficient for which a solution of an unconstrained penalized problem is a solution of the corresponding constrained problem. In this paper, we establish the exact penalty property for a large class of inequality-constrained minimization problems. [ABSTRACT FROM AUTHOR]

Split cuts constitute a class of cutting planes that has been successfully employed by the majority of branch-and-cut solvers for mixed-integer linear programs. Given a basis of the linear programming (LP) relaxation and a split disjunction, the corresponding split cut can be computed with a closed-form expression. In this paper, we use the lift-and-project framework introduced by Balas and Perregaard to provide the basis, and the reduce-and-split algorithm as described by Cornuéjols and Nannicini to compute the split disjunction. We propose a cut generation algorithm that starts from a Gomory mixed-integer cut and alternates between lift-and-project and reduce-and-split in order to strengthen it. This paper has two main contributions. First, we extend the Balas and Perregaard procedure for strengthening cuts arising from split disjunctions involving one variable to split disjunctions on multiple variables. Second, we apply the reduce-and-split algorithm to nonoptimal bases of the LP relaxation. We provide detailed computational testing of the proposed methods. [ABSTRACT FROM AUTHOR]

The ℓ0-minimization problem that seeks the sparsest point of a polyhedral set is a long-standing, challenging problem in the fields of signal and image processing, numerical linear algebra, and mathematical optimization. The weighted ℓ1-method is one of the most plausible methods for solving this problem. In this paper we develop a new weighted ℓ1-method through the strict complementarity theory of linear programs. More specifically, we show that locating the sparsest point of a polyhedral set can be achieved by seeking the densest possible slack variable of the dual problem of weighted ℓ1-minimization. As a result, ℓ0-minimization can be transformed, in theory, to ℓ0-maximization in dual space through some weight. This theoretical result provides a basis and an incentive to develop a new weighted ℓ1-algorithm, which is remarkably distinct from existing sparsity-seeking methods. The weight used in our algorithm is computed via a certain convex optimization instead of being determined locally at an iterate. The guaranteed performance of this algorithm is shown under some conditions, and the numerical performance of the algorithm has been demonstrated by empirical simulations. [ABSTRACT FROM AUTHOR]

This paper deals with nonhomogeneous Markov decision processes with Borel state space and nonuniformly bounded rewards under the average criterion. First, under the minorant-type assumption we prove the existence of an appropriate solution to the optimality equations. Second, from the optimality equations we also establish the existence of ε(≥ 0)-optimal Markov policies under the additional conditions. Third, some sufficient conditions for the validity of the assumptions in this paper and several examples such as inventory/production systems are provided. Finally, as an application of the optimality equations, a rolling horizon algorithm is given. [ABSTRACT FROM AUTHOR]

This paper deals with undiscounted infinite stage two-person zero-sum stochastic games with finite state and action spaces. It was recently shown that such games possess a value. But in general there are no optimal strategies. We prove that for each player there exists a nonempty set of easy initial states, i.e. starting states for which the player possesses an optimal stationary strategy. This result is proved with the aid of facts derived by Bewley and Kohlberg for the limit discount equation for stochastic games. [ABSTRACT FROM AUTHOR]

In this paper, we investigate the properties of the sampled version of the fictitious play algorithm, familiar from game theory, for games with identical payoffs, and propose a heuristic based on fictitious play as a solution procedure for discrete optimization problems of the form max {u(y) y = (y1,…yn ∈ y1 x … x yn} i.e., in which the feasible region is a Cartesian product of finite sets y1 i ∈ N = (1, …, n). The contributions of this paper are twofold. In the first part of the paper, we broaden the existing results on convergence properties of the fictitious play algorithm on games with identical payoffs to include an approximate fictitious play algorithm that allows for errors in players 'best replies. Moreover, we introduce sampling-based approximate fictitious play that possesses the above convergence properties, and at the same time provides a computationally efficient method for implementing fictitious play. In the second part of the paper, we motivate the use of algorithms based on sampled fictitious play to solve optimization problems in the above form with particular focus on the problems in which the objective function u(·) comes from a "black box," such as a simulation model, where significant computational effort is required for each function evaluation. [ABSTRACT FROM AUTHOR]

We study the strip packing problem, in which a set of two-dimensional rectangular items has to be packed in a rectangular strip of fixed width and infinite height, with the aim of minimizing the height used. The problem is important because it models a large number of real-world applications, including cutting operations where stocks of materials such as paper or wood come in large rolls and have to be cut with minimum waste, scheduling problems in which tasks require a contiguous subset of identical resources, and container loading problems arising in the transportation of items that cannot be stacked one over the other. The strip packing problem has been attacked in the literature with several heuristic and exact algorithms, nevertheless, benchmark instances of small size remain unsolved to proven optimality. In this paper we propose a new exact method that solves a large number of the open benchmark instances within a limited computational effort. Our method is based on a Benders' decomposition, in which in the master we cut items into unit-width slices and pack them contiguously in the strip, and in the slave we attempt to reconstruct the rectangular items by fixing the vertical positions of their unit-width slices. If the slave proves that the reconstruction of the items is not possible, then a cut is added to the master, and the algorithm is reiterated. We show that both the master and the slave are strongly NP-hard problems and solve them with tailored preprocessing, lower and upper bounding techniques, and exact algorithms. We also propose several new techniques to improve the standard Benders' cuts, using the so-called combinatorial Benders' cuts, and an additional lifting procedure. Extensive computational tests show that the proposed algorithm provides a substantial breakthrough with respect to previously published algorithms. [ABSTRACT FROM AUTHOR]

This paper combines two rival preference modeling techniques in a new approach to multi-attribute decision making. Currently existing multi-attribute procedures use either global or local preference modeling. In the global modeling technique, a single preference function is constructed in the large; its maximum is the optimal alternative. In the local procedure, sequential approximations of the preference function are constructed in the small. Each approximation generates a trial solution. Under suitable conditions, each trial solution is preferred to its predecessor, so the trial sequence eventually reaches the optimum. Each technique has advantages and disadvantages; this paper combines the desirable features of both techniques in a new improved method. This new method, called the proxy approach, uses the advantages of one technique to overcome the disadvantages of the other. This paper first develops the theoretical aspects of the proxy approach and then compares it to existing procedures. Finally, the proxy algorithm is applied to a curriculum planning problem and numerous insights are gained. [ABSTRACT FROM AUTHOR]

The motivation for this paper is a problem faced by banks which process large volumes of deposited checks. The checks must be separated by bank number before shipment to the Federal Reserve or other banks. The sorting is usually accomplished using a reader-sorter which reads the magnetic ink characters on the checks and separates them into different "pockets." This paper characterizes the optimal sorting strategy and describes an efficient procedure for finding the optimal solution for problems of the size generally found in practice. The algorithm is based on a two state dynamic programming recursion in which characterization theorems are used to drastically reduce the size of the state space and in which the storage requirements are minimal. The paper includes an analysis of computational experience and describes how the algorithm can be used in a real time environment with deadlines. [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]

This paper examines properties and interrelations of several concepts of generalized concavity. It shows that the class of functions that are both ‘generalized concave’ and ‘generalized convex’ is closely related to the class of monotone functions of a single variable. After excluding a certain small class of exceptions, the paper shows that, for arbitrary (perhaps not differentiable) functions, concave implies pseudoconcave, pseudoconcave implies strictly quasiconcave, and strictly quasiconcave implies quasiconcave. Several results characterizing the extreme values of generalized concave functions are given. [ABSTRACT FROM AUTHOR]

One of the most attractive recent approaches to processing well-structured large-scale convex optimization problems is based on smooth convex-concave saddle point reformulation of the problem of interest and solving the resulting problem by a fast first order saddle point method utilizing smoothness of the saddle point cost function. In this paper, we demonstrate that when the saddle point cost function is polynomial, the precise gradients of the cost function required by deterministic first order saddle point algorithms and becoming prohibitively computationally expensive in the extremely large-scale case, can be replaced with incomparably cheaper computationally unbiased random estimates of the gradients. We show that for large-scale problems with favorable geometry, this randomization accelerates, progressively as the sizes of the problem grow, the solution process. This extends significantly previous results on acceleration by randomization, which, to the best of our knowledge, dealt solely with bilinear saddle point problems. We illustrate our theoretical findings by instructive and encouraging numerical experiments. [ABSTRACT FROM AUTHOR]

In the stochastic orienteering problem, we are given a finite metric space, where each node contains a job with some deterministic reward and a random processing time. The processing time distributions are known and independent across nodes. However the actual processing time of a job is not known until it is completely processed. The objective is to compute a nonanticipatory policy to visit nodes (and run the corresponding jobs) so as to maximize the total expected reward, subject to the total distance traveled plus the total processing time being at most a given budget of B. This problem combines aspects of the stochastic knapsack problem with uncertain item sizes as well as the deterministic orienteering problem. In this paper, we consider both nonadaptive and adaptive policies for Stochastic Orienteering. We present a constant-factor approximation algorithm for the nonadaptive version and an O(log logB)-approximation algorithm for the adaptive version. We extend both these results to directed metrics and a more general sequence orienteering problem. Finally, we address the stochastic orienteering problem when the node rewards are also random and possibly correlated with the processing time and obtain an O(log n logB)-approximation algorithm; here n is the number of nodes in the metric. All our results for adaptive policies also bound the corresponding "adaptivity gaps". [ABSTRACT FROM AUTHOR]

This paper studies the problem of simultaneously locating trauma centers and helicopters. The standard approach to locating helicopters involves the use of helicopter busy fractions to model the random availability of helicopters. However, busy fractions cannot be estimated a priori in our problem because the demand for each helicopter cannot be determined until the trauma center locations are selected. To overcome this challenge, we endogenize the computation of busy fractions within an optimization problem. The resulting formulation has nonconvex bilinear terms in the objective, for which we develop an integrated method that iteratively solves a sequence of problem relaxations and restrictions. Specifically, we devise a specialized algorithm, called the shifting quadratic envelopes algorithm, that (1) generates tighter outer approximations than linear McCormick envelopes and (2) outperforms a Benders-like cut generation scheme. We apply our integrated method to the design of a nationwide trauma care system in Korea. By running a trace-based simulation on a full year of patient data, we find that the solutions generated by our model outperform several benchmark heuristics by up to 20%, as measured by an industry-standard metric: the proportion of patients successfully transported to a care facility within one hour. Our results have helped the Korean government to plan its nationwide trauma care system. More generally, our method can be applied to a class of optimization problems that aim to find the locations of both fixed and mobile servers when service needs to be carried out within a certain time threshold. [ABSTRACT FROM AUTHOR]

A natural optimization model that formulates many online resource allocation problems is the online linear programming (LP) problem in which the constraint matrix is revealed column by column along with the corresponding objective coefficient. In such a model, a decision variable has to be set each time a column is revealed without observing the future inputs, and the goal is to maximize the overall objective function. In this paper, we propose a near-optimal algorithm for this general class of online problems under the assumptions of random order of arrival and some mild conditions on the size of the LP right-hand-side input. Specifically, our learning-based algorithm works by dynamically updating a threshold price vector at geometric time intervals, where the dual prices learned from the revealed columns in the previous period are used to determine the sequential decisions in the current period. Through dynamic learning, the competitiveness of our algorithm improves over the past study of the same problem. We also present a worst case example showing that the performance of our algorithm is near optimal. [ABSTRACT FROM AUTHOR]

In this paper, we describe an effective exact method for solving both the capacitated vehicle routing problem (CVRP) and the vehicle routing problem with time windows (VRPTW) that improves the method proposed by Baldacci et al. [Baldacci, R., N. Christofides, A. Mingozzi. 2008. An exact algorithm for the vehicle routing problem based on the set partitioning formulation with additional cuts. Math. Programming 115(2) 351-385] for the CVRP. The proposed algorithm is based on the set partitioning (SP) formulation of the problem. We introduce a new route relaxation called ng-route, used by different dual ascent heuristics to find near-optimal dual solutions of the LP-relaxation of the SP model. We describe a column-and-cut generation algorithm strengthened by valid inequalities that uses a new strategy for solving the pricing problem. The new ng-route relaxation and the different dual solutions achieved allow us to generate a reduced SP problem containing all routes of any optimal solution that is finally solved by an integer programming solver. The proposed method solves four of the five open Solomon's VRPTW instances and significantly improves the running times of state-of-the-art algorithms for both VRPTW and CVRP. [ABSTRACT FROM AUTHOR]

This paper presents an exact algorithm for solving strategic and tactical multiperiod vehicle routing problems that can be modeled as period vehicle routing problems (PVRPs). The PVRP is defined on a time horizon of several days and consists of assigning appropriate combinations of delivery to customers and designing a set of delivery routes for every day of the planning period. The objective is to service all customers assigned to each day minimizing the overall routing cost. This paper describes an integer programming formulation of the PVRP that is used to derive different lower bounds and an exact solution method. Computational results on test instances from the literature and on new sets of test instances show the effectiveness of the proposed method. [ABSTRACT FROM AUTHOR]

In this paper, we give a finite disjunctive programming procedure to obtain the convex hull of general mixed-integer linear programs (MILP) with bounded integer variables. We propose a finitely convergent convex hull tree algorithm that constructs a linear program that has the same optimal solution as the associated MILP. In addition, we combine the standard notion of sequential cutting planes with ideas underlying the convex hull tree algorithm to help guide the choice of disjunctions to use within a cutting plane method. This algorithm, which we refer to as the cutting plane tree algorithm, is shown to converge to an integral optimal solution in finitely many iterations. Finally, we illustrate the proposed algorithm on three well-known examples in the literature that require an infinite number of elementary or split disjunctions in a rudimentary cutting plane algorithm. [ABSTRACT FROM AUTHOR]

This paper focuses on a generic model for service network design, which includes asset positioning and utilization through constraints on asset availability at terminals. We denote these relations as "design-balance constraints" and focus on the design-balanced capacitated multicommodity network design model, a generalization of the capacitated multicommodity network design model generally used in service network design applications. Both arc- and cycle-based formulations for the new model are presented. The paper also proposes a tabu search metaheuristic framework for the arc-based formulation. Results on a wide range of network design problem instances from the literature indicate the proposed method behaves very well in terms of computational efficiency and solution quality. [ABSTRACT FROM AUTHOR]

We present a new computational approach to the problem of placing n identical nonoverlapping disks in the unit square in such a way that their radii are maximized. The problem has been studied in a large number of papers, from both a theoretical and a computational point of view. In this paper, we conjecture that the problem possesses a so-called funneling landscape, a feature that is commonly found in molecular conformation problems. Based on this conjecture, we develop a stochastic search algorithm that displays excellent numerical performance. Thanks to this algorithm, we could improve over previously known putative optima in the range n ≤ 130 in as many as 32 instances, the smallest of which is n=53. [ABSTRACT FROM AUTHOR]

In 1958, Wagner and Whitin published a seminal paper on the deterministic uncapacitated lot-sizing problem, a fundamental model that is embedded in many practical production planning problems. In this paper, we consider a basic version of this model in which problem parameters are stochastic: the stochastic uncapacitated lot-sizing problem. We define the production-path property of an optimal solution for our model and use this property to develop a backward dynamic programming recursion. This approach allows us to show that the value function is piecewise linear and right continuous. We then use these results to show that a full characterization of the optimal value function can be obtained by a dynamic programming algorithm in polynomial time for the case that each nonleaf node contains at least two children. Moreover, we show that our approach leads to a polynomial-time algorithm to obtain an optimal solution to any instance of the stochastic uncapacitated lot-sizing problem, regardless of the structure of the scenario tree. We also show that the value function for the problem without setup costs is continuous, piecewise linear, and convex, and therefore an even more efficient dynamic programming algorithm can be developed for this special case. [ABSTRACT FROM AUTHOR]

The introduction of edge-finding techniques was a significant development in constraint-based scheduling. Today, edge finders are still the state of the art in the disjunctive case and a technique of interest in cumulative scheduling. This paper reconsiders edge-finding algorithms for cumulative scheduling and shows that Nuijten's edge finder, and its derivatives, are incomplete because they use an invalid dominance rule. We then present a correct cumulative edge finder running in time O(n²k), where n is the number of tasks and k the number of different capacity requirements of the tasks. The new algorithm is organized in two phases and first uses dynamic programming to precompute the innermost maximization in the edge-finder specification. The paper also proposes the first extended edge-finding algorithms that run in time O(n²k), improving the running time of available algorithms. Finally, the paper discusses how to speed up the algorithm in practice and how the first phase can be used to improve algorithms based on energetic reasoning. [ABSTRACT FROM AUTHOR]

This paper considers the provisioning of transmission line bandwidth on a private network with given traffic routing for the purpose of distribution of video-on-demand service with guaranteed end-to-end quality of service. We present an architecture for video-on-demand service delivery and model the assignment of bandwidth in the distribution network as a constrained, nonlinear optimization problem. To solve this optimization problem, we develop three new auction algorithm-based solution procedures. The optimization problem assumes that there is a functional relationship between the maximum acceptable end-to-end delay and the bandwidth requirement for the links in the distribution network. Absent reliable video traffic data models for MPEG-2 format, we sample a large number of DVD-recorded movies to form a basis for randomly generated aggregate traffic streams. The aggregate traffic streams are used in a simulation experiment to measure the maximum transmission buffer occupancy for each given traffic stream for different transmission rates. Based on this simulation experiment, we derive an empirical transmission line provisioning function that guarantees delivery of all video frames without frame loss within a maximum frame delay tolerance. To illustrate the effectiveness of the proposed solution procedure for the bandwidth assignment problem, we solve to near optimality 570 small problem instances under three demand structures and 100 large problem instances with uniformly distributed demand. [ABSTRACT FROM AUTHOR]

Roughly speaking, the no-free-lunch (NFL) theorems state that any blackbox algorithm has the same average performance as random search. These results have largely been ignored by algorithm researchers. This paper looks more closely at the NFL results and focuses on their implications for combinatorial problems typically faced by many researchers and practitioners. We derive necessary conditions for the NFL results to hold based on common problem structures. Often it is simple to verify that these conditions are not present in the class of problems under investigation, thus providing a theoretical basis for ignoring the doleful implications of NFL giving justification for believing there might be a dominant algorithm for the problem class under study. We apply our results to three common classes of problems. We find that only trivial subclasses of these problems fall under the NFL implications. [ABSTRACT FROM AUTHOR]

The performance of a given portfolio policy can in principle be evaluated by comparing its expected utility with that of the optimal policy. Unfortunately, the optimal policy is usually not computable, in which case a direct comparison is impossible. In this paper, we solve this problem by using the given portfolio policy to construct an upper bound on the unknown maximum expected utility. This construction is based on a dual formulation of the portfolio optimization problem. When the upper bound is close to the expected utility achieved by the given portfolio policy, the potential utility loss of this policy is guaranteed to be small. Our algorithm can be used to evaluate portfolio policies in models with incomplete markets and position constraints. We illustrate our methodology by analyzing the static and myopic policies in markets with return predictability and constraints on short sales and borrowing. [ABSTRACT FROM AUTHOR]

Researchers and practitioners frequently spend more time fine-tuning algorithms than designing and implementing them. This is particularly true when developing heuristics and metaheuristics, where the "right" choice of values for search parameters has a considerable effect on the performance of the procedure. When testing metaheuristics, performance typically is measured considering both the quality of the solutions obtained and the time needed to find them. In this paper, we describe the development of CALIBRA, a procedure that attempts to find the best values for up to five search parameters associated with a procedure under study. Because CALIBRA uses Taguchi's fractional factorial experimental designs coupled with a local search procedure, the best values found are not guaranteed to be optimal. We test CALIBRA on six existing heuristic-based procedures. These experiments show that CALIBRA is able to find parameter values that either match or improve the performance of the procedures resulting from using the parameter values suggested by their developers. The latest version of CALIBRA can be downloaded for free from the website that appears in the online supplement of this paper at http://or.pubs.informs.org/Pages.collect.html. [ABSTRACT FROM AUTHOR]

New lock box solution techniques have recently been suggested by Stone and Nauss-Markland. This paper briefly discusses these new methodologies and shows how the algorithms can be combined into a third solution procedure which exploits the computational efficiency of the Stone heuristic and retains the optimizing property of the Nauss-Markland algorithm. [ABSTRACT FROM AUTHOR]

The subject of this paper is a classification and discussion of algorithms for solution of nonlinear pure integer programming problems. The survey is organized by characterizing the mathematical form of the nonlinear optimization problems addressed by the various algorithms. If any method can be used without changes to solve mixed integer nonlinear programming problems that fact is mentioned in the description of the algorithm. However algorithms which must be applied only to mixed integer problems are not surveyed. [ABSTRACT FROM AUTHOR]

This paper considers optimization problems with a nonlinear-additive objective function and a single linear constraint. Such models have numerous direct applications and serve as subproblems in procedures for more complex problems. Some important portfolio selection problems can be expressed in this form, and the problem also arises in economic theory. Several authors have noticed independently that special cases and variants of the problem can be solved exactly by surprisingly simple, finite algorithms. The major purpose of this paper is to present these results in a unified framework, which then permits substantial generalizations and extensions. The results lend themselves to an appealing managerial interpretation, similar to the rate-of-return cutoff rules of capital budgeting. [ABSTRACT FROM AUTHOR]

This paper examines the problem of deriving the tangent (or market) portfolio from a given set of risky assets and a specified risk-free borrowing and lending rate. Deriving the tangent portfolio involves solving a mathematical programming problem which can be specified as the minimization of a quadratic objective function with linear constraints. The complementary pivot algorithm has previously been shown to be capable of deriving the optimal solution to certain quadratic programming problems, subject to a nonnegativity constraint. This paper demonstrates that the algorithm can be used to derive the tangent portfolio and that the nonnegativity constraint does not pose any serious handicap. Furthermore, it is shown that the algorithm can efficiently solve large-scale problems of this nature. [ABSTRACT FROM AUTHOR]

This paper, which is presented in two parts, is a contribution to the theory of fractional programming, i.e. maximization of quotients subject to constraints. In Part 1, duality theory for linear and concave-convex fractional programs is developed and related to recent results by Bector, Craven-Mond, Jagannathan, Sharma-Swarup, et al. Basic duality theorems of linear, quadratic and convex programming are extended. In Part II Dinkelbach's algorithm solving fractional programs is considered. The rate of convergence as well as a priori and a posteriori error estimates are determined. In view of these results the stopping rule of the algorithm is changed. Also the starting rule is modified using duality as introduced in Part I. Furthermore a second algorithm is proposed. In contrast to Dinkelbach's procedure the rate of convergence is still controllable. Error estimates are obtained too. [ABSTRACT FROM AUTHOR]

This paper investigates the optimal allocation of the marketing budget within the marketing-mix decision variables so that sales (or profit) is maximized in a planning horizon. Since the influence of marketing mix variables upon sales are, in reality, nonlinear and interactive, a geometric programming algorithm is used that solves this problem. A procedure to estimate a functional of sales on the marketing mix and environmental variables utilizing the experienced judgments of the firm's executives and the raw data is provided. The derived functional is later optimized by the Geometric Programming algorithm under a constraint set consisting of budget and strategy restrictions imposed by a firm's marketing environment, and conditions under which the optimal solution is either local or global are identified. An empirical application for a large midwestern brewery is provided which utilizes and illustrates both the estimation an optimization procedures. [ABSTRACT FROM AUTHOR]

This paper treats the discounted cost, optimal control problem for Markov processes with incomplete state information. The optimization approach for these partially observable Markov processes is a generalization of the well-known policy iteration technique for finding optimal stationary policies for completely observable Markov processes. The state space for the problem is the space of state occupancy probability distributions (the unit simplex). The development of the algorithm introduces several new ideas, including the class of finitely transient policies, which are shown to possess piecewise linear cost functions. The paper develops easily implemented approximations to stationary policies based on these finitely transient policies and shows that the concave hull of an approximation can be included in the well-known Howard policy improvement algorithm with subsequent convergence. The paper closes with a detailed example illustrating the application of the algorithm to the two-state partially observable Markov process. [ABSTRACT FROM AUTHOR]

This paper deals with systems (such as electronic devices and corporations) that are designed to accomplish multiple goals and whose internal structures are characterized by networks of interacting component parts. Each component of such a system is typically associated with a probability of failure, while each system goal is associated with a reward value. Failure of any network component may ultimately result in the inability to achieve one or more goals and force the forfeiture of the associated rewards. A basic problem in component-system design is to determine how the expectation of total reward may be maximized through the cost-limited acquisition of redundant (backup) components. This paper provides a formal statement of this redundancy-optimization problem and argues that the problem may not be solved easily by standard linear or integer programming techniques. It introduces an algorithm to solve this problem, proves its convergence, and presents computational results taken from a battery of test problems and an algorithm-efficiency study based on these tests. [ABSTRACT FROM AUTHOR]

This paper treats the optimal location of nuclear-power plants in the Pacific Northwest with respect to capital-construction, operating, and transmission costs. It presents a mathematical formulation of this two-product (peak and energy power) plant-location problem, using the simplex method in conjunction with a branch-and-bound process, and indicates a check procedure using Vogel's approximation method in conjunction with an algorithm for solving the transportation problem and a branch-and-bound process. The paper gives results for demand-growth rates of 4, 5, 6 and 7 percent and alternative designs and their costs. It also discusses the stability of the optimal solution. [ABSTRACT FROM AUTHOR]

This paper develops a new cutting plane for primal integer programming. This cut, when it exists and is used as pivot row, has the property that the minimum of the simplex evaluators of the next tableau is strictly larger (by an integer) than the minimum for the current tableau. The paper gives a sufficient condition in the form of a linear program for the existence of such a cut, and proposes an algorithm for generating such cuts. It also presents two additional sufficient conditions. The process of cut generation is then imbedded into a convergent primal algorithm to be used in an attempt to overcome the proof-of-optimality problem experienced with the primal algorithm. [ABSTRACT FROM AUTHOR]

Randomizing (stochastic) global optimization algorithms can be viewed as sampling procedures, where at each iteration a local optimum is sampled from the set of local optima. The effectiveness of such an algorithm depends crucially on the sampling distribution, i.e., on the probabilities of sampling the various local optima. There exists a very large body of research on stochastic global optimization. However, very little is known about the sampling distribution itself and, in particular, on the specific way in which it depends on the function being optimized, on the region in which the search takes place, and on the optimization routine. In this paper we set out to examine these issues in some detail and present some first results in this direction. The case analyzed in this paper is the optimization of a one-dimensional function using a randomizing version of binary search. We give an effective (computable in quadratic time) formula for the sampling distribution and obtain various interesting properties of this distribution which are relevant to the behavior of the algorithm in practice. We also discuss some issues related to adaptive search. [ABSTRACT FROM AUTHOR]

This paper introduces and studies an optimization problem related to the alias method for discrete random-variate generation. The alias method is an efficient method to generate random variates from a discrete probability distribution. The efficiency of the alias method can be improved by designing the alias table such that the expected number of computations that must be performed per value generated is minimized. The problem of optimizing the construction of the alias table is proven to be strongly NP-hard, even if either of two variations of the alias method relaxing the alias-table-generation restrictions are used. Integer-programming formulations describing these three optimization problems are presented, and insights regarding necessary optimality criteria and relationships among their optimal solutions are discussed. [ABSTRACT FROM AUTHOR]

The vehicle routing problem with time windows is a hard combinatorial optimization problem that has received considerable attention in the last decades. This paper proposes a two-stage hybrid algorithm for this transportation problem. The algorithm first minimizes the number of vehicles, using simulated annealing. It then minimizes travel cost by using a large neighborhood search that may relocate a large number of customers. Experimental results demonstrate the effectiveness of the algorithm, which has improved 10 (17%) of the 56 best published solutions to the Solomon benchmarks, while matching or improving the best solutions in 46 problems (82%). More important perhaps,the algorithm is shown to be very robust. With a fixed configuration of its parameters, it returns either the best published solutions (or improvements thereof) or solutions very close in quality on all Solomon benchmarks. Very preliminary results on the extended Solomon benchmarks are also given. [ABSTRACT FROM AUTHOR]

Motivated by applications in freight handling and open-pit mining, Rhys, Balinski, and Picard studied the problems of selection and closure in papers published in Management Science in 1970 and 1976. They identified efficient algorithms based on linear programming and maximum-flow/minimum-cut procedures to solve these problems. This research has had major impact well beyond the initial applications, reaching across three decades and inspiring work on numerous applications and extensions. The extensions are nontrivial optimization problems that are of theoretical interest. The applications ranged from evolving technologies, image segmentation, revealed preferences, pricing, adjusting utilities for consistencies, just-in-time production, solving certain integer programs in polynomial time, and providing efficient 2-approximation algorithms for a wide variety of hard problems. A recent generalization to a convex objective function has even produced novel solutions to prediction and Bayesian estimation problems. This paper surveys the streams of research stimulated by these papers as an example of the impact of Management Science on the optimization field and an illustration of the far-reaching implications of good original research. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

One of the basic assumptions of the classical dynamic lot-sizing model is that the aggregate demand of a given period must be satisfied in that period. Under this assumption, if backlogging is not allowed, then the demand of a given period cannot be delivered earlier or later than the period. If backlogging is allowed, the demand of a given period cannot be delivered earlier than the period, but it can be delivered later at the expense of a backordering cost. Like most mathematical models, the classical dynamic lot-sizing model is a simplified paraphrase of what might actually happen in real life. In most real-life applications, the customer offers a grace period--we call it a demand time window--during which a particular demand can be satisfied with no penalty. That is, in association with each demand, the customer specifies an acceptable earliest and a latest delivery time. The time interval characterized by the earliest and latest delivery dates of a demand represents the corresponding time window. This paper studies the dynamic lot-sizing problem with demand time windows and provides polynomial time algorithms for computing its solution. If backlogging is not allowed, the complexity of the proposed algorithm is O(T²) where T is the length of the planning horizon. When backlogging is allowed, the complexity of the proposed algorithm is O(T³). [ABSTRACT FROM AUTHOR]

In this paper, we focus on a useful modeling concept that is frequently ignored while formulating discrete optimization problems. Very often, there exists a natural symmetry inherent in the problem itself that, if propagated to the model, can hopelessly mire a branch-and-bound solver by burdening it to explore and eliminate such alternative symmetric solutions. We discuss three applications where such a symmetry arises: a telecommunications network design problem, a noise pollution problem, and a machine procurement and operation problem. For each case, we identify the indistinguishable objects in the model that create the problem symmetry and show how imposing certain decision hierarchies within the model significantly enhances its solvability, while using a popular modern-day commercial branch-and-cut software (CPLEX 6.5). [ABSTRACT FROM AUTHOR]