Abstract
I n the classical linear programming problem the behaviour of continuous, nonnegative variables subject to a system of linear inequalities is investigated.One possible generalization of this problem is to relax the continuity condition on the variables.This paper presents a simple numerical algorithm for the solution of programming problems in which some or all of the variables can take only discrete values.The algorithm requires no special techniques beyond those used in ordinary linear programming, and lends itself to automatic computing.Its use is illustrated on two ~lumerical examples.
Keywords
Computer scienceMathematical optimizationMathematical economicsMathematics
Related Publications
Determinant Maximization with Linear Matrix Inequality Constraints
The problem of maximizing the determinant of a matrix subject to linear matrix inequalities (LMIs) arises in many fields, including computational geometry, statistics, system id...
Global Optimization with Polynomials and the Problem of Moments
We consider the problem of finding the unconstrained global minimum of a real-valued polynomial p(x): {\mathbb{R}}^n\to {\mathbb{R}}$, as well as the global minimum of p(x), in ...
On the approximability of minimizing nonzero variables or unsatisfied relations in linear systems
We investigate the computational complexity of two closely related classes of combinatorial optimization problems for linear systems which arise in various fields such as machin...
Feature Selection via Mathematical Programming
The problem of discriminating between two finite point sets in n-dimensional feature space by a separating plane that utilizes as few of the features as possible is formulated a...
Interior-Point Polynomial Algorithms in Convex Programming
Written for specialists working in optimization, mathematical programming, or control theory. The general theory of path-following and potential reduction interior point polynom...
Publication Info
- Year
- 1960
- Type
- article
- Volume
- 28
- Issue
- 3
- Pages
- 497-497
- Citations
- 1827
- Access
- Closed
External Links
Social Impact
Altmetric
PlumX Metrics
Social media, news, blog, policy document mentions
Citation Metrics
1827
OpenAlex
Cite This
A. H. Land,
A. G. Doig
(1960).
An Automatic Method of Solving Discrete Programming Problems.
Econometrica
, 28
(3)
, 497-497.
https://doi.org/10.2307/1910129
Identifiers
- DOI
- 10.2307/1910129