10

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).

LarrySnyder610
  • 13,141
  • 3
  • 41
  • 105
Georgios
  • 1,193
  • 5
  • 21
  • I removed the tag [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! – LarrySnyder610 Sep 26 '19 at 00:09

2 Answers2

11

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$)

E. Tucker
  • 1,317
  • 8
  • 22
4

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.

Oguz Toragay
  • 8,652
  • 2
  • 13
  • 41
  • 1
    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? – Georgios Sep 25 '19 at 19:33
  • 1
    @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 = 2x_gt_0 + (5-2)x_gt_2 + (11-5)*x_gt_5. – GB supports the mod strike Sep 25 '19 at 23:01
  • @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? – Georgios Sep 26 '19 at 14:04
  • 1
    @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. – GB supports the mod strike Sep 27 '19 at 01:24