IBM to the rescue

Our research laboratory uses a large variety of programming and scripting languages to run simulations, mine data, analyse results and find optimised solutions. The two languages I begun to like most are MATLAB and Python. They both are easy to lean and use, and they both have powerful toolboxes and modules that extend the basic functions of MATLAB and Python, respectively. Nonetheless, for most initial implementations we frequently choose MATLAB over Python since it provides a (in my view) cleaner way to do large matrix manipulation and complex optimisation calls. Once we solved the problem on a theoretical level, we then proceed to stage two, where Python accelerates the computation (especially when we deploy it on our compute cluster HTCondor).

However, with the most recent problem we had to tackle, transition from step one to step two was not straight forward. We had to assure all components operate correctly, and that our solver could find a solution. Yet with an increasing number of input parameters, the developed procedure took more and more time to solve. In fact, the increase in time was exponential as the number of parameters increased – not good. So what could we do now?

Deadlines were coming up and we needed to solve problems lasting several weeks, however a solution may only be returned after several days of computation. At this hopeless moment in time, one of my colleagues suggested an amazing tool called CPLEX by IBM; she really saved us, because it’s free for academics and works so much quicker than MATLAB  (get it here). So, if you are interested in the mathematical problem we wanted to solve, why it is difficult to solve it, how CPLEX performed in comparison to native MATLAB solvers, and how to acquire CIPLEX and use it within your MATLAB code, then you have come to the right post.

The problem at hand

In the world of resource management for electricity and energy grids, generators need to plan ahead so that they can operate their generators when needed. Usually this is done using a forecast, yet these forecasts are inaccurate to some degree. Therefore, generators do not state how much energy they will provide, but whether their units will be active or “committed” during a certain time. Whenever units are committed, these they can provide any amount of energy within their operational limits, and the operators can plan for these periods of operation by assuring enough resources are made available. For example, if a hydro-electric plant was committed for a few hours in the future, then the operator could make sure that enough water is in its water reservoir, i.e. the resource is sufficient.

With multiple generators operating at different costs and emission levels, a solver had to be used in order to address this complex “Unit Commitment” (UC) problem. We decided to choose a “Mixed Integer Linear Programming” (MILP) approach that has a simple (yet powerful) function in MATLAB called intlinprog():

[x, fval, exitflag, output] = intlinprog(f, intvars, A, b, Aeq, beq, lb, ub);

Here, we only use the following variables:

  • x which is the output to the UC problem (math: \textbf{x})
  • intvars defining which values are integers (here, all values – math: \textbf{i})
  • f which are the costs associated to generator commitment (math: \textbf{f})
  • A and b which define the inequality constraints (math: \textbf{A} and \textbf{b})
  • lb and ub which limit the solution space (to make it binary – math: \textbf{b}_l and \textbf{b}_u)

The mathematical formula (including the unused linear constraints \textbf{A}_{eq} and \textbf{b}_{eq}), explaining what needs to be minimised would look as follows:

\min_{\textbf{x}}\left(\textbf{f}^{T}\textbf{x}\right)\text{ subject to }\begin{cases}x(i) \in \mathbb{Z}\\\textbf{A}\cdot\textbf{x}\leq\textbf{b}\\\textbf{A}_{eq}\cdot\textbf{x}=\textbf{b}_{eq}\\\textbf{b}_l\leq\textbf{x}\leq\textbf{b}_u\end{cases}

This looks rather neat and simple, but… The inequality constraints \textbf{A} and \textbf{b} for instance can become insanely large. The current average sizes are:

size(A)
ans =
963526 683280

size(b)
ans =
963526 1

If these matrices were stored as simple arrays of 8bit integers, more than 600GB of storage would be needed. Luckily, MATLAB‘s space matrices can handle these matrices within relative ease and eventually solve the MILP problem; but at what cost?

CPLEX vs MATLAB

Solving our UC problem for a single day or two reduces the size of the arrays quite significantly. Therefore, a solution is achieved within a minute. Yet if we increase the number of days, this is the trend we observe:


Running time vs number of days (average time in red)

Note that the Y-axis has a logarithmic scale. I ran 50 MILP solves for different consecutive combinations of days and noted the time it took to solve. When reaching 16 days solving took so long that it was not feasible to continue. It looks like the time it takes to solve increases exponentially with number of days, and the spread in computation time becomes wider, too. If this trend continues (and we suspect it will) then solving for 365 days will take something between 0.63 days and 2800 years (depending on what polynomial order we extrapolate).

So we installed IBM’s CPLEX solver and ran its corresponding “Binary Integer Linear Programming” (BILP) solver. Its function call uses the exact same underlying maths and is therefore surprisingly similar to MATLAB‘s function call:

[x, fval, exitflag, output] = cplexbilp(f, A, b, Aeq, beq, x0, options);

Since the output has to be a binary vector, we need not restrict x using intvars, lb and ub. However, you need to specify some starting conditions in x0, but that can just be a simple vector of zeros. Solving is now significantly accelerated:

Running time vs number of days (average time in red)

I only ran multiple simulations up to half a year, yet you can already see how much quicker and reliable IBM’s solver operates. In fact, running a single year took less than 12 minutes (on a virtual machine on my MacBook Pro). CPLEX is therefore an amazing, “plug and play” like tool that just works; and it works really well!

Getting CPLEX

As you probably know by now, CPLEX is amazing. But how do you get it, and use it in MATLAB? Simple… follow the link on IBM’s website:

https://www.ibm.com/developerworks/community/blogs/jfp/entry/CPLEX_Is_Free_For_Students

Then register with your student email, which must end in @xxx.edu or @xxx.ac.uk to assure you are an enrolled student or member of staff at university. After confirming your email address, you can download the installer for “IBM ILOG CPLEX Optimization Studio 12.7.1 – Student (CJ1HQML)” for free (12.7.1 may change based on the latest version available at the time you read this). Run the setup and you are done with the acquisition of CPLEX.

In MATLAB all you need to do is add the CPLEX toolbox to the search path. This can be done by adding this simple line of code:

addpath('C:\Program Files\IBM\ILOG\CPLEX_Studio1271\cplex\matlab\x64_win64');

Keep in mind, that this path may be different for different versions of CPLEX. To find the correct path to the CPLEX toolbox, navigate to the folder into which you previously installed CPLEX Studio. Then look for the matlab directory, and inside it, and choose the folder of matching system architecture (in my case it was x64_win64). Once you assured that the addpath(); function uses the correct path to this folder, you are done and good to go.

Further information can be found on IBM’s CPLEX for MATLAB page (for version 12.7.1: link). Now however, my break for lunch (during which I wrote this post) is definitely over, and I shall resume my work. I wish you much fun solving problems, “gerfficiently” 😉

Leave a Reply

*
*