Go Down

### Topic: Linear Programming (optimization) code to find a maximum/minimum of a function (Read 8645 times)previous topic - next topic

#### GelOP

Hello,
I am trying to create a code to Arduino be able to find a maximum or minimum of a function subject to constraints like the following example:

/* Objective function */
max: +143 x +60 y;

/* Constraints */
+120 x +210 y <= 15000;
+110 x +30 y <= 4000;
+x +y <= 75;

Has anyone done something similar?  The Arduino is capable to calculate the minimum of a function with 300 variables?

#### pylon

The problem lies between keyboard and chair. That's not a job for an embedded controller but usually for a capable programmer, that knows a bit about algebra, or if the programmer is not capable of doing it, for a PC running some kind of algebra software like Mathematica.
That's not a moving target, that's a static calculation.

#### nid69ita

Has anyone done something similar?  The Arduino is capable to calculate the minimum of a function with 300 variables?

For me is not clear the first question.

For second question (I think is a different problem !?!)
a. the minimum of 300 value?  you can store value on array and after with a for made a search on array.
b. a function with 300 parameters ? Are you able to write a function with 300 parameters?
void funz(int p1,int p2, int p3...etc )

my name is IGOR, not AIGOR

#### PeterH

I am trying to create a code to Arduino be able to find a maximum or minimum of a function subject to constraints like the following example:

I suppose you could tackle the problem using a 'brute force' approach of evaluating your function with argument values covering the domain of values that meet your criteria, but it would be a very crude way to tackle the problem, and even if you took this approach it's not obvious why you'd need to involve an Arduino.

I would have thought that the more sensible approach would have been to solve the equation algebraically to find the maxima and minima within the domain defined by your constraints. That doesn't seem to require anything more than a pen and paper, and perhaps a calculator, and the ability to do algebra.

#### KeithRB

I would suggest the steepest decent method. And, assuming it is a polynomial , I would derive formulas for the partials to make calculating the gradient go *much* faster.

This is what my HP-71 uses.

But this is *really* not very well suited for an Arduino. I hope you don't want to do this with "300 variables" in real time!

http://en.wikipedia.org/wiki/Steepest_descent

#### robtillaart

Quote
The Arduino is capable to calculate the minimum of a function with 300 variables?

Can you give their name and type please?

I assume you will use a global array of integers for your variables.

int var[300];  // 600 bytes

// for the search range per param
int rangeBegin[300]; // 600 bytes
int rangeEnd[300]; // 600 bytes

In total 1800 bytes. Given the fact that an UNO has only 2K RAM you should at least go for a MEGA.

Then there is the question if the parameters have a linear behavior or polynomal, power or exponential

Think I would go for an heuristic or genetic algorithm, generate random parameters and compare that with the previous version. Remember the best.
Then you only need to have an array with the best value so far, so an UNO would do. Problem is that it will converge very slowly and slower as time passes.
Rob Tillaart

Nederlandse sectie - http://arduino.cc/forum/index.php/board,77.0.html -
(Please do not PM for private consultancy)

#### GelOP

Thanks for all replies.

I will give some more details about my project.

The optimization that I am trying to do is linear (all the function and constraints are linear). My objective function have 300 variables because I am using predictive control and I have to predict the value of 6 different variables 50 steps ahead and I have to repeat this process every 5 minutes.

The variables are floats that represent irradiation, water temperature and flow.

At this moment I am doing the optimization in a computer using Matlab, and I am using serial communication to send data between the arduino and the computer. Because my project will be implement in houses, it is required the lowest cost as possible, so I am trying a way to do all the optimization inside of arduino, withou using a computer.
One possible solution is to use a raspberry, but I will only use that if the arduino proved to be incapable of solving this linear programming.

#### el_supremo

Quote
I am trying to create a code to Arduino

The first thing to decide is whether you can write a 300-variable min/max program in C/C++ for any computer. If so, write it for a PC (or MAC) and get it working there first.
THEN you will be able to determine whether it can be ported to an Arduino, R-Pi, whatever.

Pete
Don't send me technical questions via Private Message.

#### robtillaart

Quote
The variables are floats that represent irradiation, water temperature and flow

300 floats => 1200 bytes  definitely no uno

however it are in fact 6 variables and you want 50 extrapolations if I understand.
Can you explain why you want 50 extrapolations?
should 10 work to (and then every minute)?
should 1 work every 5 seconds?
Rob Tillaart

Nederlandse sectie - http://arduino.cc/forum/index.php/board,77.0.html -
(Please do not PM for private consultancy)

#### nid69ita

#9
##### Jul 02, 2013, 11:09 pmLast Edit: Jul 03, 2013, 09:24 am by nid69ita Reason: 1

... I am trying a way to do all the optimization inside of arduino, withou using a computer.
One possible solution is to use a raspberry, but I will only use that if the arduino proved to be incapable of solving this linear programming.

Arduino is NOT a computer like a PC. Is not so powerful. It's a 8 bit MCU, very slow and with few memory (2K ram and 32K for program) and is absent the arithmetic coprocessor.
my name is IGOR, not AIGOR

#### GelOP

Thanks el_supremo and robtillaart.

Quote
The variables are floats that represent irradiation, water temperature and flow

300 floats => 1200 bytes  definitely no uno

however it are in fact 6 variables and you want 50 extrapolations if I understand.
Can you explain why you want 50 extrapolations?
should 10 work to (and then every minute)?
should 1 work every 5 seconds?

I am not doing extrapolations, I am using the information that I received from the sensors to predict the future value of the temperature and flow. In other words, I am measuring a temperature inside of a tank and I am trying to figure out what will be the next 50 measurement considering some restrictions.
Using 50 predictions (and considering that I am using processing it every 5 minutes) I can estimate the future value of the temperature in the next 5, 10, 15, 20, ..., 240, 245 and 250 minutes ahead. That is the reason I can not do 1 process every 5 seconds.

The arduino that I am using is Mega, so I guess I have enough memory to do deal with the variables, however I not sure if it supports the whole math.

#### nid69ita

Arduino support float but not double. Are you sure that float calculations are enough?
my name is IGOR, not AIGOR

#### holmes4

@nid69ita

Quote
Arduino is NOT a computer. Is not so powerful. It's a 8 bit MCU, very slow and with few memory (2K ram and 32K for program) and is absent the arithmetic coprocessor.

The Atmel AVR chips used in the uno/mega are in every way computer!, they are NOT 8 bit processors the program memory is 16 bits wide. See the datasheet, instructions working with bytes are executed in 1 clock cycle including instruction fetch.

Mark

#### holmes4

THe Due should be able to cope with the OP's problem.

Mark

#### nid69ita

#14
##### Jul 03, 2013, 09:19 amLast Edit: Jul 03, 2013, 09:25 am by nid69ita Reason: 1

@nid69ita
Quote
Arduino is NOT a computer. Is not so powerful. It's a 8 bit MCU, very slow and with few memory (2K ram and 32K for program) and is absent the arithmetic coprocessor.

The Atmel AVR chips used in the uno/mega are in every way computer!, they are NOT 8 bit processors the program memory is 16 bits wide. See the datasheet, instructions working with bytes are executed in 1 clock cycle including instruction fetch.
Mark

My English is terrible, but I attach the first page of datasheet from AtMel, first line:
Features: • High Performance, Low Power AVR® 8-Bit Microcontroller

The my sentence "Arduino is NOT a computer" has a part not expressed, "like a PC" but implied.
And here the wiki for MCU or microcontroller (a special CPU). And, strange, for example you can see Atmel mcu.
http://en.wikipedia.org/wiki/Microcontroller
my name is IGOR, not AIGOR

Go Up