10
$\begingroup$

Is there a way to set a decision variable to take values from a set?

Example:

decision variable $x \in \{0,50,100\}$

So this variable can only take one of these three values and not more.

I have found a documentation online which unfortunately does not state such a thing:

Gurobi Documentation

For this example, I could probably set two different decision variables, with lower bound 0 and 50 or 100, respectively. I am not satisfied with this method, though.

This is how it would probably look like in Java:

//GRBVar addVar(double lb, double ub, double obj, char type, String name)
GRBVar x = model.addVar(50.0,50.0,null,GRB.SEMIINT,"x");
GRBVar y = model.addVar(100.0,100.0,null,GRB.SEMIINT,"y");

Note:

A semi-continous variable has the property that it takes a value of 0, or a value between the specified lower and upper bounds. A semi-integer variable adds the additional restriction that the variable also take an integral value (GRB.SEMIINT).

$\endgroup$
1
  • $\begingroup$ I removed the tag or-tools because this question is not about OR Tools, Google's OR solver. If I was wrong to do so, please add it back, along with clarification in the question. Thanks! $\endgroup$ Sep 26, 2019 at 0:09

2 Answers 2

11
$\begingroup$

I don't think directly, but one way to model that would be to:

  • define a parameter as the vector of the possible values: $p = [0,50,100]$

  • define three binary decision variables that each correspond to whether a value in the set is selected ($y_i \in \{0,1\}, i = 1,2,3$)

  • enforce constraints:

$\sum_{i\in \{1,2,3\} } y_i = 1$ (select exactly 1 of the values to use)

$x=\sum_{i\in \{1,2,3\} } p_iy_i $ (apply the chosen value to the variable $x$)

$\endgroup$
1
  • 1
    $\begingroup$ Quite similar to my suggestion. Nevertheless, thanks for a clear answer. $\endgroup$
    – Georgios
    Sep 25, 2019 at 19:31
4
$\begingroup$

In the case of the example that you provided,(and generally, if you have a pattern in the set of available values for $x$), I am assuming that you have the mentioned pattern in the values of the set, you can define your variable $x$ as the integer and then multiply the value of $x$ by a constant. To explain what I mean:

$x \in \{0, 50, 100\}$ can be equivalently replaced by $x' \in \{0, 1, 2\}$ and then $x = 50 \times x'$ in all constraints and objective function.

But if the general form of decision variable's set is not like the example that you mentioned, this approach won't work. Comment on this solution if my assumption is not correct.

$\endgroup$
4
  • 1
    $\begingroup$ Brilliant answer if the values are the same as in my example. What if I had values such as $x \in \{0,2,5,11\}$ that are not succeeding one another? $\endgroup$
    – Georgios
    Sep 25, 2019 at 19:33
  • 1
    $\begingroup$ @Georgios One option is to create three binary DVs: x_gt_0, x_gt_2, x_gt_5, constrained s.t. x_gt_5 <= x_gt_2 <= x_gt_0, and constrain x = 2*x_gt_0 + (5-2)*x_gt_2 + (11-5)*x_gt_5. $\endgroup$ Sep 25, 2019 at 23:01
  • $\begingroup$ @GeoffreyBrent Ou beautifully crafted. Although it seems to be overcomplicated. Your solution appears to be similar to E.Tucker's. Why would you prefer yours instead? $\endgroup$
    – Georgios
    Sep 26, 2019 at 14:04
  • 1
    $\begingroup$ @Georgios Obviously it's mathematically equivalent, but depending on the solver a different formulation can sometimes make a big difference to the solution time/difficulty. (I don't know whether it matters for Gurobi; I've done some constraint problems where it mattered a lot.) Setting up that formulation by hand is a bit tedious, but it's easy enough to automate, and IIRC some optimisation products can do this sort of piecewise-linearisation automatically. $\endgroup$ Sep 27, 2019 at 1:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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