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

被引：3
|
作者：
Butkovic, P. [1 ]
机构：
[1] Univ Birmingham, Sch Math, Birmingham B15 2TT, W Midlands, England
来源：
OPERATIONS RESEARCH LETTERS | 2008年 / 36卷 / 05期
基金：
英国工程与自然科学研究理事会;
关键词：
Eigenvector; Dual network inequalities; Max-algebra;
D O I：
10.1016/j.orl.2008.04.004
中图分类号：
C93 [管理学]; O22 [运筹学];
学科分类号：
070105 ; 12 ; 1201 ; 1202 ; 120202 ;
摘要：
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.
引用
收藏
页码：623 / 627
页数：5
相关论文
共 50 条
  • [1] Mixing mixed-integer inequalities
    Günlük, O
    Pochet, Y
    MATHEMATICAL PROGRAMMING, 2001, 90 (03) : 429 - 457
  • [2] Mixing mixed-integer inequalities
    Oktay Günlük
    Yves Pochet
    Mathematical Programming, 2001, 90 : 429 - 457
  • [3] MINIMAL INEQUALITIES FOR MIXED-INTEGER PROBLEMS
    BLAIR, CE
    NOTICES OF THE AMERICAN MATHEMATICAL SOCIETY, 1975, 22 (04): : A470 - A471
  • [4] Network Formulations of Mixed-Integer Programs
    Conforti, Michele
    Di Summa, Marco
    Eisenbrand, Friedrich
    Wolsey, Laurence A.
    MATHEMATICS OF OPERATIONS RESEARCH, 2009, 34 (01) : 194 - 209
  • [5] Lifted inequalities for mixed-integer bilinear covering sets
    Chung, Kwanghun
    Richard, Jean-Philippe P.
    Tawarmalani, Mohit
    MATHEMATICAL PROGRAMMING, 2014, 145 (1-2) : 403 - 450
  • [6] Valid inequalities based on simple mixed-integer sets
    Sanjeeb Dash
    Oktay Günlük
    Mathematical Programming, 2006, 105 : 29 - 53
  • [7] Valid inequalities based on simple mixed-integer sets
    Dash, S
    Günlük, O
    INTEGER PROGRAMMING AND COMBINATORIAL OPTIMIZATION, PROCEEDINGS, 2004, 3064 : 33 - 45
  • [8] Valid inequalities based on simple mixed-integer sets
    Dash, S
    Günlük, O
    MATHEMATICAL PROGRAMMING, 2006, 105 (01) : 29 - 53
  • [9] A STRONG DUAL FOR CONIC MIXED-INTEGER PROGRAMS
    Moran R, Diego A.
    Dey, Santanu S.
    Vielma, Juan Pablo
    SIAM JOURNAL ON OPTIMIZATION, 2012, 22 (03) : 1136 - 1150
  • [10] Augmented Hopfield network for mixed-integer programming
    Walsh, MP
    Flynn, ME
    O'Malley, MJ
    IEEE TRANSACTIONS ON NEURAL NETWORKS, 1999, 10 (02): : 456 - 458
12345