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.
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook