1
$\begingroup$

Crossposted at Operations Research SE

I am attempting to optimize the operation of an electrical system that produces some amount of thermal power $P_t$ and keeps a temperature $x_t$ within a certain range. Given a cost vector $\mathbf{c} \in \mathbb{R}^n$, bounds $P_{\max} > P_{\min} > 0$ and a time horizon ${\Bbb T} \in {\Bbb Z}$, I have the following mixed-integer linear program (MILP)

$$ \begin{array}{rl} \underset{\mathbf{P} \in \mathbb{R}^n, z_t \in \{0,1\}}{\text{minimize}} &\quad \mathbf{c}^\top \mathbf{P}\\ \text{subject to} & z_t P_{\min} \leq P_t \leq z_t P_{\max} \quad &\forall t \in {\Bbb T}\\ & x_{t+1} = A x_t + BP_t \quad &\forall t \in {\Bbb T}\\ & x_\min \leq x_t \leq x_\max \quad &\forall t \in {\Bbb T}\\ \end{array} $$

where the binary variable $z_t \in \{0,1\}$ indicates whether the machine is on or off at time $t$:

  • when it is on, $P_t \in [P_{\min}, P_{\max}]$
  • when it is off, $P_t = 0$

My time horizon $\Bbb T$ can have up to 96 time indices, so that would result in a combinatorial problem with $2^{96}$ options. Yet, Gurobi can solve this problem globally in milliseconds.

Real-time optimization

I can solve the MILP offline without any issues, but now it has to run on an embedded controller. The temperature dynamics are rather slow, so I don't have any strict timing constraints. But I would like to relax the binary constraint so I don't have to deal with the combinatorial part.

I assumed this kind of situation would turn up in practice all the time, but I have yet to find a good solution. Of course, I could just relax the binary variable to $z_t \in [0,1]$ but wouldn't that produce infeasible solutions $0 < P < P_\min$?

I need to relax the problem because I currently don't have a good method to solve MILPs on the target embedded platform. For context, I use CVXPY to write the model and CVXPYgen to generate the C code. CVXPYgen does not have a stable solver for MILPs. The solver ECOS_BB is available, but it is not stable. I would greatly appreciate any tips to solve this.

$\endgroup$
10
  • $\begingroup$ You might want to take a look at CVXPY course at NASA $\endgroup$ Commented Feb 10 at 12:19
  • $\begingroup$ Thank you, I am going through the material. I think what I ultimately need is a convex hull of my original problem. $\endgroup$ Commented Feb 10 at 13:47
  • 1
    $\begingroup$ Because you could potentially violate $x_\max$, and turning on would always cost money. $\endgroup$ Commented Feb 10 at 14:24
  • 1
    $\begingroup$ Turning on is not penalized, producing power is penalized. Turning on implies $P \in [P_\min, P_\max]$. Hence you always at least pay the price associated with $P = P_\min$. $\endgroup$ Commented Feb 10 at 14:42
  • 1
    $\begingroup$ Cross-posted at or.stackexchange.com/questions/12908/…. $\endgroup$ Commented Feb 11 at 17:16

1 Answer 1

Reset to default
1
$\begingroup$

It appears to me that this problem is essentially a network flow problem with gains (the $A$ matrix being the gain). My understanding is that such problems are very easy to solve (low order polynomial time), and this is corroborated by your experience. You might not need to relax the problem at all.

If you have to relax the problem, I would suggest reducing the time horizon (96). This would give somewhat myopic solutions, but these might be good enough.

$\endgroup$
1
  • 1
    $\begingroup$ I need to relax the problem because I currently don't have a good method to solve MILPs on the target embedded platform. For context, I use cvxpy to write the model and cvxpygen to generate the C code. cvxpygen does not have a stable solver for MILPs. ECOS_BB is available, but it is not stable. $\endgroup$ Commented Feb 10 at 11:13

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.