Skip to main content
SpringerLink
Log in

Representations of unbounded optimization problems as integer programs

  • Contributed Papers
  • Published:
Journal of Optimization Theory and Applications Aims and scope Submit manuscript

Abstract

Any optimization problem in a finite structure can be represented as an integer or mixed-integer program in integral quantities.

We show that, when an optimization problem on an unbounded structure has such a representation, it is very close to a linear programming problem, in the specific sense described in the following results. We also show that, if an optimization problem has such a representation, no more thann+2 equality constraints need be used, wheren is the number of variables of the problem.

We obtain a necessary and sufficient condition for a functionf:S→Z, withS \( \subseteq \) Z n, to have a rational model in Meyer's sense, and show that Ibaraki models are a proper subset of Meyer models.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Ibaraki, T.,Integer Programming Formulation of Combinational Optimization Problems, Discrete Mathematics, Vol. 16, pp. 39–52, 1976.

    Google Scholar 

  2. Meyer, R. R.,Integer and Mixed-Integer Programming Models: General Properties, Journal of Optimization Theory and Applications, Vol. 16, pp. 191–206, 1975.

    Google Scholar 

  3. Meyer, R. R.,Mixed-Integer Minimization Models for Piecewise-Linear Functions of a Single Variable, University of Wisconsin, Mathematics Research Center, Report No. 1460, 1974.

  4. Meyer, R. R., andThakkar, M. V.,Rational Mixed-Integer Minimization Models, University of Wisconsin, Mathematics Research Center, Report No. 1552, 1975.

  5. Bradley, G. H.,Transformation of Integer Programs to Knapsack Problems, Discrete Mathematics, Vol. 1, pp. 29–45, 1971.

    Google Scholar 

  6. Padberg, M.,Equivalent Knapsack-type Formulations of Bounded Integer Linear Programs, Carnegie-Mellon University, Management Science, Research Report No. 227, 1970.

  7. Rockafellar, R. T.,Convex Analysis, Princeton University Press, Princeton, New Jersey, 1970.

    Google Scholar 

  8. Jeroslow, R.,Some Structure and Basis Theorems for Integral Monoids, Carnegie-Mellon University, Management Science, Research Report No. 367, 1975.

  9. Blair, C. E., andJeroslow, R.,The Value Function of MIP: I and II, Carnegie-Mellon University, Management Science, Research Report No. 377, 1975.

  10. Wolsey, L. A.,Group Theoretic Results in Mixed Integer Programming, Operations Research, Vol. 19, pp. 1691–1697, 1971.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. College of Industrial Management, Georgia Institute of Technology, Atlanta, Georgia

    R. G. Jeroslow (Professor)

Authors
  1. R. G. Jeroslow
    View author publications

    You can also search for this author in PubMed Google Scholar

Additional information

Communicated by O. L. Managasarian

This research was supported by NSF Grant No. GP-37510X1 and ONR Contract No. N00014-75-C0621, NR047-048.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Jeroslow, R.G. Representations of unbounded optimization problems as integer programs. J Optim Theory Appl 30, 339–351 (1980). https://doi.org/10.1007/BF00935492

Download citation

  • Issue Date:

  • DOI: https://doi.org/10.1007/BF00935492

Key Words

Search

Navigation