1
$\begingroup$

I have a very large number of constraints such as:

  1. $ A1 \land B1 \land C1 \land D1 \land E1 \land F1$
  2. $ A2 \land B2 \land C2 \land D2 \land E2 \land F2$
  3. $ A3 \land B3 \land C3 \land D3 \land E3 \land F3$
  4. $ A4 \land B4 \land C4 \land D4 \land E4 \land F4$

Here a constraint is a condition. For example, A1 is (response time < 10). All the condition needs to be satisfied such that the configuration is feasible. For instance, the configuration 1 needs to have A1, B1, C1, D1, E1 and F1 =1. How can I quickly check which configurations are valid? At moment I'm using a CSP (choco-solver) and iterate over each configuration and check the conditions. Is there a better (faster) way to do this rather than just checking the configuration one by one?

$\endgroup$
  • $\begingroup$ You can factor common subexpressions to speed up the processing. $\endgroup$ – Yuval Filmus Oct 10 '17 at 12:41
  • $\begingroup$ I don't understand the question yet. Are you trying to pick a single configuration that satisfies all of the constraints? Why not just set all of the atoms $A1,A2,...,B1,B2,...$ to true? Are some of them not simultaneously satisfiable? Is there some underlying structure to the $A1,...$ atoms? If so, what is it? Are all of them linear inequalities? Something else? If so, what? Are your constraints always conjunctions, with no negations? Please tell us more about the nature of the constraints and your problem. $\endgroup$ – D.W. Oct 10 '17 at 15:17
  • $\begingroup$ @D.W. In the end I need a single configuration that satisfies all of the constraints. Some of them are not simultaneously satisfiable. For example, my constraints are all liniar for now and a value for first configuration can be (a,b,c,d,e)=(10,90,15,90,10,60). If we check this configuration we have (a < 10 AND b > 80 AND C > 10 AND d < 100 AND e <20 AND f >50). Now, this is not satisfiable because we have F AND T AND T AND T AND T AND T. In my problem, I have many configurations of type (a,b,c,d,e). $\endgroup$ – Andrei Oct 10 '17 at 16:50
  • $\begingroup$ Does it make sense to use a CSP solver to check all of them? Do I need something else? In the next step I want to extract the non-dominated set. Do I have to do it in 2 steps or is there a clever way to do this (checking for valid config and getting the non-dominated set). $\endgroup$ – Andrei Oct 10 '17 at 16:53
  • $\begingroup$ I'm confused. If the constraints aren't simultaneously satisfiable, then there is no configuration that satisfies all of them. So are you asking for something that is impossible? I don't understand what your question is. Have you read about linear programming, integer linear programming, SAT, and SMT solvers? Perhaps that will help you formulate your question more clearly? $\endgroup$ – D.W. Oct 10 '17 at 23:14
1
$\begingroup$

Apparently, based on your comments, each condition is a linear inequality, you have a list of conditions, and you want to test whether an assignment satisfies all of the conditions, or find an assignment that satisfies all of the conditions.

Testing whether an assignment satisfies all of the conditions is just a simple matter of programming. For each inequality, you just plug in the values of the variables, then test whether the inequality holds or not. No special solver or anything is needed.

It's also possible to find an assignment that satisfies all of the conditions, i.e., find values for all of the variables that makes all of the conditions true. This is exactly the linear programming problem. There are good, efficiently algorithms known for linear programming. You can use any off-the-shelf linear programming solver. They should very rapidly find a valid configuration.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.