Algebraic solution of tropical optimization problems via matrix sparsification with application to scheduling

DOI10.1016/J.JLAMP.2017.03.004zbMATH Open1386.90174arXiv1504.02602OpenAlexW3101473527MaRDI QIDQ2397043FDOQ2397043

Authors: Nikolai Krivulin 

Publication date: 29 May 2017

Published in: Journal of Logical and Algebraic Methods in Programming (Search for Journal in Brave)

Abstract: Optimization problems are considered in the framework of tropical algebra to minimize and maximize a nonlinear objective function defined on vectors over an idempotent semifield, and calculated using multiplicative conjugate transposition. To find the minimum of the function, we first obtain a partial solution, which explicitly represents a subset of solution vectors. We characterize all solutions by a system of simultaneous equation and inequality, and show that the solution set is closed under vector addition and scalar multiplication. A matrix sparsification technique is proposed to extend the partial solution, and then to obtain a complete solution described as a family of subsets. We offer a backtracking procedure that generates all members of the family, and derive an explicit representation for the complete solution. As another result, we deduce a complete solution of the maximization problem, given in a compact vector form by the use of sparsified matrices. The results obtained are illustrated with illuminating examples and graphical representations. We apply the results to solve real-world problems drawn from project (machine) scheduling, and give numerical examples.

Full work available at URL: https://arxiv.org/abs/1504.02602

Recommendations

• Solving a tropical optimization problem via matrix sparsification
• Solution of a multidimensional tropical optimization problem using matrix sparsification
• Solving a tropical optimization problem with application to optimal scheduling
• Algebraic solutions of tropical optimization problems
• Complete solution of tropical vector inequalities using matrix sparsification.
• Tropical optimization problems with application to project scheduling with minimum makespan
• Direct solution to constrained tropical optimization problems with application to project scheduling
• Solution of mathematical programming problems using tropical optimization methods
• Sparse Monge matrices arising from scheduling problems

zbMATH Keywords

sparse matrixidempotent semifieldtropical algebrabacktrackingoptimization problemjust-in-time scheduling

Mathematics Subject Classification ID

Computational methods for sparse matrices (65F50) Deterministic scheduling theory in operations research (90B35) Programming in abstract spaces (90C48)

Cites Work

• Title not available (Why is that?)
• Max-linear systems. Theory and algorithms.
• Title not available (Why is that?)
• Max-plus methods for nonlinear control and estimation.
• Minimax algebra
• Extremal properties of tropical eigenvalues and solutions to tropical optimization problems
• A constrained tropical optimization problem: Complete solution and application example
• A New Matrix Calculus
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• A multidimensional tropical optimization problem with a non-linear objective function and linear constraints
• Title not available (Why is that?)
• On abstract dual linear programs
• Graphs, dioids and semirings. New models and algorithms.
• Multicriteria scheduling problems: a survey
• Title not available (Why is that?)
• Bases in max-algebra
• On some properties of the image set of a max-linear mapping
• Feature issue: Project management and scheduling. 4th international workshop organized by the EURO working group. Leuven, Belgium, July 12--15, 1994
• Title not available (Why is that?)
• Solving a tropical optimization problem via matrix sparsification
• Title not available (Why is that?)
• A maximization problem in tropical mathematics: a complete solution and application examples
• Tropical optimization problems in time-constrained project scheduling
• Title not available (Why is that?)

Cited In (7)

• Monomial Tropical Cones for Multicriteria Optimization
• Complete solution of tropical vector inequalities using matrix sparsification.
• Tropical implementation of the analytical hierarchy process decision method
• Solving a tropical optimization problem via matrix sparsification
• Solution of a multidimensional tropical optimization problem using matrix sparsification
• Solving a tropical optimization problem with application to optimal scheduling
• Application of an optimization problem in max-plus algebra to scheduling problems

This page was built for publication: Algebraic solution of tropical optimization problems via matrix sparsification with application to scheduling

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2397043)