2

I want to know LP can be considered as a Discrete optimization or continuous. The solutions can be fractions so it should be continuous. Please suggest. thanks

user55531
  • 309

2 Answers2

1

According to the nomenclature of the optimization community, linear programming is continuous optimization. Solutions to a linear program are allowed to assume any real value (subject of course to satisfaction of the constraints).

You mention that solutions may assume fractional values. That is in itself not a requirement for continuous optimization. It is true however that linear programs consisting exclusively of rational coefficients can be guaranteed to obtain rational vertex solutions (when feasible).

Michael Grant
  • 19,450
0

An LP can be considered as combinatorial. Recall that the feasible region is a polyhedron and that a solution to an LP can be found evaluating the objective function at each vertex. one such algorithm is the simplex method.

Another technique is the interior point method which treats an LP as a continuous problem.

So it can be treated as combinatorial or continuous.

Mykie
  • 7,037
  • I am not convinced that you can call a problem "combinatorial" just because it admits a sub-optimal algorithm with exponential complexity. I could sort $n$ elements, for instance, by trying all possible $n$-factorial permutations, and selecting the first one whose elements are in order; that does not make sorting combinatorial. – Michael Grant Jan 04 '15 at 06:42