linear constraint with mixed binary and continuous variables

[Jaco Vermaak]

Hi there,

I have a constraint of the form x = a y, where a > 0 is a continuous variable and the elements of y is binary, which has the implication of the elements of x either taking on 0 or a.

This is trivial to implement in Mosek if a is a known constant, using a big-M approximation. The problem I have is that a is a variable also, so I cannot find an easy way, it seems, to implement this.

Does anyone know how I might model this?

Many thanks in advance,

Jaco Vermaak

[Erling D. Andersen]

MOSEK version 10 to be released  next year has something called disjunctive constraints.

This implies you can write

<x-a=0, y=1>  or <x=0, y=0>

Here I assume all are scalars. Is that what you want?

[Sven Wiese]

Until you have access to MOSEK 10, you can still model this with big-M constraints (note that from your description one can deduce the globally valid lower bound 0 <= x):

-M(1 - y) <= a - x <= M(1 - y)

x <= My

If you know bounds on a, say lb_a <= a <= ub_a, and an upper bound on x, say x <= ub_x, then the following values for M guarantee a valid formulation:

lb_a(1 - y) <= a - x <= ub_a(1 - y)

x <= ub_x * y.

[Jaco Vermaak]

Thank you for the reply!

Yes, thanks, that looks like it will work. I have looked into the possibility of disjunctive constraints, but seems like Mosek can currently only handle linear inequality constraints (with the big-M trick) this way.

[Jaco Vermaak]

Thank you very much Sven, that works beautifully!

[Sven Wiese]

Note that any equality constraint can be equivalently written by two inequality constraints. In MOSEK 10 we will initially allow only linear constraints inside the disjunctive terms. But even in that case one might apply some tricks to model non-linear disjunctions. The same is likely to be true when big-Ms are used. If you have a specific example in mind don't hesitate to post it here, that would be interesting.

[Jaco Vermaak]

Thanks for all the help so far! My full problem is stated in the attachment below (R is the Cholesky factorisation of the covariance Sigma). With the big-M approximation as suggested above it all seems to work fine.

The biggest issue now is that it takes a very long time to obtain solutions for typical problem sizes (n in the order of 100). I have also tried a version where I assume alpha to be a known constant (so a simplified version of the below problem), and then solving for alpha in an outer loop using a non-derivative minimisation algorithm (scipy's minimize_scalar with the brent algorithm). This is somewhat quicker, but gives less good solutions (in terms of the final objective) than the one-shot formulation (as one might expect).

My main question now is if there is something that I can do to speed up running times for the one-shot approach at all? Maybe there are tricks in setting up the problem that could help that I'm not aware of?

[Sven Wiese]

You could of course try to tune parameters. One thing that comes to my mind is switching the solution method from conic branch-and-bound to outer approximation. In the C API that is controlled with the parameter MSK_IPAR_MIO_CONIC_OUTER_APPROXIMATION.

[Jaco Vermaak]

Thank you again. I tried to enable this (in python) by:

m.setSolverParam("mioConicOuterApproximation", "on")

but got an unknown parameter error:

Traceback (most recent call last):
  File "/users/is/ahlpypi/medusa_egg_cache/36-1/i/ipython-7.7.0-py3.6.egg/IPython/core/interactiveshell.py", line 3326, in run_code
    exec(code_obj, self.user_global_ns, self.user_ns)
  File "<ipython-input-8-9ffcb1567791>", line 1, in <module>
    m.setSolverParam("mioConicOuterApproximation", "on")
  File "/users/is/ahlpypi/medusa_egg_cache/36-1/m/Mosek-1!8.1.77+ahl1-py3.6-linux-x86_64.egg/mosek/fusion/impl/_implementation.py", line 2996, in setSolverParam
    return self._setSolverParam_SS(*args)
  File "/users/is/ahlpypi/medusa_egg_cache/36-1/m/Mosek-1!8.1.77+ahl1-py3.6-linux-x86_64.egg/mosek/fusion/impl/_implementation.py", line 4075, in _setSolverParam_SS
    mosek.fusion.Parameters._setParameter_Lmosek_4fusion_4Model_2SS(self,_0,_1)
  File "/users/is/ahlpypi/medusa_egg_cache/36-1/m/Mosek-1!8.1.77+ahl1-py3.6-linux-x86_64.egg/mosek/fusion/impl/_implementation.py", line 40552, in _setParameter_Lmosek_4fusion_4Model_2SS
    raise mosek_fusion_ParameterError._ctor_S("Unknown parameter")
mosek.fusion.impl._implementation.__mk_mosek_fusion_ParameterError.<locals>.ParameterError: Unknown parameter

Maybe the version of mosek I'm using does not have this feature? This is the version:

mosek.Env.getversion()
Out[6]: (8, 1, 0, 77)

Sorry for the hassle with this!

[Sven Wiese]

That is indeed available only from version 9 onward. Any chance you can grade up? That might of course include general improvements, besides the parameter.