Linear Programming - satisfaction only at least one constraint

1. Jun 11, 2014

wavingerwin

Linear Programming - satisfaction of only at least one constraint

Hi

Is there a form of relaxation/modification of an LP of the form
$$\text{min }\;\;f^\mathsf{T}x\\\mathbf{A}x\leq b$$
such that if only any one of the constraints is satisfied, then the solution $x$ is regarded as feasible?

Here $\mathbf{A}x\leq b$ represents a row of linear constraints.

Last edited: Jun 11, 2014
2. Jun 12, 2014

Erland

I don't really understand what you mean. If we have a constraint with only one inequality instead of a system of more than one, then we have a new LP-problem.

3. Jun 12, 2014

wavingerwin

The LP I am concerned with has a number of inequalities. However, I need to only have at least one of them satisfied. This can be any combination of the inequalities, not a particular one.

Say the LP has 5 inequalities to satisfy. I want to have that satisfying at least one of the 5 means that the solution is feasible, as opposed to having all of the 5 satisfied, like in a standard LP. However, it can be any combination of the constraint, for example [1 0 0 0 0], [0 0 1 1 0], and many others, where 1 and 0 correspond to each of the inequality being satisfied or unsatisfied respectively.

4. Jun 13, 2014

Erland

I see... If there are n inequalities, you could solve n LP problems, one for each inequality, and choose the one with smallest value.

5. Jun 13, 2014

Stephen Tashi

There is the concept of whether a constraint is "tight" at an optimal solution. If you find an optimal solution subject to n inequality constraints then to improvie on that solution, look at dropping the constraits that are satisified as exact equalities.