HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Linear programs with strict inequalities and supremum objectives

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
linearwithinequalitiesprogramsandstrictobjectivessupremum

Problem

Linear programming can solve only problems with weak inequalities, such as "maximize $c x$ such that $A x \leq b$". This makes sense, since problems with strict inequality often do not have a solution. For example "maximize $x$ such that $x<5$" does not have a solution.

But suppose we are interested in finding supremum instead of maximum. In this case, the above program does have a solution - the supremum is $5$.

Given a linear program with strict inequalities and a supremum or infimum objective, is it possible to solve it by reduction to a standard linear program?

Solution

Suppose that the supremum of a continuous function $f(x)$ subject to $Ax 0$ is $0$, but the sequence $(n+1/n,n)$ has no limit points. Nevertheless, the answer should be the same.

Context

StackExchange Computer Science Q#112999, answer score: 4

Revisions (0)

No revisions yet.