Trinary/Ternary Variables

Specific Domains Optimization (Mathematical)
1

I am looking to efficiently implement trinary/ternary variables in a JuMP model. I am considering the following options:

  1. An integer variable with lb=-1, ub=1 (set of values {-1,0,1})
  2. A semi-integer variable…(can take 0 as well as values between bounds) lb=1, ub=2 (set of values {0,1,2})

Is there a performance difference between these two options? Any better options that I have not mentioned? Basically I want it to be more performant than using 2 binary variables. Thoughts?

2

For any formulation choice, I would consider what (linear) relaxation is the result after relaxing any discrete variables. This can likely be only understood in conjunction with other problem structure. For example, a single integer variable x, 0 <= x <= 2 (or similar) might be useful if the relaxation’s one-dimensional interval produces some convex boundary, over the alternative of two binary variables y and z such that their relaxation is a two-dimensional region with an interior intersection with the feasible region.

3

Is there a performance difference between these two options?

In addition to the quality of the LP relaxation as already mentioned, I usually ask myself what this {+1, 0, -1} quantity represents. Is this modeling an alternative between 3 categorical options, e.g., choose between red/blue/green? Or is a physical quantity that can take value \{-1, 0, +1\}?

If it’s the former (3 categories), I would actually go with 3 binaries (see below). If it’s the latter, the integer variable with bounds seems more intuitive. The semi-integer approach would not be my first choice, because it’s mostly intended to distinguish between “zero” and “not zero”.

Any better options that I have not mentioned?

You can also use 3 binaries: x_{-1}, x_{0}, x_{+1}, and the constraint x_{-1} + x_{0} + x_{+1} = 1.
The resulting formulation has more variables, but it typically has a better LP relaxation, and MIP solvers like Gurobi/CPLEX will be better at detecting structure and propagating it (especially when branching).

2 Likes
4

Hi,

I found this topic while also trying to implement ternary variables in optimization problems.

To my knowledge, your second variant (a semi-integer variable) produces an additional binary variable and corresponding constraints:
b = {0;1}
x <= b * ub
x >= b * lb
If you don’t need this binary information in other parts of your optimization model, I don’t see advantages of the second variant. You finally have an integer variable (that is a hidden binary variable, because it only has two values: y=x-1) and a binary variable. At best, this is as performant as using 2 binary variables.

Besides the mentioned variant with three binaries, there are (at least) some more variants:
{-1;0;1}: x = b_1 - b_2 (eventually with b_1 + b_2 <= 1 to prevent two solutions for zero: 0 = 0 - 0 = 1 - 1)
{0;1;2}: x = b_1 + b_2 (eventually with b_2 <= b_1 to order the binaries)
{0;1;2}: x = b_1 + 2 * b_2 (logarithmic expansion, limited by lb <= x <= ub or in this simple case by b_1 + b_2 <= 1)

@chelseas, how did you finally decide to model the ternaries?

Does anybody know some literature about ternary variables in optimization? I didn’t find something helpfull.

5

Hi @Leveringhaus, welcome to the forum :smile:

Some solvers have specialized support for semi-integer variables. For others, JuMP will automatically add the binary. They’re more intended for sets that are not contiguous, like 0 \cup \{5, 6\}.

I’d use @mtanneau’s suggestion of

model = Model()
@variable(model, x[1:3], Bin)
@constraint(model, sum(x) == 1)