2
$\begingroup$

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 iteratively on more constrained hardware. Unfortunately I cannot use an MILP solver on this hardware. 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$?

Improve this question
$\endgroup$
18
  • $\begingroup$ Welcome to OR.SE. You said Unfortunately I cannot use an MILP solver on this hardware. Would you elaborate more on how you can solve the problem as an LP, relaxed form, but cannot deal with BIP? $\endgroup$ Commented Feb 10 at 17:54
  • $\begingroup$ Currently the model is an MILP which I solve using Gurobi. My model is formulated in cvxpy and I use cvxpygen to generate efficient c-code. cvxpygen currently only supports convex (conic) solvers, namely: ECOS, OSQP and SCS. $\endgroup$ Commented Feb 10 at 17:57
  • 1
    $\begingroup$ Cross-posted at math.stackexchange.com/questions/5033604/…. $\endgroup$ Commented Feb 11 at 17:15
  • 1
    $\begingroup$ I'm not sure I understand what you mean. I don't need the entire solver in C. cvxpygen generates a custom solver that solves just my problem, and does nothing else. Here's some material by Boyd that explains what cvxpygen does: web.stanford.edu/~boyd/papers/cvxpygen.html $\endgroup$ Commented Feb 11 at 17:32
  • 1
    $\begingroup$ yes, there is a large application written in C that now also needs to solve an optimization problem. So basically what cvxpy does is it turns my problem into very low footprint C code. So I just have a solve() function + some functions to set new parameters values. That's exactly what I want, but it can't solve MILPs (yet). And maybe it never will, but I am confident I can find a way to solve this using just the LP solver + some reformulations or heuristics or post processing or whatever is needed. Solving it in the model formulation would be by far the most elegant ofcourse! $\endgroup$ Commented Feb 11 at 21:12

1 Answer 1

Reset to default
1
$\begingroup$

Since nobody has been able to provide an answer to this question, I thought I would summarize some of my findings.

So far I have not been able to find an elegant solution. I have however found a bunch of 'tricks', heuristics, relaxations etc. My (incompolete) list so far is:

  1. A promising method is the convex-concave procedure. See slides by Boyd's group for an introduction. The core idea is to use a binary relaxation, so that $x \in [0,1]$ and use g(x) = $\sum^n_i (x_i^2 - x_i)$. Then within a few iterations you should be able to find a solution where most of the $x$'s are (close to) integer. See slide 14.
  2. Instead of enforcing $x_i$ to be binary for every $i \in N$ with $N$ the horizon, only enforce that for the first few variables. For example enforce $x_1, x_2$ to be binary and $x_3, x_4, \dots, x_N \in [0,1]$. Then you would be left with only $2^2=4$ combinations to check, instead of $2^{96}$. I got this idea from https://help.juliahub.com/juliasimcontrol/stable/examples/minlp_mpc/#Speed-up-computation.
  3. Build your own version of branch and bound lite in C. Could be done, not easy.
  4. Use heuristic algorithms. For example simulated annealing.
  5. Relax and round, iteratively. Basically the dumbest thing you could think of but it might work.

I will add more options as I find them.

Improve this answer
$\endgroup$

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.