Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

(I have post a question with bounty for several days (Find a best 4-tuple which fulfils a variable boolean formula), but unfortunately got no answer yet. Here I simplify it to a smaller problem and hope could get some ideas...)

I have a big boolean formulae as follows:

$\quad (c_0 \leq c \wedge c \geq a_0+e_0 \vee e \geq c_0-b_0 \wedge e_0 \leq e) \wedge$

$\quad \quad c \leq d \wedge d-e \geq a_0 \wedge c-f \leq b_0 \wedge e \leq f \wedge$

$\quad \quad (d \leq d_0 \vee f \leq d_0-a_0) \wedge (d \leq b_0+f_0 \vee f \leq f_0)$

where $a_0, b_0, c_0, d_0, e_0, f_0$ are integer constants (including $-\infty$ and $+\infty$) as arguments, and $c, d, e, f$ are integer variables (including $-\infty$ and $+\infty$) to find.

I have already a function area to measure the dimension of 4 integers: $area(c,d,e,f) = |c-d| \times |e-f|$

So I am looking for an algorithm to find an optimal 4-tuple $(c,d,e,f)$ which makes the big formula TRUE and the $area(c,d,e,f)$ is greater or equal to the dimension of any other 4-tuple which also satisfies the formula.

In other word, find $\text{Max}(area(c,d,e,f))$ subjet to the big formula.

Could anyone help? Thank you very much!

share|improve this question

1 Answer 1

This is not an answer, but it's how I would proceed. Your conditions on $c, d, e,$ and $f$ translate to the following in a less Boolean language:

$$d\leq \min(d_0,b_0+f_0)$$

$$f\leq \min(d_0-a_0,f_0)$$

$$\max(c_0,a_0+e_0)\leq c\leq \min(d,b_0+f)$$

$$\max(c_0-b_0, e_0)\leq e\leq \min(d-a_0,f)$$

With boundary conditions like this, you could try to parameterize the components of the boundary surface (some kind of hacked up prism) and use Lagrange multipliers to find the optimal values of your function. There are at least $8$ components to this surface, and quite possibly more depending on the values of your constants.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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