Effective optimization with weighted automata on decomposable trees

Date

2014-01-02

Author

Ravve, E. V.
Volkovich, Z.
Weber, Gerhard Wilhelm

Metadata

Show full item record

This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

Item Usage Stats

235
views

0
downloads

In this paper, we consider quantitative optimization problems on decomposable discrete systems. We restrict ourselves to labeled trees as the description of the systems and we use weighted automata on them as our computational model. We introduce a new kind of labeled decomposable trees, sum-like weighted labeled trees, and propose a method, which allows us to reduce the solution of an optimization problem, defined in a fragment of Weighted Monadic Second Order Logic, on such a tree to the solution of effectively derived problems, defined in the same logic, on its components with some additional post-processing. The approach originates from a method, proposed first by Feferman and Vaught in 1959, which we adapt and generalize. We adapt the method to the case of (fragments of) Weighted Monadic Second Order Logic and generalize it to the case of sum-like labeled trees rather than disjoint union and product. The main result of the paper may be applied in the wide range of optimization problems, such as critical path analysis or project planning, network optimization, generalized assignment problem, routing and scheduling as well as in the modern document languages like XML, image processing and compression, probabilistic systems or speech-to-text processing.

Subject Keywords

Management Science and Operations Research, Control and Optimization, Applied Mathematics

URI

https://hdl.handle.net/11511/52390

Journal

OPTIMIZATION

DOI

https://doi.org/10.1080/02331934.2013.865735

Collections

Graduate School of Applied Mathematics, Article

Suggestions

OpenMETU
Core

A new multiobjective simulated annealing algorithm Tekinalp, Ozan (Springer Science and Business Media LLC, 2007-09-01) A new multiobjective simulated annealing algorithm for continuous optimization problems is presented. The algorithm has an adaptive cooling schedule and uses a population of fitness functions to accurately generate the Pareto front. Whenever an improvement with a fitness function is encountered, the trial point is accepted, and the temperature parameters associated with the improving fitness functions are cooled. Beside well known linear fitness functions, special elliptic and ellipsoidal fitness functions,...
Neural network calibrated stochastic processes: forecasting financial assets Giebel, Stefan; Rainer, Martin (Springer Science and Business Media LLC, 2013-03-01) If a given dynamical process contains an inherently unpredictable component, it may be modeled as a stochastic process. Typical examples from financial markets are the dynamics of prices (e.g. prices of stocks or commodities) or fundamental rates (exchange rates etc.). The unknown future value of the corresponding stochastic process is usually estimated as the expected value under a suitable measure, which may be determined from distribution of past (historical) values. The predictive power of this estimati...
Multi-objective integer programming: A general approach for generating all non-dominated solutions Oezlen, Melih; Azizoğlu, Meral (Elsevier BV, 2009-11-16) In this paper we develop a general approach to generate all non-dominated solutions of the multi-objective integer programming (MOIP) Problem. Our approach, which is based on the identification of objective efficiency ranges, is an improvement over classical epsilon-constraint method. Objective efficiency ranges are identified by solving simpler MOIP problems with fewer objectives. We first provide the classical epsilon-constraint method on the bi-objective integer programming problem for the sake of comple...
Optimal lot-sizing/vehicle-dispatching policies under stochastic lead times and stepwise fixed costs Alp, O; Erkip, NK; Gullu, R (Institute for Operations Research and the Management Sciences (INFORMS), 2003-01-01) We characterize optimal policies of a dynamic lot-sizing/vehicle-dispatching problem under dynamic deterministic demands and stochastic lead times. An essential feature of the problem is the structure of the ordering cost, where a fixed cost is incurred every time a batch is initiated (or a vehicle is hired) regardless of the portion of the batch (or vehicle) utilized. Moreover, for every unit of demand not satisfied on time, holding and backorder costs are incurred. Under mild assumptions we show that the ...
The semismooth approach for semi-infinite programming under the Reduction Ansatz Stein, Oliver; Tezel, Aysun (Springer Science and Business Media LLC, 2008-06-01) We study convergence of a semismooth Newton method for generalized semi-infinite programming problems with convex lower level problems where, using NCP functions, the upper and lower level Karush-Kuhn-Tucker conditions of the optimization problem are reformulated as a semismooth system of equations. Nonsmoothness is caused by a possible violation of strict complementarity slackness. We show that the standard regularity condition for convergence of the semismooth Newton method is satisfied under natural assu...

Citation Formats

E. V. Ravve, Z. Volkovich, and G. W. Weber, “Effective optimization with weighted automata on decomposable trees,” OPTIMIZATION, pp. 109–127, 2014, Accessed: 00, 2020. [Online]. Available: https://hdl.handle.net/11511/52390.