2
$\begingroup$

I need to implement a load scheduling algorithm that involves solving an online optimisation problem from a research paper for my Real time systems course. This convex optimisation problem is setup through Model predictive control or receding horizon control. This problem involves under 100 decision variables. I am just googling about solvers and it would be great if you can give me more accurate suggestions about specific numerical solvers available in python for solving these kinds of cost functions (quadratic + one norm + infinity norm) and constraints (both equality and inequality). I think its convex (single minimum) because the author says so.

If you are an expert you dont have to read the contents below just click and look at the Optimzation problem formulation below and suggest to me a solver or links to a solver in python, Thanks :)

Optimzation problem formulation

constraints description

Full paper at this link: Full paper

Please see the cost function and constraints in the link above.

Brief description of the problem:

We want to schedule tasks (i.e. power allocation) that maximises power allocation from renewable sources, W to Electric vehicle (EV) loads, E that have some timing deadlines, di (due to running out of charge). We should minimize the use of grid energy sources, G and only use it in the worst case when EV load demand cannot be satisfied using renewable sources.

In the objective function the matrix W represents renewable energy/power allocation for task i at time step k. we look into N time steps into the future from the current time step, t. Say we have a renewable energy forecast chart that predicts the maximum output power at future times like in renewable generation forecast graph. Matrix G is grid generated power/energy also indexed similarly to W and is available at all times. Total power/energy supplied to load E is W + G. phi (flexibility factor) is the term that implicitly brings W into the cost fucntion. we try to keep phi large so that we can always defer load scheduling to future times if renewable power/energy is not sufficiently available for the time being and maybe available in the future. Note: the size/dimension (MXN) of matrix W and G is decreasing as we approach end of active tasks list in the time horizon N. As tasks in active tasks get completed and as we approach the last deadline in active task list M and N are decreasing.

In constraint 7, we put a cap on the maximum renewable energy available for all the M tasks up to N time steps using the renewable energy forcast data given below. renewable generation forecast graph constraint 8 is a conservation equation W and G power/energy supplied equals load energy required, E for the M tasks. In constriant 9 mi is maximum power that can be supplied to the load due to loads physical limitation. In contraint 10 and 11, di is the deadline of task i, delta t is time step for within which the optimisation must be solved. ei(k) is the remanining energy required for the task to complete.

From this description please suggest solvers or links to solvers that can be used in python.

Thank you!!

paper abstract

$\endgroup$
7
  • 2
    $\begingroup$ CVXPY may be the easiest way for you to formulate and enter your optimization problem, and solve it. There are several free solvers available under CVXPY, as well as some more robust and better performing commericlal solvers for which students can get a free license.PYOMO is another poissiility. $\endgroup$ – Mark L. Stone Feb 10 at 18:05
  • $\begingroup$ As @MarkL.Stone said, Pyomo is an option to write your model and it has GLPK as free, embedded solver. Another option could be using Gurobipy for modeling and then use Gurobi as the solver. Free trial licenses can be obtained from their website. $\endgroup$ – Oguz Toragay Feb 10 at 21:01
  • $\begingroup$ Thank you @OguzToragay. :) Btw will GPLK be suitable for the quadratic term in the cost function? $\endgroup$ – PcumP_Ravenclaw Feb 10 at 21:39
  • $\begingroup$ Thank you @MarkL.Stone for your comments. :) $\endgroup$ – PcumP_Ravenclaw Feb 10 at 21:40
  • $\begingroup$ @PcumP_Ravenclaw No Gurobi 9.1 supports quadratic functions. GLPK is good for linear terms only sorry I didn’t check the objective function... $\endgroup$ – Oguz Toragay Feb 10 at 21:41
2
$\begingroup$

Assuming you are writing the norms as explicit mathematical expressions (e.g. $|x_1|+|x_2|...$) you can just use our own Octeract Engine. As of next Monday (15 Feb 2021) it's free for everyone, and it will most likely destroy any problem that size, especially compared to any open source solver I could recommend as an alternative. It has a Python API, and also works with Pyomo.

If you do want to try open-source, the only alternative that I know of (although I'm sure there are others) that could handle the norm expressions out-of-the-box is Couenne, so you can also try that out. Couenne also works with Pyomo but AFAIK doesn't have a Python API.

$\endgroup$
1
  • $\begingroup$ Thanks for your reply. @NikosKazazakis $\endgroup$ – PcumP_Ravenclaw Feb 12 at 10:13

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.