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