Robust optimization is still a relatively new approach to optimization problems affected by uncertainty, but it has already proved so useful in real applications that it is difficult to tackle such ...problems today without considering this powerful methodology. Written by the principal developers of robust optimization, and describing the main achievements of a decade of research, this is the first book to provide a comprehensive and up-to-date account of the subject. Robust optimization is designed to meet some major challenges associated with uncertainty-affected optimization problems: to operate under lack of full information on the nature of uncertainty; to model the problem in a form that can be solved efficiently; and to provide guarantees about the performance of the solution.
This paper deals with the solvability of interval matrix equations in max-plus algebra. Max-plus algebra is the algebraic structure in which classical addition and multiplication are replaced by ⊕ ...and ⊗, where a⊕b=max{a,b} and a⊗b=a+b.
The notation A⊗X⊗C=B represents an interval max-plus matrix equation, where A, B, and C are given interval matrices. We define four types of solvability of interval max-plus matrix equations, i.e., the tolerance, weak tolerance, left-weak tolerance, and right-weak tolerance solvability. We derive the necessary and sufficient conditions for checking each of them, whereby all can be verified in polynomial time.
The objective of this paper is to propose a filtering strategy for max-plus linear systems with bounded disturbances without the direct calculation of the a posteriori state probability. The strategy ...is based on the inversion of the expectation of the measure with respect to the state variable. Among the possible solutions, the closest to the prediction is chosen. An algorithm, based on interval propagation, is proposed to solve this problem. Simulations are performed to show the consistence of the proposed methodology with other approaches in the literature.
A class of timed discrete event systems can be modeled by using Timed-Event Graphs, a class of timed Petri nets that can have its firing dynamic described by using an algebra called “Max-plus ...algebra”. For this kind of systems it may be desirable to enforce some timing constraints in steady state. In this paper, this problem is called a “max-plus regulation problem”. In this context we show a necessary condition for solving these regulation problems and in addition that this condition is sufficient for a large class of problems. The obtained controller is a simple linear static state feedback and can be computed using efficient pseudo-polynomial algorithms. Simulation results will illustrate the applicability of the proposed methodology.
Highspeed rail (HSR) has formed a networked operational scale in China. Any internal or external disturbance may deviate trains' operation from the planned schedules, resulting in primary delays or ...even cascading delays on a network scale. Studying the delay propagation mechanism could help to improve the timetable resilience in the planning stage and realize cooperative rescheduling for dispatchers. To quickly and effectively predict the spatial-temporal range of cascading delays, this paper proposes a max-plus algebra based delay propagation model considering trains' operation strategy and the systems' constraints. A double-layer network based breadth-first search algorithm based on the constraint network and the timetable network is further proposed to solve the delay propagation process for different kinds of emergencies. The proposed model could deal with the delay propagation problem when emergencies occur in sections or stations and is suitable for static emergencies and dynamic emergencies. Case studies show that the proposed algorithm can significantly improve the computational efficiency of the large-scale HSR network. Moreover, the real operational data of China HSR is adopted to verify the proposed model, and the results show that the cascading delays can be timely and accurately inferred, and the delay propagation characteristics under three kinds of emergencies are unfolded.
•Interval eigenvectors of interval matrices corresponding to steady states of systems with inexact data are investigated.•Tolerable, strongly tolerable and weakly tolerable interval eigenvectors are ...described.•Polynomial solutions to the recognition versions of all three types of tolerability are presented.
Max-plus algebra plays a key role in the study of discrete event systems in connection with optimization problems such as scheduling or project management in which the objective function depends on the operations maximum and plus. The steady states of such systems correspond to the eigenvectors of max-plus matrices, therefore the investigation of the properties of these eigenvectors is important for applications.
Matrices and vectors with interval coefficients in a max-plus algebra are studied in this paper, and polynomial algorithms are presented for the recognition problem with three types of tolerance interval eigenvector.
An exponent matrix is an n×n matrix A=(aij) over N0 satisfying (1) aii=0 for all i=1,…,n and (2) aij+ajk≥aik for all pairwise distinct i,j,k∈{1,…,n}. In the present paper we study the set En of all ...non-negative n×n exponent matrices as an algebra with the operations ⊕ of component-wise maximum and ⊙ of component-wise addition. We provide a basis of the algebra (En,⊕,⊙,0) and give a row and a column decompositions of a matrix A∈En with respect to this basis. This structure result determines all n×n-tiled orders over a fixed discrete valuation domain. We also study automorphisms of En with respect to each of the operations ⊕ and ⊙ and prove that Aut(En,⊕,⊙,0)≅Aut(En,⊕)≅Aut(En,⊙)≅Sn×C2, n>2.
The basic filters in mathematical morphology are dilation and erosion. They are defined by a structuring element that is usually shifted pixel-wise over an image, together with a comparison process ...that takes place within the corresponding mask. This comparison is made in the grey value case by means of maximum or minimum formation. Hence, there is easy access to max-plus algebra and, by means of an algebra change, also to the theory of linear algebra. We show that an approximation of the maximum function forms a commutative semifield (with respect to multiplication) and corresponds to the maximum again in the limit case. In this way, we demonstrate a novel access to the logarithmic connection between the Fourier transform and the slope transformation. In addition, we prove that the dilation by means of a fast Fourier transform depends only on the size of the structuring element used. Moreover, we derive a bound above which the Fourier approximation yields results that are exact in terms of grey value quantisation.
PDF
