Finding a bounded mixed-integer solution to a system of dual network inequalities

Peter Butkovic

doi:10.1016/j.orl.2008.04.004

Finding a bounded mixed-integer solution to a system of dual network inequalities

Peter Butkovic

Mathematics

Research output: Contribution to journal › Article

3 Citations (Scopus)

Abstract

We show that using max-algebraic techniques it is possible to generate the set of all solutions to a system of inequalities x(i) - x(j) >= b(ij), i,j = 1,..., n using n generators. This efficient description enables us to develop a pseudopolynomial algorithm which either finds a bounded mixed-integer solution, or decides that no such solution exists. (c) 2008 Elsevier B.V. All rights reserved.

Original language	English
Pages (from-to)	623-627
Number of pages	5
Journal	Operations Research Letters
Volume	36
Issue number	5
DOIs	https://doi.org/10.1016/j.orl.2008.04.004
Publication status	Published - 1 Sept 2008

Keywords

Dual network inequalities
Eigenvector
Max-algebra

Access to Document

10.1016/j.orl.2008.04.004

Feasibility and Reachability in Max-Linear Systems
Butkovic, P.
Engineering & Physical Science Research Council
1/02/08 → 30/04/11
Project: Research Councils

Cite this

@article{f83f803c8c7c4e3ab2eee57fde30fec6,

title = "Finding a bounded mixed-integer solution to a system of dual network inequalities",

abstract = "We show that using max-algebraic techniques it is possible to generate the set of all solutions to a system of inequalities x(i) - x(j) >= b(ij), i,j = 1,..., n using n generators. This efficient description enables us to develop a pseudopolynomial algorithm which either finds a bounded mixed-integer solution, or decides that no such solution exists. (c) 2008 Elsevier B.V. All rights reserved.",

keywords = "Dual network inequalities, Eigenvector, Max-algebra",

author = "Peter Butkovic",

year = "2008",

month = sep,

day = "1",

doi = "10.1016/j.orl.2008.04.004",

language = "English",

volume = "36",

pages = "623--627",

journal = "Operations Research Letters",

publisher = "Elsevier",

number = "5",

}

TY - JOUR

T1 - Finding a bounded mixed-integer solution to a system of dual network inequalities

AU - Butkovic, Peter

PY - 2008/9/1

Y1 - 2008/9/1

N2 - We show that using max-algebraic techniques it is possible to generate the set of all solutions to a system of inequalities x(i) - x(j) >= b(ij), i,j = 1,..., n using n generators. This efficient description enables us to develop a pseudopolynomial algorithm which either finds a bounded mixed-integer solution, or decides that no such solution exists. (c) 2008 Elsevier B.V. All rights reserved.

AB - We show that using max-algebraic techniques it is possible to generate the set of all solutions to a system of inequalities x(i) - x(j) >= b(ij), i,j = 1,..., n using n generators. This efficient description enables us to develop a pseudopolynomial algorithm which either finds a bounded mixed-integer solution, or decides that no such solution exists. (c) 2008 Elsevier B.V. All rights reserved.

KW - Dual network inequalities

KW - Eigenvector

KW - Max-algebra

U2 - 10.1016/j.orl.2008.04.004

DO - 10.1016/j.orl.2008.04.004

M3 - Article

VL - 36

SP - 623

EP - 627

JO - Operations Research Letters

JF - Operations Research Letters

IS - 5

ER -

Finding a bounded mixed-integer solution to a system of dual network inequalities

Abstract

Keywords

Access to Document

Fingerprint

Projects

Feasibility and Reachability in Max-Linear Systems

Cite this