Finding a bounded mixed-integer solution to a system of dual network inequalities
type: Item
instance of: scholarly article
title: Finding a bounded mixed-integer solution to a system of dual network inequalities
zbMATH Open document ID: 1157.15021
published in: Operations Research Letters
publication date: 2008-11-27T00:00:00Z
review text: Let \(B=(b_{ij})\) be a real \(n\times n\) matrix. The system of dual network inequalities is defined by (1) \(x_i-x_j\geq b_{ij}\) \((i,j=1,\dots,n)\). Applying max-algebra, the author shows that all its solutions can be generated using \(n\) generators. Furthermore, let \(J\) be a subset of \(\{1,\dots,n\}\), and let \((u_1,\dots,u_n)\) and \((l_1,\dots,l_n)\) be real vectors. A bounded mixed-integer solution is defined by considering~(1) subject to constraints \(u_j\geq x_j\geq l_j\) \((j=1,\dots,n)\) and requiring that \(x_j\) is an integer for all \(j\in J\). The author develops a pseudopolynomial algorithm to compute such a solution or to decide that it does not exist. If all the entries of \(B\) are integers, then a solution can be found explicitly. A note on application to scheduling completes the paper.
Mathematics Subject Classification ID: 15A39
Mathematics Subject Classification ID: 65F30
Mathematics Subject Classification ID: 90B10
Mathematics Subject Classification ID: 90B35
zbMATH DE Number: 5374663
zbMATH Keywords: dual network inequalities
zbMATH Keywords: max-algebra
zbMATH Keywords: eigenvector
zbMATH Keywords: bounded mixed-integer solution
zbMATH Keywords: pseudopolynomial algorithm
zbMATH Keywords: scheduling
author: Peter Butkovič
reviewed by: Jorma K. Merikoski
MaRDI profile type: Publication
full work available at URL: j.orl.2008.04.004
OpenAlex ID: W2066399276
cites work: Q4304869
cites work: A max version of the Perron-Frobenius theorem
cites work: Pattern Properties and Spectral Inequalities in Max Algebra
cites work: Max-algebra: The linear algebra of combinatorics?
cites work: Max algebra and the linear assignment problem
cites work: Applications of max algebra to diagonal scaling of matrices
cites work: Generators, extremals and bases of max cones
cites work: A linear-system-theoretic view of discrete-event processes and its use for performance evaluation in manufacturing
cites work: Q3964346
cites work: Minimax algebra and applications
cites work: Q5200628
cites work: Simple and Fast Algorithms for Linear and Integer Programs with Two Variables Per Inequality
cites work: Q4217266
cites work: A decomposition algorithm for optimality problems in tree-structured networks
cites work: Network Formulations of Mixed-Integer Programs
DOI: 10.1016/J.ORL.2008.04.004
description: scientific article; zbMATH DE number 5374663