7
$\begingroup$

I have a general question about the effect of 'unused' variables on the result and runtime of optimization algorithms. I try to explain my question by giving an example. Let's say I have 2 type of buildings that I want to model. They have flexible electrical consumers that can vary their electrical power. We also have a time-dependent price for electricity for one day. So basically the task is a scheduling problem that can for example be modelled as a mixed-integer linear problem.

Let's say buildings from type 1 have two flexible electrical consumers:

  • A heat pump (electrical heating element) with a maximum electrical Power of P_HP and a binary (or continuous) decision variable x(t) between [0,1] for x(t) in {1,2,3,...,24}.
  • An electric vehicle with a maximum electrical power of P_EV and a binary (or continuous) decision variable x(t) between [0,1] for y(t) in {1,2,3,...,24}.

So the current electrical power for a time slot t for the heat pump is P(t)= x(t) *P_HP for every hour of the day. Analogously, the current electrical power for a time slot t for the electric vehicle is calculated P(t)=y(t) * P_EV. Of course I have several constraints for the devices and and objective function that depend on x(t) and y(t).

Building type 2 also has the heat pump as the flexible device but does not have an electric vehicle. Now I come to my question. What effect does it have on the optimization if I model building type 2 exactly like building type 1 but set the maximum (and minimum) power of the electric vehicle P_EV to 0? By doing so, the decision variable y(t) would not have any effects on any constraint and on the objective function and thus can be labelled as 'unused'. But still they are incorporated in the optimization and the number of variables is surely increased by that. Another way would be to use a different model for building type 2 and exclude the variables and the constraints for the electric vehicle. Thus, I would reduce the number of decision variables and constraints for building type 2 but the effort for modelling will be higher as I would have to model building type 2 separately instead of just adjusting the parameters for them.

My concrete questions are:

  1. What effect do such 'unused' variables have on the runtime and the result of the optimization? We now have more decision variables but all of them could just take any value as they do not influence anything.
  2. From a modelling perspective: Is it advisable to use such variables or not? I mean the model of all buildings would be exactly the same which reduces the lines of code and the time to implement it. However, the model would not be really "correct" for certain building types as it would include variables and constraints that are not really existing for those building types.

What is your experience regarding theses questions? I'd highly appreciate every comment and every shared experience. The motivation for my question is that in fact I have not 2 but 20 different building types with different combinations of flexible electrical consumers.

$\endgroup$
4
  • 2
    $\begingroup$ A solver will usually fix those variables to some value in a preprocessing step and the time for doing that should usually be negligible. However, it is probably better to directly fix the unused y variables to 0, if possible. That makes life for the solver a bit easier. $\endgroup$ Jun 1 at 11:08
  • 3
    $\begingroup$ I have seen models where preprocessing/presolve takes most of time simple because the modeller included too much unneeded stuff. So my advice is to look at the preprocessing time printed by the optimizer. If that is large in a relative sense then improving the model might be worthwhile. $\endgroup$ Jun 1 at 11:14
  • $\begingroup$ @DanielJunglas: Thanks Daniel for your comment. You wrote "A solver will usually fix those variables to some value in a preprocessing step" --> is this automatically done by the solver or do I have to somehow indicate those variables to the solver? $\endgroup$
    – PeterBe
    Jun 1 at 12:45
  • 2
    $\begingroup$ That question is somewhat solver-specific, but pretty much every solver I've seen does it automatically. $\endgroup$
    – prubin
    Jun 1 at 19:40
8
$\begingroup$

If variable fixings can be derived automatically (e.g. you specified a constraint saying $2x_1=4$ and maybe another saying $x_1+x_2=1$), those variables will be fixed at known values. A smaller problem will then be solved, and we will restore the values for the fixed variables when we report the solution (e.g. in this case $x_1=2$ and $x_2=-1$).

The cost of doing this for the solver is typically negligible (e.g. our Octeract Engine can reduce a 110K x 110K problem to 800 x 800 in about 1 second), but the overhead can become significant for massive problems. It's nearly always worth the time spent though because the problem becomes much easier to solve.

For "junk" variables, i.e., variables that are present but do not affect the problem in any way, we would typically remove them (if we can detect them) and report a value for them by convention at the end (e.g. 0,$\infty$). For the ones we can't detect, the feasible solution reported at the end would have some junk values.

From a modelling point of view it's usually best not to worry about such things and focus on getting the logic right, as long as the solver seems to be able to handle it.

If you see that the solver is beginning to struggle, you can help it out by removing redundant information. Free variables in particular can be quite nasty, especially in MINLP.

However, state-of-the-art solvers are generally pretty good at handling this stuff. If you notice that the solver is struggling it's more likely that there are deeper problems with your formulation that mere redundancy.

One subtle thing that I would point out here is that, although "fixable" variables are a non-issue for most solvers (unless the problem is in the millions of variables/constraints), having a model with a large amount of redundant information can make it very difficult for the modeller to improve/change the model, as it's very difficult to see what the degrees of freedom of your problem are.

$\endgroup$
1
  • $\begingroup$ Thanks for your answer Nikos. I upvoted and accepted it. $\endgroup$
    – PeterBe
    Jun 9 at 6:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.