Search code examples
optimizationmixed-integer-programming

MIP/MIQP Solver for an optimization problem with a logical function and exclusive conditions

I have the following problem:

Maximize: F1(I1) + F2(I2) + F3(I3)

Subject to:
   I1 in [min1, max1] U 0
   I2 in [min2, max2] U 0
   I3 in [min3, max3] U 0
   
   I1 + I2 + I3 <= Constant

   Exclusive condition: When I1 > 0 I2 must be zero and vice-versa.
   An arbitrary number of exclusive conditions may be provided.

Where:
   F1(x) = {
      0.15 x if x in [min1, min1 + 100]
      0.1  x if x in [min1 + 101, min1 + 200]
      0.05 x if x in [min1 + 201, max]
   }

   The ranges and quotients for x are arbitrary and provided as a
   part of the optimization problem.

I'm struggling with the exclusive conditions and the logical function, I didn't find any solvers capable of handling such cases.

Is there a solver able to handle such optimization?

P. S. I have a strong impression this is out of MIP/MQP domain at all.

Solution

  • We have three concepts here:

    1. Semi-continuous variables
    2. Complementarity constraints
    3. Piecewise linear functions in the objective

    I'll discuss all these below.

    The first constraints:

     x ∈ [L,U] ∪ {0}

    are usually described as x being a semi-continuous variable. Many solvers have direct support for this. If not you can use a binary variable δ:

     δ⋅L ≤ x ≤ δ⋅U
 δ ∈ {0,1}

    The second constraint

     x*y = 0

    is a non-convex quadratic constraint. This is sometimes called a complementarity constraint. Some solvers can handle this directly. We can also use indicator constraints or binary variables. E.g. we can do, using the same binary variables as before:

     δ(i)⋅L(i) ≤ x(i) ≤ δ(i)⋅U(i)   # all x(i) are semi-continuous
 δ(1) + δ(2) ≤ 1               # x(1)*x(2) = 0 
 δ(i) ∈ {0,1}
 (Assumed:L(i) > 0 or U(i) < 0).

    The last thing, (F1(x)), is just a piecewise linear function. This can be implemented in many ways. Some solvers have special facilities for this. Otherwise, the easiest is to use so-called SOS2 sets. These are supported by many solvers. See e.g.: https://yetanothermathprogrammingconsultant.blogspot.com/2019/02/piecewise-linear-functions-and.html. A good explanation can be found in: https://www.amazon.com/Model-Building-Mathematical-Programming-Williams/dp/1118443330.

    Concluding: with a bit of effort, this can be written in a linear fashion. The precise implementation depends heavily on what modeling tools or solvers are being used. For more information see the documentation of these.