How to deal with universal and existential quantifiers?
AnsweredHi
Can we input a problem that got a couple of universal and existential quantifiers directly to the Gurobi optimizer, or we need to reformulate it without quantifiers first, then process it?
Currently, I am using Farkas lemma to remove the quantifiers, consequently, I got a lot of auxiliary variables, which make my problems complex. It seems to me that Gurobi got the power to deals with such quantifiers problems without reformulating it. Is it true?
If it is, then how to work with such problems? Could you please give me a simple example.
Thanks
Umair
-
Official comment
-
Gurobi Staff
This post is more than three years old. Some information may not be up to date. For current information, please check the Gurobi Documentation or Knowledge Base. If you need more help, please create a new post in the community forum. Or why not try our AI Gurobot?. -
-
-
You have to explicitly write the problem in a form that Gurobi can solve. This means you can't add a constraint like \( \exists i \textrm{ s.t. } x_i = 1 \). Instead, such constraints must be rewritten using mathematical programming techniques, which often involve binary variables.
Of course, if you have a constraint set like \( x_i = 1 \ \forall i \in N \), you can just add these \( |N| \) constraints to the model. These constraints must be represented in the model individually, not as a single constraint with a universal quantifier.
0 -
-
Dear Eli
Thank you so much for your kind and helpful response.
I understand that I have to write the whole problem in mathematical programming. I am just wondering how to write a universally quantified constraint in Gurobi python. For example
Could you please guide me on how to represent this constraint?
Thanks
Umair
0 -
-
-
I am confused by these constraints. They do not contain any variables, since the values of \( i \) and \( p \) are all known. Additionally, \( i - p \geq 0 \) and \( p - i \geq 0 \) together are equivalent to \( i = p \). So, if we write out each of these constraints individually, we end up with
$$\begin{align*} 0 &= 0 \\ 0 &= 1 \\ &\vdots \\ 3 &= 2 \\ 3 &= 3. \end{align*}$$
None of these constraints make sense in a math programming model. Are you missing some variables in your statement?
0 -
-
Sorry Sir, it's my bad. In fact, I was trying to write a very simple example.
Actually I want to solve the following problem.
Here Pi and Sigma are known relations. Whereas Delta relation is unknown.
And, I want the minimize the q and want the optimizer to find out the values of these Delta variables.
Sir, presently I am using Farkas Lemma to get a quantifier-free problem. For this purpose, I have to add a lot of auxiliary variables which make my problem very complex. Furthermore, it is a non-parametric case with a very simple PI and Sigma relations. Later-on I want to try a parametric version of this problem, with some complex relations. That's why I was thinking maybe I get some solution in GUROBI without using Farkas Lemma.
Any help in this regard will be highly appreciated. Sir, still if I am missing something in the explanation of my problem, please let me know.
Thanks
Umair
0 -
-
-
You would have to model something like this with binary indicator variables and additional problem-specific logical constraints. Gurobi does have built-in support for indicator constraints, but the antecedent of the implication (i.e., the \( p \) in \( p \implies q \)) should be a binary variable equal to \( 0 \) or \( 1 \). So, it is possible to do in a math programming framework, but it does require the use of additional constraints and auxiliary binary variables. There's unfortunately no way around that.
The problem is written in a strange way. The truth of \( \Pi(i, p) \) and \( \Sigma(i, l) \) are independent of any variables. Their purpose is to make sure we only enforce the implication \( \Delta(\ell, m) \implies |p - m| \leq q \) if \( p = \ell \). Thus, if we let \( N := \{0, \ldots, 3\} \), we could simplify the whole problem to:
$$\begin{align*}\Delta(\ell, m) \implies |\ell - m| \leq q \qquad \forall \ell \in N,\ m \in N.\end{align*}$$
The problem itself only makes sense if \( q \) is a variable. If not, the truth of \( |p - m| \leq q \) is always a known value, so we wouldn't want to use this statement in a logical constraint.
0 -
-
Thank you so much, Sir.
Actually I have solved successfully this problem with SCIP solver, and Gurobi Python as well. I am getting quantifier-free formula first by using the Affine form of Farkas Lemma, which adds a lot of Farkas multipliers (auxiliary variables), then I am giving input to the optimizer.
I just thought maybe there is any other simple way to do this task. That's why I ask this question at this forum. I am really grateful and appreciate all of you guys. Your whole team is instantly responsive and helpful.
Thanks again
Umair
0 -
Post is closed for comments.
Comments
7 comments