Message Boards Message Boards

0
|
8617 Views
|
8 Replies
|
4 Total Likes
View groups...
Share
Share this post:

Help/Hints on finding the most "restrictive" equation in a set of equations

Posted 9 years ago

Good morning, I need some help or hints on finding the most "restrictive" equation in a set of equations and inequalities. I have a set of 30 single equations/inequalities in my set, namely:

eqs={y + 0.135456 z >= 78.4807, z >= 51.5464, x + 0.495376 y >= 79.1498, 
 x + 371.686 y >= 34406.8, x + 3.68043 y >= 243.273, 
 x + 0.523148 y + 2.1009 z >= 84.8248, x + 0.532835 y >= 66.3424, 
 x + 0.542384 y >= 75.3277, y + 1.65913 z >= 87.2085, 
 x >= 38.7097, y >= 75.6909, z >= 57.7224, z <= 51.5544, 
 y + 0.135456 z <= 98.1008, z <= 64.4124, y <= 6.25*10^7, 
 x + 2.42904 y + 2.18814 z <= 7260.06, y <= 3.57143*10^7, 
 x + 0.495376 y <= 131.905, x + 371.686 y <= 57372.9, 
 x + 3.68043 y <= 405.455, x + 0.523148 y + 2.1009 z <= 141.417, 
 x + 0.532835 y <= 110.488, x + 0.542384 y <= 125.465, 
 x <= 6.66667*10^7, y <= 166667., y + 1.65913 z <= 109.007, 
 x <= 47.3118, y <= 92.5111, z <= 70.5496}

Finally, I need to solve the whole set. If you apply FullSimplify[And@@eqs], you get False, which is correct; the 12th equation z >= 57.7224 and the 13th equation z <= 51.5544 are conflicting.

Instead of checking all combinations, I would like to have a "smarter" (and faster) way to find conflicting equations which restricts the whole system the most.

I was thinking of adding on equation after another, but this also involves a lot of combinations.

Do you have any ideas or hints? Thank you!

8 Replies

Here is the integer programming method to force a minimum on the number of inequalities violated. The code is almiost the same as before except we make the objective function use 0-1 variables. The 10^6 usage is a heuristic. In general we want something with a quotient much larger than a machine precision ULP, but smaller than the max violation (else we'll have an unsatisfiable system). Stated differently, the result will be optimal unless there is a consistent system from omitting fewer inequalities but accepting a constraint violation larger than 10^6.

e2 = eqs /. {aa_ >= bb_ :> bb - aa, aa_ <= bb_ :> aa - bb};
cvars = Array[c, Length[e2]];
ineqs1 = Thread[cvars >= e2/10^6];
ineqs2 = Thread[0 <= cvars <= 1];
obj = Total[cvars];
allvars = Join[cvars, Variables[e2]];

In[205]:= NMinimize[{obj, 
  Join[ineqs1, ineqs2, {Element[cvars, Integers]}]}, allvars]

(* Out[205]= {2., {16[1] -> 0, 16[2] -> 1, 16[3] -> 0, 16[4] -> 0, 
  16[5] -> 0, 16[6] -> 0, 16[7] -> 0, 16[8] -> 0, 16[9] -> 0, 
  16[10] -> 0, 16[11] -> 0, 16[12] -> 1, 16[13] -> 0, 16[14] -> 0, 
  16[15] -> 0, 16[16] -> 0, 16[17] -> 0, 16[18] -> 0, 16[19] -> 0, 
  16[20] -> 0, 16[21] -> 0, 16[22] -> 0, 16[23] -> 0, 16[24] -> 0, 
  16[25] -> 0, 16[26] -> 0, 16[27] -> 0, 16[28] -> 0, 16[29] -> 0, 
  16[30] -> 0, x -> 38.7097, y -> 92.4653882578, z -> -1.07476935423}} *)

I will remark that this particular solution gives a worse total violation than my previous one, but only requires removal of two inequalities (#2 and #12; this time it's not a matter of checking by eyeball). Also I will say that this approach can be slow in general, although in this example it is quite fast.

POSTED BY: Daniel Lichtblau

Brilliant! I have a lot of different equation systems, but all with similar complexity (number of equations and variables). Indeed, your approach is pretty fast. Thanks!

OK, I got it. "Hinreichende Bedingung"! This is a good starting point for my problem. So I can scan my several hundred equation systems for possible issues. Thanks a lot.

This does not exactly answer the question as asked but it gives a result that can be (re)interpreted as a plausible response. The idea is to solve a linear programming problem wherein we minimize a sum of terms, one for each inequality, with each term greater than the larger of 0 and the inequality violation. The code below sets this up.

e2 = eqs /. {aa_ >= bb_ :> bb - aa, aa_ <= bb_ :> aa - bb};
cvars = Array[c, Length[e2]];
ineqs1 = Thread[cvars >= e2];
ineqs2 = Thread[cvars >= 0];
obj = Total[cvars];
allvars = Join[cvars, Variables[e2]];

Now solve the LP.

Minimize[{obj, Join[ineqs1, ineqs2]}, allvars]

(* Out[158]= {83.9114880482, {c[1] -> 0., c[2] -> 25.6840471685, 
  c[3] -> 0., c[4] -> 0., c[5] -> 0., c[6] -> 0., c[7] -> 0., 
  c[8] -> 0., c[9] -> 0., c[10] -> 0., c[11] -> 0., 
  c[12] -> 31.8600471685, c[13] -> 0., c[14] -> 0., c[15] -> 0., 
  c[16] -> 0., c[17] -> 0., c[18] -> 0., c[19] -> 0., c[20] -> 0., 
  c[21] -> 0., c[22] -> 0., c[23] -> 0., c[24] -> 0., c[25] -> 0., 
  c[26] -> 0., c[27] -> 26.3673937112, c[28] -> 0., c[29] -> 0., 
  c[30] -> 0., x -> 38.7097, y -> 92.4653882578, z -> 25.8623528315}} *)

This means we can find values for {x,y,z} so that only two inequalities (the second and twelfth) are violated.

This minimization of a 1-norm makes the problem tractable. What you want (and I think obtain, in this case, but not in general) is to minimize the 0-norm. That's a harder problem, though it is approachable with integer linear programming.

POSTED BY: Daniel Lichtblau

Dear Daniel,

thanks a lot for your work; I have tested this with a few equations. However, your code will also flag equation 27 in my example above, right? If I just eliminate equations 2, 12 and leave 27, I can solve the system using Reduce and Solve.

How should I interpretate your solution? Do I need to remove 2, 12 and 27 to get a solvable system?

You are correct, I somehow missed that one visually. My solution means it will suffice to remove inequalities 2, 12, 27 in order to have a solvable system. But it does not mean that that is a necessary condition for a solution, and indeed it could be the case that fewer will require removal.

POSTED BY: Daniel Lichtblau

Hi Andreas,

this is an interesting problem and I would like to see a definitive answer as well!

One gets an idea about the nature of the problem by playing around. You can start with searching for pairwise conflicts:

pIndexList2 = Select[Tuples[Range[Length[eqs]], 2], First[#] < Last[#] &];
comb2 = Select[{{#1, #2}, FullSimplify[eqs[[#1]] && eqs[[#2]]]} & @@@ pIndexList2, ! #[[2]] &]
(*   Out:  {{{12,13},False}}  *)

In the same manner one can find conflicting triples:

pIndexList3 = Select[Tuples[Range[Length[eqs]], 3], #[[1]] < #[[2]] < #[[3]] &];
comb3 = Select[{{#1, #2, #3}, FullSimplify[eqs[[#1]] && eqs[[#2]] && eqs[[#3]]]} & @@@ pIndexList3, ! #[[2]] &];
comb3 /. {{___, 12, 13, ___}, _} -> Nothing  (* new combinations only *)
(* Out:  {{{1,2,27},False},{{1,12,27},False},{{2,11,27},False},{{11,12,27},False}}  *)

or quadruples:

pIndexList4 = Select[Tuples[Range[Length[eqs]], 4], #[[1]] < #[[2]] < #[[3]] < #[[4]] &];
comb4 = Select[{{#1, #2, #3, #4}, FullSimplify[eqs[[#1]] && eqs[[#2]] && eqs[[#3]] && eqs[[#4]]]} & @@@ 
    pIndexList4, ! #[[2]] &];
falseCombsPattern = {#, _} & /@ {{___, 12, 13, ___}, {1, 2, ___, 27, ___}, {1, ___, 12, ___, 27, ___}, {___, 2, ___, 11, ___, 27, ___}, {___, 11, 12, ___, 27, ___}};
comb4 /. Thread[falseCombsPattern -> Nothing]  (*  new combinations only  *)

For me the interesting point seems to become obvious by making a statistics of the indices of all quadruples:

ListPlot[Tally@Flatten[First /@ comb4], PlotRange -> All]

giving:

enter image description here

So my guess is that the most conflicting equations are always the ones which gives a pairwise conflict (eqn12 and eqn13 in this case), because they show up in all other combinations as well. Then in this ranking comes eqn27 and then eqn2. Does that make sense to you?

Regards -- Henrik

POSTED BY: Henrik Schachner

Not smart, but a bit interactive:

Manipulate[
 FullSimplify[And @@ (eqs[[choice]])], {{choice, Range[Length[eqs]]}, 
  Range[Length[eqs]], TogglerBar}]
POSTED BY: Gianluca Gorni
Reply to this discussion
Community posts can be styled and formatted using the Markdown syntax.
Reply Preview
Attachments
Remove
or Discard

Group Abstract Group Abstract