A Fast Algorithm for the Two-Variable Integer Programming Problem (Q3783845)

From MaRDI portal

!

This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:

scientific article; zbMATH DE number 4047442
Language Label Description Also known as
default for all languages
No label defined
    English
    A Fast Algorithm for the Two-Variable Integer Programming Problem
    scientific article; zbMATH DE number 4047442

      Statements

      A Fast Algorithm for the Two-Variable Integer Programming Problem (English)
      0 references
      1984
      0 references
      two-variable problem
      0 references
      minimal binding set of constraints
      0 references
      three constraint problems
      0 references
      Considered is the problem max z\(=a_{01}x+a_{02}y\) subject to \(a_{i1}x+a_{i2}y\geq c_ i\) \((i=1,...,m)\), \(a_{ij}\), \(c_ i\), x, y integer. There are no sign restrictions and the feasible region may be bounded, unbounded or empty. At first the restrictions are transformed by a unimodular \(2\times 2\) matrix to a standard form. Next all not-bounding constraints are discarded and some trivial cases can be solved immediately. In all other cases the solution points lie on a vertical line \(x=c\), the solution line, which can be found by a simplified version of a method of Scarf. A new method of solving three constraint problems is also given.
      0 references

      Identifiers

      0 references
      0 references
      0 references
      0 references
      0 references
      0 references