1 - 8 of 8
Number of results to display per page
Search Results
2. A note on resolving the inconsistency of one-sided max-plus linear equations
- Creator:
- Li, Pingke
- Format:
- bez média and svazek
- Type:
- model:article and TEXT
- Subject:
- max-plus algebra, max-plus linear systems, and mixed integer programming
- Language:
- English
- Description:
- When a system of one-sided max-plus linear equations is inconsistent, its right-hand side vector may be slightly modified to reach a consistent one. It is handled in this note by minimizing the sum of absolute deviations in the right-hand side vector. It turns out that this problem may be reformulated as a mixed integer linear programming problem. Although solving such a problem requires much computational effort, it may propose a solution that just modifies few elements of the right-hand side vector, which is a desired property in some practical situations.
- Rights:
- http://creativecommons.org/publicdomain/mark/1.0/ and policy:public
3. An iterative algorithm for computing the cycle mean of a Toeplitz matrix in special form
- Creator:
- Szabö, Peter
- Format:
- bez média and svazek
- Type:
- model:article and TEXT
- Subject:
- max-plus algebra, eigenvalue, sub-partition of an integer, and Toeplitz matrix
- Language:
- English
- Description:
- The paper presents an iterative algorithm for computing the maximum cycle mean (or eigenvalue) of n×n triangular Toeplitz matrix in max-plus algebra. The problem is solved by an iterative algorithm which is applied to special cycles. These cycles of triangular Toeplitz matrices are characterized by sub-partitions of n−1.
- Rights:
- http://creativecommons.org/publicdomain/mark/1.0/ and policy:public
4. Generalized public transportation scheduling using max-plus algebra
- Creator:
- Subiono, Fahim, Kistosil, and Adzkiya, Dieky
- Format:
- bez média and svazek
- Type:
- model:article and TEXT
- Subject:
- max-plus algebra, strongly connected road network, and scheduling
- Language:
- English
- Description:
- In this paper, we discuss the scheduling of a wide class of transportation systems. In particular, we derive an algorithm to generate a regular schedule by using max-plus algebra. Inputs of this algorithm are a graph representing the road network of public transportation systems and the number of public vehicles in each route. The graph has to be strongly connected, which means there is a path from any vertex to every vertex. Let us remark that the algorithm is general in the sense that we can allocate any number of vehicles in each route. The algorithm itself consists of two main steps. In the first step, we use a novel procedure to construct the model. Then in the second step, we compute a regular schedule by using the power algorithm. We describe our proposed framework for an example.
- Rights:
- http://creativecommons.org/publicdomain/mark/1.0/ and policy:public
5. Idempotent versions of Haar´s Lemma: Links between comparison of discrete event systems with different state spaces and control
- Creator:
- Ahmane, Mourad and Truffet, Laurent
- Format:
- bez média and svazek
- Type:
- model:article and TEXT
- Subject:
- max-plus algebra, control, monotonicity, positive invariance, residuation, and duality
- Language:
- English
- Description:
- Haar's Lemma (1918) deals with the algebraic characterization of the inclusion of polyhedral sets. This Lemma has been involved many times in automatic control of linear dynamical systems via positive invariance of polyhedrons. More recently, it has been used to characterize stochastic comparison w.r.t. linear/integral ordering of Markov (reward) chains. In this paper we develop a state space oriented approach to the control of Discrete Event Systems (DES) based on the remark that most of control constraints of practical interest are naturally expressed as the inclusion of two systems of linear (w.r.t. idempotent semiring or semifield operations) inequalities. Thus, we establish tropical version of Haar's Lemma to obtain the algebraic characterization of such inclusion. As in the linear case this Lemma exhibits the links between two apparently different problems: comparison of DES and control via positive invariance. Our approach to the control differs from the ones based on formal series and is a kind of dual approach of the geometric one recently developed. Control oriented applications of the main results of the paper are given. One of these applications concerns the study of transportation networks which evolve according to a time table. Although complexity of calculus is discussed the algorithmic implementation needs further work and is beyond the scope of this paper.
- Rights:
- http://creativecommons.org/publicdomain/mark/1.0/ and policy:public
6. Interval multi-linear systems for tensors in the max-plus algebra and their application in solving the job shop problem
- Creator:
- Khaleghzade, Sedighe, Zangiabadi, Mostafa, Peperko, Aljoša, and Hajarian, Masoud
- Format:
- bez média and svazek
- Type:
- model:article and TEXT
- Subject:
- interval tensor, max-plus algebra, multi-linear systems, weak solvability, and job shop problem
- Language:
- English
- Description:
- In this paper, we propose the notions of the max-plus algebra of the interval tensors, which can be used for the extension of interval linear systems to interval multi-linear systems in the max-plus algebra. Some properties and basic results of interval multi-linear systems in max-plus algebra are derived. An algorithm is developed for computing a solution of the multi-linear systems in the max-plus algebra. Necessary and sufficient conditions for the interval multi-linear systems for weak solvability over max-plus algebra are obtained as well. Also, some examples are given for illustrating the obtained results. Moreover, we briefly sketch how our results can be used in the max-plus algebraic system theory for synchronized discrete event systems.
- Rights:
- http://creativecommons.org/licenses/by-nc-sa/4.0/ and policy:public
7. On an algorithm for testing T4 solvability of max-plus interval systems
- Creator:
- Myšková, Helena
- Format:
- bez média and svazek
- Type:
- model:article and TEXT
- Subject:
- max-plus algebra, interval system, T4 vector, and T4 solvability
- Language:
- English
- Description:
- In this paper, we shall deal with the solvability of interval systems of linear equations in max-plus algebra. Max-plus algebra is an algebraic structure in which classical addition and multiplication are replaced by ⊕ and \kr, where a⊕b=max{a,b}, a\krb=a+b. The notation \mbfA\krx=\mbfb represents an interval system of linear equations, where \mbfA=[\pA,\nA] and \mbfb=[\pb,\nb] are given interval matrix and interval vector, respectively. We can define several types of solvability of interval systems. In this paper, we define the T4 solvability and give an algorithm for checking the T4 solvability.
- Rights:
- http://creativecommons.org/publicdomain/mark/1.0/ and policy:public
8. Solving the sensor cover energy problem via integer linear programming
- Creator:
- Li, Pingke
- Format:
- bez média and svazek
- Type:
- model:article and TEXT
- Subject:
- max-plus algebra, sensor coverage problem, and integer linear programming
- Language:
- English
- Description:
- This paper demonstrates that the sensor cover energy problem in wireless communication can be transformed into a linear programming problem with max-plus linear inequality constraints. Consequently, by a well-developed preprocessing procedure, it can be further reformulated as a 0-1 integer linear programming problem and hence tackled by the routine techniques developed in linear and integer optimization. The performance of this two-stage solution approach is evaluated on a set of randomly generated instances and demonstrates that it is capable of solving large size instances of the sensor cover energy problem.
- Rights:
- http://creativecommons.org/licenses/by-nc-sa/4.0/ and policy:public