52 results
Search Results
2. Constructing New Weighted ℓ1-Algorithms for the Sparsest Points of Polyhedral Sets.
- Author
-
Zhao, Yun-Bin and Luo, Zhi-Quan
- Subjects
POLYHEDRAL functions ,ALGORITHMS ,MATHEMATICAL optimization ,IMAGE processing ,LINEAR algebra - Abstract
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]- Published
- 2017
- Full Text
- View/download PDF
3. NONHOMOGENOUS MARKOV DECISION PROCESSES WITH BOREL STATE SPACE-- THE AVERAGE CRITERION WITH NONUNIFORMLY BOUNDED REWARDS.
- Author
-
Xianping Guo, Jianyong Liu, and Ke Liu
- Subjects
MARKOV processes ,BOREL sets ,MATHEMATICAL optimization ,ALGORITHMS ,STOCHASTIC processes - Abstract
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]
- Published
- 2000
- Full Text
- View/download PDF
4. ON THE EXISTENCE OF EASY INITIAL STATES FOR UNDISCOUNTED STOCHASTIC GAMES.
- Author
-
Tijs, S. H. and Vrieze, O. J.
- Subjects
GAME theory ,STOCHASTIC processes ,MATHEMATICAL optimization ,MATHEMATICAL analysis ,MATHEMATICS ,SIMULATION methods & models ,ALGORITHMS ,MATHEMATICAL functions ,FUNCTIONALS - Abstract
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]
- Published
- 1986
- Full Text
- View/download PDF
5. On Solving Large-Scale Polynomial Convex Problems by Randomized First-Order Algorithms.
- Author
-
Ben-Tal, Aharon and Nemirovski, Arkadi
- Subjects
POLYNOMIALS ,ALGORITHMS ,MATHEMATICAL optimization ,GEOMETRY ,RANDOMIZATION (Statistics) - Abstract
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]
- Published
- 2015
- Full Text
- View/download PDF
6. Running Errands in Time: Approximation Algorithms for Stochastic Orienteering.
- Author
-
Gupta, Anupam, Krishnaswamy, Ravishankar, Nagarajan, Viswanath, and Ravi, R.
- Subjects
APPROXIMATION theory ,ALGORITHMS ,STOCHASTIC analysis ,MATHEMATICAL optimization ,PROBLEM solving - Abstract
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]
- Published
- 2015
- Full Text
- View/download PDF
7. RANDOM BINARY SEARCH: A RANDOMIZING ALGORITHM FOR GLOBAL OPTIMIZATION IN R.
- Author
-
Zemel, Eitan
- Subjects
ALGORITHMS ,MATHEMATICAL optimization ,STOCHASTIC processes ,ITERATIVE methods (Mathematics) ,DISTRIBUTION (Probability theory) ,PROBABILITY theory ,STATISTICAL sampling ,MATHEMATICS ,OPERATIONS research - Abstract
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]
- Published
- 1986
- Full Text
- View/download PDF
8. THE COMPLEXITY OF GENERIC PRIMAL ALGORITHMS FOR SOLVING GENERAL INTEGER PROGRAMS.
- Author
-
Schulz, Andreas S. and Weismantel, Robert
- Subjects
COMBINATORIAL optimization ,INTEGER programming ,ALGORITHMS ,MATHEMATICAL optimization ,POLYNOMIALS ,COMPUTATIONAL complexity ,VECTOR analysis - Abstract
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]
- Published
- 2002
- Full Text
- View/download PDF
9. EQUIVALENCE OF SOLUTIONS TO NETWORK LOCATION PROBLEMS.
- Author
-
Hansen, P., Thisse, J.-F., and Wendell, R. E.
- Subjects
LOCATION problems (Programming) ,TRANSPORTATION problems (Programming) ,LINEAR programming ,MATHEMATICAL programming ,ALGORITHMS ,MATHEMATICAL optimization ,ALGEBRA ,OPERATIONS research ,MATHEMATICS - Abstract
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]
- Published
- 1986
- Full Text
- View/download PDF
10. COMBINATORIAL OPTIMIZATION WITH RATIONAL OBJECTIVE FUNCTIONS.
- Author
-
Megiddo, Nimrod
- Subjects
MATHEMATICAL optimization ,ALGORITHMS - Abstract
Let A be the problem of minimizing c[sub1x[sub1] + ... + c[subn]x[subn] subject to certain constraints on x = (x[sub1], ...., x[subn]), and let B be the problem of minimizing (a[sub0] + a[sub1]x[sub1] + ... + a[subn]x[subn])/(b[sub0] + b[sub1]x[sub1]+ ...+ b[subn]x[subn]) subject to the same constraints, assuming the denominator is always positive. It is shown that if A is solvable within O [p(n)] comparisons and O [q(n)] additions, then B is solvable in time O[p(n)(q(n)+p(n))]. This applies to most of the "network" algorithms. Consequently, minimum ratio cycles, minimum ratio spanning trees, minimum ratio (simple) paths, maximum ratio weighted matchings, etc., can be computed withing polynomial-time in the number of variables. This improves a result of E. L. Lawler, namely, that a minimum ratio cycle can be computed within a time bound which is polynomial in the number of bits required to specify an instance of the problem. A recent result on minimum ratio spanning trees by R. Chandrasekaran is also improved by the general arguments presented in this paper. Algorithms of time-complexity O(|E|•|V|²•log|V|) for a minimum ratio cycle and O(|E|•log²|V|•log log|V|) for a minimum ratio spanning tree are developed. [ABSTRACT FROM AUTHOR]
- Published
- 1979
- Full Text
- View/download PDF
11. Optimal Lower Bounds for Anonymous Scheduling Mechanisms.
- Author
-
Ashlagi, Itai, Dobzinski, Shahar, and Lavi, Ron
- Subjects
MATHEMATICAL optimization ,ALGORITHMS ,MATHEMATICAL analysis ,MATHEMATICAL bounds ,PROOF theory ,SCHEDULING - Abstract
We consider the problem of designing truthful mechanisms on m unrelated machines, to minimize some optimization goal. Nisan and Ronen [Nisan, N., A. Ronen. 2001. Algorithmic mechanism design. Games Econom. Behav. 35 166-196] consider the specific goal of makespan minimization, and show a lower bound of 2, and an upper bound of m. This large gap inspired many attempts that yielded positive results for several special cases, but very partial success for the general case: the lower bound was slightly increased to 2.61 by Christodoulou et al. [Christodoulou, G., E. Koutsoupias, A. Kovács. 2010. Mechanism design for fractional scheduling on unrelated machines. ACM Trans. Algorithms (TALG) 6(2) 1-18] and Koutsoupias and Vidali [Koutsoupias, E., A. Vidali. 2007. A lower bound of 1+phi for truthful scheduling mechanisms. Proc. 32nd Internat. Sympos. Math. Foundations Comput. Sci. (MFCS)], while the best upper bound remains unchanged. In this paper we show the optimal lower bound on truthful anonymous mechanisms: no such mechanism can guarantee an approximation ratio better than m. Moreover, our proof yields similar optimal bounds for two other optimization goals: the sum of completion times and the l norm of the schedule. [ABSTRACT FROM AUTHOR]
- Published
- 2012
- Full Text
- View/download PDF
12. Optimality of Affine Policies in Multistage Robust Optimization.
- Author
-
Bertsimas, Dimitris, Iancu, Dan A., and Parrilo, Pablo A.
- Subjects
ROBUST optimization ,AFFINE geometry ,ALGORITHMS ,METHODOLOGY ,INVENTORY control ,MATHEMATICAL optimization - Abstract
In this paper, we prove the optimality of disturbance-affine control policies in the context of one-dimensional, constrained, multistage robust optimization. Our results cover the finite-horizon case, with minimax (worst-case) objective, and convex state costs plus linear control costs. We develop a new proof methodology, which explores the relationship between the geometrical properties of the feasible set of solutions and the structure of the objective function. Apart from providing an elegant and conceptually simple proof technique, the approach also entails very fast algorithms for the case of piecewise-affine state costs, which we explore in connection with a classical inventory management application. [ABSTRACT FROM AUTHOR]
- Published
- 2010
- Full Text
- View/download PDF
13. Penalty and Smoothing Methods for Convex Semi-Infinite Programming.
- Author
-
Auslender, Alfred, Goberna, Miguel A., and López, Marco A.
- Subjects
MATHEMATICAL optimization ,MATHEMATICAL programming ,ALGORITHMS ,SMOOTHING (Numerical analysis) ,OPERATIONS research - Abstract
In this paper we consider min-max convex semi-infinite programming. To solve these problems we introduce a unified framework concerning Remez-type algorithms and integral methods coupled with penalty and smoothing methods. This framework subsumes well-known classical algorithms, but also provides some new methods with interesting properties. Convergence of the primal and dual sequences are proved under minimal assumptions. [ABSTRACT FROM AUTHOR]
- Published
- 2009
- Full Text
- View/download PDF
14. Online Scheduling of a Single Machine to Minimize Total Weighted Completion Time.
- Author
-
Anderson, Edward J. and Potts, Chris N.
- Subjects
PRODUCTION scheduling ,PRODUCTION control ,ALGORITHMS ,ONLINE data processing ,MATHEMATICAL optimization - Abstract
This paper considers the online scheduling of a single machine in which jobs arrive over time, and preemption is not allowed. The goal is to minimize the total weighted completion time. We show that a simple modification of the shortest weighted processing time rule has a competitive ratio of two. This result is established using a new proof technique that does not rely explicitly on a lower bound on the optimal objective function value. Because it is known that no online algorithm can have a competitive ratio of less than two, we have resolved the open issue of determining the minimum competitive ratio for this problem. [ABSTRACT FROM AUTHOR]
- Published
- 2004
- Full Text
- View/download PDF
15. ON THE COMPLEXITY OF COMPUTING ESTIMATES OF CONDITION MEASURES OF A CONIC LINEAR SYSTEM.
- Author
-
Freund, Robert M. and Vera, Jorge R.
- Subjects
MATHEMATICAL optimization ,LINEAR programming ,MATHEMATICAL programming ,ERROR analysis in mathematics ,LINEAR systems ,ALGORITHMS ,OPERATIONS research - Abstract
Condition numbers based on the "distance to ill-posedness" ρ(d) have been shown to play a crucial role in the theoretical complexity of solving convex optimization models. In this paper, we present two algorithms and corresponding complexity analysis for computing estimates of ρ(d) for a finite-dimensional convex feasibility problem P(d) in standard primal form: find x that satisfies Ax = b, x ∈ C[subx], where d = (A, b) is the data for the problem P(d). Under one choice of norms for the m- and n-dimensional spaces, the problem of estimating ρ(d) is hard (co-NP complete even when C[subx] = ℜ[supn][sub+]). However, when the norms are suitably chosen, the problem becomes much easier: We can estimate ρ(d) to within a constant factor of its true value with complexity bounds that are linear in ln(C(d)) (where C(d) is the condition number of the data d for P(d), plus other quantities that arise naturally in consideration of the problem P(d). The first algorithm is an interior-point algorithm, and the second algorithm is a variant of the ellipsoid algorithm. The main conclusion of this work is that when the norms are suitably chosen, computing an estimate of the condition measures of P(d) is essentially not much harder than computing a solution of P(d) itself. [ABSTRACT FROM AUTHOR]
- Published
- 2003
- Full Text
- View/download PDF
16. A FAST COMPUTATIONAL PROCEDURE TO SOLVE THE MULTI-ITEM SINGLE MACHINE LOT SCHEDULING OPTIMIZATION PROBLEM: THE AVERAGE COST CASE.
- Author
-
Aragone, L. S. and González, R. L. V.
- Subjects
VISCOSITY ,OPERATIONS research ,MATHEMATICAL optimization ,ALGORITHMS ,MATHEMATICAL inequalities ,INFINITE processes - Abstract
In this paper we present some special procedures for the numerical solution of the optimal scheduling problem of a multi-item single machine. We study the infinite horizon case when the optimization criterion is the average cost. We establish the solution of the problem in terms of viscosity solutions of the Quasi-Variational Inequality (QVI) system associated to the problem. The existence of solution of the QVI and the uniqueness of the optimal average cost are proved. A method of discretization and a computational procedure are described. They allow us to compute the solution in a short time and with precision of order k. We obtain an estimate for the discretization error and develop an algorithm that converges in a finite number of steps. In our method the nodes of the triangulation mesh are joined by segments of trajectories of the original system. This feature allows us to obtain the k-order precision which, in general, is impossible to obtain by usual methods. [ABSTRACT FROM AUTHOR]
- Published
- 2000
- Full Text
- View/download PDF
17. THE QUICKEST TRANSSHIPMENT PROBLEM.
- Author
-
Hoppe, Bruce and Tardos, Eva
- Subjects
POLYNOMIALS ,ALGORITHMS ,MATHEMATICAL optimization ,MATHEMATICAL analysis ,DYNAMIC programming ,MATHEMATICAL programming ,GRAPH theory - Abstract
The article presents information on the first polynomial-time algorithm for the quickest transshipment problem. The quickest transshipment problem is defined by a dynamic network with a set of sources and sinks;each source has a specified supply of flow, and each sink has a specified demand. The problem is to send exactly the right amount of flow out of each source and into each sink in the minimum overall time, if possible. The integral quickest transshipment problem requires a solution that is not only optimal but also integral. This paper describes the first polynomial-time algorithm for the quickest transshipment problem, and also provides an integral flow. Dynamic networks allow not only flow on edges but also intermediate storage at vertices. This corresponds to holding inventory at a node before sending it onward. Unfortunately, the maximum dynamic flow problem is about the only one to yield to a temporally repeated solution. Most other dynamic flow problems are typically solved with time-expanded graphs.
- Published
- 2000
- Full Text
- View/download PDF
18. CLOSED FORM TWO-SIDED BOUNDS FOR PROBABILITIES THAT AT LEAST r AND EXACTLY r OUT OF n EVENTS OCCUR.
- Author
-
Boros, Endre and Prékopa, András
- Subjects
ALGORITHMS ,LINEAR programming ,PROBABILITY theory ,APPROXIMATION theory ,MATHEMATICAL optimization ,MATHEMATICAL statistics - Abstract
In two previous papers Préopa (1986a, b) gave algorithms to approximate probabilities that at least r and exactly r out of n events occur (1 ⩽ r ⩽ n). Primal and dual linear programming problems were formulated and solved by dual type algorithms. The purpose of the present paper is to give closed forms for the basis inverse and the corresponding dual vector in case of an arbitrary basis, furthermore to give closed forms for the lower and upper bounds, approximating the probability in question, in case of a dual feasible basis. In the case when the probability that at least one out of n events occurs is approximated, it is shown that the absolute values of the components of any dual vector form a monotonically decreasing sequence. The paper improves the method of inclusion-exclusion, proves new probability inequalities and proves the sharpness of some known inequalities. [ABSTRACT FROM AUTHOR]
- Published
- 1989
- Full Text
- View/download PDF
19. NESTED OPTIMAL POLICIES FOR SET FUNCTIONS WITH APPLICATIONS TO SCHEDULING.
- Author
-
Assad, Arjang A.
- Subjects
MATHEMATICAL optimization ,ALGORITHMS ,PRODUCTION scheduling ,PRODUCTION management (Manufacturing) ,OPERATIONS research ,SET functions ,DYNAMIC programming ,COMBINATORIAL optimization ,MACHINERY in the workplace ,SYSTEMS engineering - Abstract
Consider a set function v(·) defined on all subsets of a finite set N. This paper presents a class of set function maximization problems of the form Max(v(S)|S ⊆ N) that are solved optimally by the greedy algorithm. In particular, it is shown that there exists a nested sequence of subsets S[sup *, sub l] ... S[sup *, sub m] that increase to the optimal policy and S[sup *, sub k] maximizes v(S) over all subsets of cardinality k. The class is characterized by conditions on the set function v(·) and related to the notion of submodularity. These results are then applied to two order-preserving machine scheduling problems. The greedy algorithm is shown to be optimal for these problems thereby providing a new algorithm different from previous approaches based on dynamic programming. [ABSTRACT FROM AUTHOR]
- Published
- 1985
- Full Text
- View/download PDF
20. AN ALGORITHM FOR SOLVING THE GENERAL BILEVEL PROGRAMMING PROBLEM.
- Author
-
Bard, Jonathan F.
- Subjects
NONLINEAR programming ,ALGORITHMS ,MATHEMATICAL optimization ,SET theory ,MATHEMATICAL programming ,PROBLEM solving - Abstract
The conflict that naturally arises in a hierarchical system can often be modeled as a multistage optimization problem. This paper considers the sequential uncooperative problem in which two decision makers wish to maximize their own objective functions over a feasible region defined by interactive strategy sets. The resultant problem is known as the bilevel program. Such programs are inherently nonconvex and resistant to standard nonlinear programming solution techniques such as piecewise linearization and convex underestimating envelopes. Alternatively, a grid search algorithm is offered which exhibits the desirable property of monotonicity. The algorithm is based on two sets of necessary conditions previously developed and combined here to provide an operational check for stationarity and local optimality. Potential solutions are obtained from a parameterized master program whose feasible region approximates that of the original problem. As the one-dimensional parameter is varied over the unit interval and the master problem solved, a nondecreasing sequence of lower bounds to the first decision maker's objective function is produced. If the solution to the original problem is stable under small perturbations, the sequence is shown to converge to the global optimum. A discussion of the computational requirements follows the presentation of the algorithm. [ABSTRACT FROM AUTHOR]
- Published
- 1983
- Full Text
- View/download PDF
21. Refined MDP-Based Branch-and-Fix Algorithm for the Hamiltonian Cycle Problem.
- Author
-
Ejov, Vladimir, Filar, Jerzy A., Haythorpe, Michael, and Nguyen, Giang T.
- Subjects
HAMILTONIAN systems ,MARKOV processes ,ALGORITHMS ,LINEAR statistical models ,MATHEMATICAL optimization - Abstract
We consider the famous Hamiltonian cycle problem (HCP) embedded in a Markov decision process (MDP). More specifically, we consider the HCP as an optimisation problem over the space of occupation measures induced by the MDP's stationary policies. In recent years, this approach to the HCP has led to a number of alternative formulations and algorithmic approaches. In this paper, we focus on a specific embedding, because of the work of Feinberg. We present a "branch-and-fix" type algorithm that solves the HCP. At each branch of the algorithm, only a linear program needs to be solved and the dimensions of the successive linear programs are shrinking rather than expanding. Because the nodes of the branch-and-fix tree correspond to specially structured 1-randomised policies, we characterise the latter. This characterisation indicates that the total number of such policies is significantly smaller than the subset of all 1-randomised policies. Finally, we present some numerical results. [ABSTRACT FROM AUTHOR]
- Published
- 2009
- Full Text
- View/download PDF
22. Hilbert-Valued Perturbed Subgradient Algorithms.
- Author
-
Barty, Kengy, Roy, Jean-Sébastien, and Strugarek, Cyrille
- Subjects
STOCHASTIC processes ,NONSMOOTH optimization ,HILBERT algebras ,ALGORITHMS ,MARTINGALES (Mathematics) ,MATHEMATICAL optimization - Abstract
We propose a Hilbert-valued perturbed subgradient algorithm with stochastic noises, and we provide a convergence proof for this algorithm under classical assumptions on the descent direction and new assumptions on the stochastic noises. Instead of requiring the stochastic noises to correspond to martingale increments, we only require these noises to be asymptotically so. Furthermore, the variance of these noises is allowed to grow infinitely under the control of a decreasing sequence linked with the subgradient stepsizes. This algorithm can be used to solve stochastic closed-loop control problems without any a priori discretization of the uncertainty, such as linear decision rules or tree representations. It can also be used as a way to perform stochastic dynamic programming without state-space discretization or a priori functional bases (i.e., approximate dynamic programming). Both problems arise frequently--for example, in power systems scheduling or option pricing. This article focuses on the theorical foundations of the algorithm, and gives references to detailed practical experimentations. [ABSTRACT FROM AUTHOR]
- Published
- 2007
- Full Text
- View/download PDF
23. Convergence to Second-Order Stationary Points of a Primal-Dual Algorithm Model for Nonlinear Programming.
- Author
-
Di Pillo, Gianni, Lucidi, Stefano, and Palagi, Laura
- Subjects
ALGORITHMS ,MATHEMATICAL inequalities ,MATHEMATICAL optimization ,LAGRANGIAN functions ,CALCULUS of variations - Abstract
We define a primal-dual algorithm model (second-order Lagrangian algorithm, SOLA) for inequality constrained optimization problems that generates a sequence converging to points satisfying the second-order necessary conditions for optimality. This property can be enforced by combining the equivalence between the original constrained problem and the unconstrained minimization of an exact augmented Lagrangian function and the use of a curvilinear line search technique that exploits information on the nonconvexity of the augmented Lagrangian function. [ABSTRACT FROM AUTHOR]
- Published
- 2005
- Full Text
- View/download PDF
24. AN INTERIOR-POINT PERSPECTIVE ON SENSITIVITY ANALYSIS IN SEMIDEFINITE PROGRAMMING.
- Author
-
Yildirim, E. A.
- Subjects
SENSITIVITY theory (Mathematics) ,ALGORITHMS ,MATHEMATICAL optimization ,MATRICES (Mathematics) ,PERTURBATION theory ,MATHEMATICAL programming ,OPERATIONS research - Abstract
We study the asymptotic behavior of the interior-point bounds arising from the work of Yildirim and Todd on sensitivity analysis in semidefinite programming in comparison with the optimal partition bounds. We introduce a weaker notion of nondegeneracy and discuss its implications. For perturbations of the right-hand-side vector or the cost matrix, we show that the interior-point bounds evaluated on the central path using the Monteiro-Zhang family of search directions converge (as the duality gap tends to zero) to the symmetrized version of the optimal partition bounds under mild nondegeneracy assumptions. Furthermore, our analysis does not assume strict complementarity as long as the central path converges to the analytic center in a relatively controlled manner. We also show that the same convergence results carry over to iterates lying in an appropriate (very narrow) central path neighborhood if the Nesterov-Todd direction is used to evaluate the interior- point bounds. We extend our results to the case of simultaneous perturbations of the right-hand-side vector and the cost matrix. We also provide examples illustrating that our assumptions, in general, cannot be weakened. [ABSTRACT FROM AUTHOR]
- Published
- 2003
25. ON THE CONVERGENCE OF ALGORITHMS WITH IMPLICATIONS FOR STOCHASTIC AND NONDIFFERENTIABLE OPTIMIZATION.
- Author
-
Higle, Julia L. and Sen, Suvrajeet
- Subjects
STOCHASTIC convergence ,ALGORITHMS ,MATHEMATICAL functions ,MATHEMATICAL analysis ,MATHEMATICAL optimization ,DIFFERENTIAL equations ,OPERATIONS research ,SIMULATION methods & models - Abstract
Studies of the convergence of algorithms often revolve around the existence of a function with respect to which monotonic descent is required. In this paper, we show that under relatively lenient conditions, "stage-dependent descent" (not necessarily monotonic) is sufficient to guarantee convergence. This development also provides the impetus to examine optimization algorithms. We show that one of the important avenues in the study of convergence, namely, the theory of epi-convergence imposes stronger conditions than are necessary to establish the convergence of an optimization algorithm. Working from a relaxation of epi-convergence, we introduce the notion of ∂-compatibility, and prove several results that permit relaxations of conditions imposed by previous approaches to algorithmic convergence. Finally, to illustrate the usefulness of the concepts, we combine stage-dependent descent with results derivable from ∂-compatibility to provide a basis for the convergence of a general algorithmic statement that might be used for stochastic and nondifferentiable optimization. [ABSTRACT FROM AUTHOR]
- Published
- 1992
- Full Text
- View/download PDF
26. SCENARIOS AND POLICY AGGREGATION IN OPTIMIZATION UNDER UNCERTAINTY.
- Author
-
Rockafellar, R. T. and Wets, Roger J. -B.
- Subjects
MATHEMATICAL models of decision making ,MATHEMATICAL optimization ,ALGORITHMS ,STOCHASTIC programming ,ITERATIVE methods (Mathematics) ,PROBABILITY theory ,OPERATIONS research - Abstract
A common approach in coping with multiperiod optimization problems under uncertainty where statistical information is not really enough to support a stochastic programming model, has been to set up and analyze a number of scenarios. The aim then is to identify trends and essential features on which a robust decision policy can be based. This paper develops for the first time a rigorous algorithmic procedure for determining such a policy in response to any weighting of the scenarios. The scenarios are bundled at various levels to reflect the availability of information, and iterative adjustments are made to the decision policy to adapt to this structure and remove the dependence on hindsight. [ABSTRACT FROM AUTHOR]
- Published
- 1991
- Full Text
- View/download PDF
27. MINIMIZING TOTAL TARDINESS ON ONE MACHINE IS NP-HARD.
- Author
-
Du, Jianzhong and Leung, Joseph Y. -T.
- Subjects
MACHINERY ,PROBLEM solving ,PRODUCTION control ,POLYNOMIALS ,OPERATIONS research ,ALGORITHMS ,MATHEMATICS ,MATHEMATICAL optimization ,MAXIMA & minima - Abstract
The problem of minimizing the total tardiness for a set of independent jobs on one machine is considered. Lawler has given a pseudo-polynomial-time algorithm to solve this problem. In spite of extensive research efforts for more than a decade, the question of whether it can be solved in polynomial time or it is NP-hard (in the ordinary sense) remained open. In this paper the problem is shown to be NP-hard (in the ordinary sense). [ABSTRACT FROM AUTHOR]
- Published
- 1990
- Full Text
- View/download PDF
28. OPTIMAL ASSIGNMENT OF COMPONENTS TO A TWO-STAGE k-OUT-OF-n SYSTEM.
- Author
-
Hwang, F. K.
- Subjects
RELIABILITY in engineering ,MATHEMATICAL optimization ,PROBABILITY theory ,HEURISTIC ,ALGORITHMS ,DYNAMIC programming ,MATHEMATICAL programming - Abstract
A two-stage k-out-of-n system is an l-out-of-m system except that each of the m parts is itself a k
i -out-of-ni system. The problem is to assign a set of Σi=1 m ni probabilities to the Σi=1 m ni components in the system to maximize its reliability. In this paper we consider the case ki = k for all i. We give optimal assignments when the first stage is a parallel system or the second stage is a series system. We conjecture that the optimal assignment problems for all other two-stage k-out-of-n system are NP-complete, but we are able to prove this only when the second stage is a parallel system. We also propose a heuristic assignment algorithm for the general case. [ABSTRACT FROM AUTHOR]- Published
- 1989
- Full Text
- View/download PDF
29. EXPONENTIAL LOWER BOUNDS ON A CLASS OF KNAPSACK ALGORITHMS.
- Author
-
Hausmann, Dirk, Kannan, Ravindran, and Korte, Bernhard
- Subjects
ALGORITHMS ,KNAPSACK problems ,MATHEMATICAL optimization - Abstract
The O-1 knapsack problem is a well known NP-hard optimization problem. The proof of the generally believed hypothesis that there is no polynomial optimization algorithm for this problem ,would settle the famous NP ≠ P question. We show here the nonexistence of a polynomial knapsack algorithm within the class of algorithms having restricted access to the input. Algorithms for the problem max{c(S): a(S) < b,, S ⊆ E[subn] ) that can only check the sign of a(S) - b cannot have a better performance guarantee: than the greedy algorithm; furthermore even if they can exploit the order of the densities c[subj]/a[subj] 1≤i≤n, or of the weights a(S), S C_ Eh, they cannot be guaranteed to find the optimum. [ABSTRACT FROM AUTHOR]
- Published
- 1981
- Full Text
- View/download PDF
30. CONSTRAINED DISCOUNTED DYNAMIC PROGRAMMING.
- Author
-
Feinberg, Eugene A. and Shwartz, Adam
- Subjects
MARKOV processes ,STATISTICAL correlation ,DYNAMIC programming ,MATHEMATICAL optimization ,ALGORITHMS ,SYSTEMS engineering - Abstract
This paper deals with constrained optimization of Markov Decision Processes with a countable state space, compact action sets, continuous transition probabilities, and upper semicontinuous reward functions. The objective is to maximize the expected total discounted reward for one reward function, under several inequality constraints on similar criteria with other reward functions. Suppose a feasible policy exists for a problem with M constraints. We prove two results on the existence and structure of optimal policies. First, we show that there exists a randomized stationary optimal policy which requires at most M actions more than a nonrandomized stationary one. This result is known for several particular cases. Second, we prove that there exists an optimal policy which is (i) stationary (nonrandomized) from some step onward, (ii) randomized Markov before this step, but the total number of actions which are added by randomization is at most M, (iii) the total number of actions that are added by nonstationarity is at most M. We also establish Pareto optimality of policies from the two classes described above for multi-criteria problems. We describe an algorithm to compute optimal policies with proper- ties (O-(iii) for constrained problems. The policies that satisfy properties (i)-(iii) have the pleasing aesthetic property that the amount of randomization they require over any trajectory is restricted by the number of constraints. In contrast, a randomized stationary policy may require an infinite number of randomizations over time. [ABSTRACT FROM AUTHOR]
- Published
- 1996
- Full Text
- View/download PDF
31. Convergence Analysis of Stochastic Algorithms.
- Author
-
Shapiro, A. and Wardi, Y.
- Subjects
NONLINEAR programming ,ALGORITHMS ,STOCHASTIC convergence ,MATHEMATICAL optimization ,DYNAMIC programming ,MONTE Carlo method ,CONJUGATE gradient methods ,LINEAR programming - Abstract
This paper investigates asymptotic convergence to stationary points of gradient descent algorithms where the functions involved are not available in closed form but are approximated by sequences of random functions. The algorithms take large stepsizes and use progressively finer precision at successive iterations. Two kinds of optimization algorithms are considered: one, where the limiting function (to be minimized) is differentiable but the random approximating functions can be nondifferentiable, and the other, where both the limiting and approximating functions are nondifferentiable and convex. Such functions often arise in discrete event dynamic system-models in various application areas. The analysis brings together ideas and techniques from the disciplines of nonlinear programming and nondifferentiable optimization on one hand, and stochastic processes and especially uniform laws of large numbers, on the other hand. A general algorithmic frame- work is first developed and analyzed, and then applied to the specific algorithms considered. The analysis extends the results derived to date for similar algorithms, and has a potential for further extensions in proving convergence of other algorithms as well. [ABSTRACT FROM AUTHOR]
- Published
- 1996
- Full Text
- View/download PDF
32. A Faster Combinatorial Algorithm for the Generalized Circulation Problem.
- Author
-
Goldfarb, Donald and Zhiying Jin
- Subjects
COMBINATORIAL optimization ,ALGORITHMS ,COMBINATORICS ,COMBINATORIAL geometry ,MATHEMATICAL optimization ,ALGEBRA - Abstract
This paper presents a modified version of Algorithm MCF proposed by Goldberg, Plotkin and Tardos for the generalized circulation problem. This new combinatorial algorithm has a worst-case complexity that is better than the complexities of the MCF and Fat-Path combinatorial algorithms of Goldberg, Plotkin, and Tardos (1991). [ABSTRACT FROM AUTHOR]
- Published
- 1996
- Full Text
- View/download PDF
33. Coordination Complexity of Parallel Price-Directive Decomposition.
- Author
-
Grigoriadis, Michael D. and Khachiyan, Leonid G.
- Subjects
ALGORITHMS ,MATHEMATICAL decomposition ,MATHEMATICAL optimization ,INDUSTRIAL design ,ENGINEERING design ,TECHNOLOGY ,PROGRESS reports - Abstract
The general block-angular convex resource sharing problem in K blocks and M nonnegative block-separable coupling constraints is considered. Applications of this model are in combinatorial optimization, network flows, scheduling, communication networks, engineering design, and finance. This paper studies the coordination complexity of approximate price- directive decomposition (PDD) for this problem, i.e., the number of iterations required to solve the problem to a fixed relative accuracy as a function of K and M. First a simple PDD method based on the classical logarithmic potential is shown to be optimal up to a logarithmic factor in M in the class of all PDD methods that work with the original (unrestricted) blocks. It is then shown that logarithmic and exponential potentials generate a polylogarithmically-optimal algorithm for a wider class of PDD methods which can restrict the blocks by the coupling constraints. As an application, the fastest currently-known deterministic approximation algorithm for minimum-cost multicommodity flows is obtained. [ABSTRACT FROM AUTHOR]
- Published
- 1996
- Full Text
- View/download PDF
34. Second-order Sufficiency and Quadratic Growth for Nonisolated Mimima.
- Author
-
Bonnans, Joseph Frédéric and Ioffe, Alexander
- Subjects
NONLINEAR programming ,CALCULUS of variations ,MATHEMATICAL optimization ,MAXIMA & minima ,REASONING ,ALGORITHMS - Abstract
For standard nonlinear programming problems, the weak second-order sufficient condition is equivalent to the quadratic growth condition as far as the set of minima consists of isolated points and some qualification hypothesis holds. This kind of condition is instrumental in the study of numerical algorithms and sensitivity analysis. The aim of the paper is to study the relations between various types of sufficient conditions and quadratic growth in cases when the set of minima may have nonisolated points. [ABSTRACT FROM AUTHOR]
- Published
- 1995
- Full Text
- View/download PDF
35. Projection: A Unified Approach to Semi-Infinite Linear Programs and Duality in Convex Programming.
- Author
-
Basu, Amitabh, Martin, Kipp, and Ryan, Christopher Thomas
- Subjects
LINEAR programming ,CONVEX programming ,ALGORITHMS ,EXISTENCE theorems ,MATHEMATICAL optimization - Abstract
Fourier-Motzkin elimination is a projection algorithm for solving finite linear programs. We extend Fourier-Motzkin elimination to semi-infinite linear programs, which are linear programs with finitely many variables and infinitely many constraints. Applying projection leads to new characterizations of important properties for primal-dual pairs of semi-infinite programs such as zero duality gap, feasibility, boundedness, and solvability. Extending the Fourier-Motzkin elimination procedure to semi-infinite linear programs yields a new classification of variables that is used to determine the existence of duality gaps. In particular, the existence of what the authors term dirty variables can lead to duality gaps. Our approach has interesting applications in finite-dimensional convex optimization. For example, sufficient conditions for a zero duality gap, such as the Slater constraint qualification, are reduced to guaranteeing that there are no dirty variables. This leads to completely new proofs of such sufficient conditions for zero duality. [ABSTRACT FROM AUTHOR]
- Published
- 2015
- Full Text
- View/download PDF
36. The Maximum Multiflow Problems with Bounded Fractionality.
- Author
-
Hirai, Hiroshi
- Subjects
BOUNDED arithmetics ,EULERIAN graphs ,MATHEMATICAL optimization ,POLYNOMIALS ,ALGORITHMS - Abstract
We consider the weighted maximum multiflow problem with respect to a terminal weight. We show that if the dimension of the tight span associated with the weight is at most 2, then this problem has a 1/12-integral optimal multiflow for every Eulerian supply graph. This result solves a weighted generalization of Karzanovˌs conjecture for classifying commodity graphs with finite fractionality. In addition, our proof technique proves the existence of an integral or half-integrality optimal multiflow for a large class of multiflow maximization problems, and it gives a polynomial time algorithm. [ABSTRACT FROM AUTHOR]
- Published
- 2014
- Full Text
- View/download PDF
37. Generic Optimality Conditions for Semi-Algebraic Convex Programs.
- Author
-
Bolte, Jérôme, Daniilidis, Aris, and Lewis, Adrian S.
- Subjects
ALGORITHMS ,MATHEMATICAL optimization ,CONVEX programming ,PERTURBATION theory ,ITERATIVE methods (Mathematics) - Abstract
We consider linear optimization over a nonempty convex semialgebraic feasible region F. Semidefinite programming is an example. If F is compact, then for almost every linear objective there is a unique optimal solution, lying on a unique "active" manifold, around which F is "partly smooth," and the second-order sufficient conditions hold. Perturbing the objective results in smooth variation of the optimal solution. The active manifold consists, locally, of these perturbed optimal solutions; it is independent of the representation of F and is eventually identified by a variety of iterative algorithms such as proximal and projected gradient schemes. These results extend to unbounded sets F. [ABSTRACT FROM AUTHOR]
- Published
- 2011
- Full Text
- View/download PDF
38. On the Closedness of the Linear Image of a Closed Convex Cone.
- Author
-
Pataki, Gábor
- Subjects
LINEAR statistical models ,LINEAR systems ,ALGORITHMS ,CONVEX functions ,MATHEMATICAL models ,MATHEMATICAL optimization - Abstract
When is the linear image of a closed convex cone closed? We present very simple and intuitive necessary conditions that (1) unify, and generalize seemingly disparate, classical sufficient conditions such as polyhedrality of the cone, and Slater-type conditions; (2) are necessary and sufficient, when the dual cone belongs to a class that we call nice cones (nice cones subsume all cones amenable to treatment by efficient optimization algorithms, for instance, polyhedral, semidefinite, and p-cones); and (3) provide similarly attractive conditions for an equivalent problem: the closedness of the sum of two closed convex cones. [ABSTRACT FROM AUTHOR]
- Published
- 2007
- Full Text
- View/download PDF
39. An Efficient Interior-Point Method for Convex Multicriteria Optimization Problems.
- Author
-
Fliege, Jörg
- Subjects
MATHEMATICAL optimization ,MATHEMATICAL analysis ,CONVEX functions ,REAL variables ,ALGORITHMS - Abstract
In multicriteria optimization, several objective functions have to be minimized simultaneously. We propose a new efficient method for approximating the solution set of a multicriteria optimization problem, where the objective functions involved are arbitrary convex functions and the set of feasible points is convex. The method is based on generating warm-start points for an efficient interior-point algorithm, while the approximation computed consists of a finite set of discrete points. Polynomial-time complexity results for the method proposed are derived. In these estimates, the number of operations per point decreases when the number of points generated for the approximation increases. This reduced theoretical complexity estimate is a novel feature and is not observed in standard solution techniques for multicriteria optimization problems. [ABSTRACT FROM AUTHOR]
- Published
- 2006
- Full Text
- View/download PDF
40. Simulated Annealing for Convex Optimization.
- Author
-
Kalai, Adam Tauman and Vempala, Santosh
- Subjects
MATHEMATICAL optimization ,CONVEX sets ,ALGORITHMS ,MATHEMATICS ,MATHEMATICAL analysis - Abstract
We apply the method known as simulated annealing to the following problem in convex optimization: Minimize a linear function over an arbitrary convex set, where the convex set is specified only by a membership oracle. Using distributions from the Boltzmann-Gibbs family leads to an algorithm that needs only O
* (√n) phases for instances in ℝn . This gives an optimization algorithm that makes O* (n4.5 ) calls to the membership oracle, in the worst case, compared to the previous best guarantee of O* (n5 ). The benefits of using annealing here are surprising because such problems have no local minima that are not also global minima. Hence, we conclude that one of the advantages of simulated annealing, in addition to avoiding poor local minima, is that in these problems it converges faster to the minima that it finds. We also give a proof that under certain general conditions, the Boltzmann-Gibbs distributions are optimal for annealing on these convex problems. [ABSTRACT FROM AUTHOR]- Published
- 2006
- Full Text
- View/download PDF
41. Integer Polynomial Optimization in Fixed Dimension.
- Author
-
De Loera, Jesús A., Hemmecke, Raymond, Köppe, Matthias, and Weismantel, Robert
- Subjects
COMPUTATIONAL complexity ,MATHEMATICAL optimization ,POLYNOMIALS ,CONVEX polytopes ,ALGORITHMS - Abstract
We classify, according to their computational complexity, integer optimization problems whose constraints and objective functions are polynomials with integer coefficients, and the number of variables is fixed. For the optimization of an integer polynomial over the lattice points of a convex polytope, we show an algorithm to compute lower and upper bounds for the optimal value. For polynomials that are nonnegative over the polytope, these sequences of bounds lead to a fully polynomial-time approximation scheme for the optimization problem. [ABSTRACT FROM AUTHOR]
- Published
- 2006
- Full Text
- View/download PDF
42. On Hochbaum's Proximity-Scaling Algorithm for the General Resource Allocation Problem.
- Author
-
Moriguchi, Satoko and Shioura, Akiyoshi
- Subjects
RESOURCE allocation ,ALGORITHMS ,MATHEMATICAL optimization ,COMBINATORIAL optimization ,MATHEMATICAL analysis - Abstract
It is pointed out that the polynomial-time scaling algorithm by Hochbaum does not work correctly for the general resource allocation problem. Hochbaum's algorithm increases a variable by one unit if the variable cannot feasibly be increased by the scaling unit. We modify the algorithm to increase such a variable by the largest possible amount and show that with this modification the algorithm works correctly. The effect is to modify the factor F in the running time of Hochbaum's algorithm for finding whether a certain solution is feasible by the factor F of finding the maximum feasible increment (also called the saturation capacity). Therefore, the corrected algorithm runs in O (n(log n + F) log B/n)) time. [ABSTRACT FROM AUTHOR]
- Published
- 2004
- Full Text
- View/download PDF
43. THE COMPLEXITY OF DECENTRALIZED CONTROL OF MARKOV DECISION PROCESSES.
- Author
-
Bernstein, Daniel S., Givan, Robert, Immerman, Neil, and Zilberstein, Shlomo
- Subjects
MARKOV processes ,NUMERICAL solutions for Markov processes ,ALGORITHMS ,DECISION making ,MATHEMATICAL optimization ,COMPUTATIONAL complexity ,POLYNOMIALS ,FINITE groups - Abstract
We consider decentralized control of Markov decision processes and give complexity bounds on the worst-case running time for algorithms that find optimal solutions. Generalizations of both the fully observable case and the partially observable case that allow for decentralized control are described. For even two agents, the finite-horizon problems corresponding to both of these models are hard for nondeterministic exponential time. These complexity results illustrate a fundamental difference between centralized and decentralized control of Markov decision processes. In contrast to the problems involving centralized control, the problems we consider provably do not admit polynomial-time algorithms. Furthermore, assuming EXP ≠ NEXP, the problems require superexponential time to solve in the worst case. [ABSTRACT FROM AUTHOR]
- Published
- 2002
- Full Text
- View/download PDF
44. ASSOCIATIVE AND JORDAN ALGEBRAS, AND POLYNOMIAL TIME INTERIOR-POINT ALGORITHMS FOR SYMMETRIC CONES.
- Author
-
Schmieta, S. H. and Alizadeh, F.
- Subjects
ALGORITHMS ,SYMMETRIC matrices ,ABSTRACT algebra ,JORDAN algebras ,CLIFFORD algebras ,LINEAR algebra ,MATHEMATICAL optimization - Abstract
We present a general framework whereby analysis of interior-point algorithms for semidefinite programming can be extended verbatim to optimization problems over all classes of symmetric cones derivable from associative algebras. In particular, such analyses are extendible to the cone of positive semidefinite Hermitian matrices with complex and quaternion entries, and to the Lorentz cone. We prove the case of the Lorentz cone by using the embedding of its associated Jordan algebra in the Clifford algebra. As an example of such extensions we take Monterio's polynomial-time complexity analysis of the family of similarly scaled directions - introduced by Monteiro and Zhang (1998) - and generalize it to cone-LP over all representable symmetric cones. [ABSTRACT FROM AUTHOR]
- Published
- 2001
- Full Text
- View/download PDF
45. ON THE WAGNER-WHITIN LOT-SIZING POLYHEDRON.
- Author
-
Pereira, Olivier and Wolsey, Laurence
- Subjects
ECONOMIC lot size ,POLYHEDRA ,INVENTORY control ,MAXIMAL functions ,ALGORITHMS ,DYNAMIC programming ,MATHEMATICAL optimization ,MATHEMATICAL programming ,MATHEMATICAL analysis - Abstract
We study a family of unbounded polyhedra arising in the study of uncapacitated lot-sizing problems with Wagner-Whitin costs. We present a new proof of integrality based on completely characterizing the bounded faces of maximal dimension,and in particular showing that they are integral. With n the number of periods, we derive an O(n[sup2]) algorithm to express any point within the polyhedron as a convex combination of extreme points and extreme rays. We also study adjacency on the polyhedra, and give a simple O(n) test for adjacency. Finally we observe that for a given objective function the face of optimal solutions can be found in O(n[sup2])/. [ABSTRACT FROM AUTHOR]
- Published
- 2001
- Full Text
- View/download PDF
46. Mean cost cyclical games.
- Author
-
Pisaruk, N. N.
- Subjects
GAME theory ,COMBINATORIAL optimization ,ALGORITHMS ,MATHEMATICAL optimization ,MATHEMATICAL models ,MATHEMATICAL functions - Abstract
This article studies the mean cost cyclical game in a more general setting than that in the study by V.A. Gurvich and colleagues, and A.V. Karzanow and V.N. Lebedev. The game is played on a directed graph and generalizes the single source shortest path problem, the minimum mean cycle problem, and the ergodic extension of matrix games. The article proves the existence of a solution in uniform stationary strategies and present an algorithm for finding such optimal strategies. Let G = (V,E) be a directed graph with vertex set V containing v vertices and arc set E containing m arcs. It is assumed that G may have loops but has no multiple arcs and dead ends, i.e., vertices without leaving arcs. These assumptions are introduced for notational convenience only. F(v) may be exponentially large in d(v). In interesting applications, however, F(v) is usually described combinatorially and can be given by use of an efficient membership procedure, e.g., when F(v) is given by a system of linear inequalities. The players have complete information about all moves and the game lasts infinitely long. The payoff function f(c,P) depends on the cost function.
- Published
- 1999
- Full Text
- View/download PDF
47. THE FAIR RESOURCE ALLOCATION PROBLEM WITH SUBMODULAR CONSTRAINTS.
- Author
-
Fujishige, Satoru, Katoh, Naoki, and Ichimori, Tetsuo
- Subjects
RESOURCE allocation ,MATHEMATICAL optimization ,ALGORITHMS - Abstract
Presents an algorithm for the problem of allocating a limited resource to relevant activities in a fair manner on the basis of a general objective function. Background on the generalization of allocation problems with submodular constraints; Characterization of optimal solutions; Details on the algorithm.
- Published
- 1988
- Full Text
- View/download PDF
48. ON SHORTEST PATHS IN GRAPHS WITH RANDOM WEIGHTS .
- Author
-
Hassin, Refeal and Zemel, Eitan
- Subjects
RANDOM graphs ,PATH analysis (Statistics) ,ALGORITHMS ,GRAPH theory ,MATHEMATICAL optimization ,DISTANCES ,PROBABILITY theory ,OPERATIONS research ,DISTRIBUTION (Probability theory) - Abstract
We consider the shortest paths between all pairs of nodes in a directed or undirected complete graph with edge lengths which are uniformly and independently distributed in [0, 1]. We show that the longest of these paths is bounded by c log n/n almost surely, where c is a constant and n is the number of nodes. Our bound is the best possible up to a constant. We apply this result to some well-known problems and obtain several algorithmic improvements over existing results. Our results hold with obvious modifications to random (as opposed to complete) graphs and to any distribution of weights whose density is positive and bounded from below at a neighborhood of zero. As a corollary of our proof we get a new result concerning the diameter of random graphs. [ABSTRACT FROM AUTHOR]
- Published
- 1985
- Full Text
- View/download PDF
49. ADDENDUM: A FINITE ALGORITHM FOR SOLVING NONLINEAR ALLOCATION PROBLEMS.
- Author
-
Einbu, John M.
- Subjects
RESOURCE allocation ,ALGORITHMS ,CONVEX programming ,MATHEMATICAL programming ,NONLINEAR theories ,MATHEMATICAL optimization ,MATHEMATICS ,OPERATIONS research ,RESOURCE management - Abstract
This note communicates two improvements to a finite allocation algorithm previously reported. The algorithm yields exact solutions to multi-resource allocation problems which have concave return functions. The first improvement permits one of the conditions on the return functions to be relaxed and the second improvement speeds up one of the steps of the algorithm. [ABSTRACT FROM AUTHOR]
- Published
- 1985
- Full Text
- View/download PDF
50. A FAST ALGORITHM FOR THE DECOMPOSITION OF GRAPHS AND POSETS.
- Author
-
Buer, Hermann and Möhring, Rolf H.
- Subjects
COMBINATORICS ,GRAPH theory ,ALGORITHMS ,MATHEMATICAL functions ,MATHEMATICAL optimization ,GRAPHIC methods - Abstract
Many combinatorial (optimization) problems of graphs (e.g., finding maximal independent sets or maximum matchings) and acyclic networks (e.g., finding shortest paths or maximum flows) can be solved by means of decomposition of the graph (network) into autonomous subsets. (Given a relation R on A, a subset B of A is called autonomous, if for each a α ∈ A\ B the following holds: (i)if (α, β[sub0])) ∈ R for some β[sub0] ∈- B, then (α β ∈) R for all &beta ; ∈ B; (ii)if ( β[sub0], α) ∈ R for some β[sub0] ∈, then (β, α) ∈ R for all β &isin B). We present an algorithm which finds all autonomous subsets of graphs and posers with p points in O(ρ³) time and O(ρ²) space. The ideas behind this algorithm reveal rather strong connections between graph decomposition, homomorphisms of graphs and posets, and comparability graph recognition. Furthermore, the well-known series-parallel decomposition for graphs and posers is contained as a special case. [ABSTRACT FROM AUTHOR]
- Published
- 1983
- Full Text
- View/download PDF
Discovery Service for Jio Institute Digital Library
For full access to our library's resources, please sign in.