Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Linear Programming - satisfaction only at least one constraint

  1. Jun 11, 2014 #1
    Linear Programming - satisfaction of only at least one constraint


    Is there a form of relaxation/modification of an LP of the form
    [tex]\text{min }\;\;f^\mathsf{T}x\\\mathbf{A}x\leq b[/tex]
    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.

    Gratitudes in advance.
    Last edited: Jun 11, 2014
  2. jcsd
  3. Jun 12, 2014 #2


    User Avatar
    Science Advisor

    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.
  4. Jun 12, 2014 #3
    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.
  5. Jun 13, 2014 #4


    User Avatar
    Science Advisor

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

    Stephen Tashi

    User Avatar
    Science Advisor

    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.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook