Pages: [1] 2   Go Down
Author Topic: Linear Programming (optimization) code to find a maximum/minimum of a function  (Read 1412 times)
0 Members and 1 Guest are viewing this topic.
Offline Offline
Newbie
*
Karma: 0
Posts: 3
View Profile
 Bigger Bigger  Smaller Smaller  Reset Reset

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?
Logged

Switzerland
Offline Offline
Faraday Member
**
Karma: 96
Posts: 4702
View Profile
 Bigger Bigger  Smaller Smaller  Reset Reset

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.
Logged

ivrea (to)
Offline Offline
Faraday Member
**
Karma: 57
Posts: 3526
miaaao ^-^
View Profile
 Bigger Bigger  Smaller Smaller  Reset Reset

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 ) ???

 
Logged

my name is IGOR, not AIGOR

UK
Offline Offline
Shannon Member
****
Karma: 184
Posts: 11173
-
View Profile
 Bigger Bigger  Smaller Smaller  Reset Reset

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.
Logged

I only provide help via the forum - please do not contact me for private consultancy.

Offline Offline
Edison Member
*
Karma: 18
Posts: 1170
View Profile
 Bigger Bigger  Smaller Smaller  Reset Reset

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
Logged

Global Moderator
Netherlands
Online Online
Shannon Member
*****
Karma: 170
Posts: 12457
In theory there is no difference between theory and practice, however in practice there are many...
View Profile
 Bigger Bigger  Smaller Smaller  Reset Reset

Quote
The Arduino is capable to calculate the minimum of a function with 300 variables?
Can you give their name and type please? smiley-wink

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.
Logged

Rob Tillaart

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

Offline Offline
Newbie
*
Karma: 0
Posts: 3
View Profile
 Bigger Bigger  Smaller Smaller  Reset Reset

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.
Logged

Offline Offline
Edison Member
*
Karma: 35
Posts: 1419
View Profile
 Bigger Bigger  Smaller Smaller  Reset Reset

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
Logged

Where are the Nick Gammons of yesteryear?

Global Moderator
Netherlands
Online Online
Shannon Member
*****
Karma: 170
Posts: 12457
In theory there is no difference between theory and practice, however in practice there are many...
View Profile
 Bigger Bigger  Smaller Smaller  Reset Reset

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?
Logged

Rob Tillaart

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

ivrea (to)
Offline Offline
Faraday Member
**
Karma: 57
Posts: 3526
miaaao ^-^
View Profile
 Bigger Bigger  Smaller Smaller  Reset Reset

... 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.
« Last Edit: July 03, 2013, 02:24:10 am by nid69ita » Logged

my name is IGOR, not AIGOR

Offline Offline
Newbie
*
Karma: 0
Posts: 3
View Profile
 Bigger Bigger  Smaller Smaller  Reset Reset

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.
Logged

ivrea (to)
Offline Offline
Faraday Member
**
Karma: 57
Posts: 3526
miaaao ^-^
View Profile
 Bigger Bigger  Smaller Smaller  Reset Reset

Arduino support float but not double. Are you sure that float calculations are enough?
Logged

my name is IGOR, not AIGOR

Poole, Dorset, UK
Offline Offline
Edison Member
*
Karma: 25
Posts: 1873
View Profile
 Bigger Bigger  Smaller Smaller  Reset Reset

@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
Logged

Poole, Dorset, UK
Offline Offline
Edison Member
*
Karma: 25
Posts: 1873
View Profile
 Bigger Bigger  Smaller Smaller  Reset Reset

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

Mark
Logged

ivrea (to)
Offline Offline
Faraday Member
**
Karma: 57
Posts: 3526
miaaao ^-^
View Profile
 Bigger Bigger  Smaller Smaller  Reset Reset

@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


* Immagine.GIF (39.91 KB, 681x524 - viewed 19 times.)
« Last Edit: July 03, 2013, 02:25:52 am by nid69ita » Logged

my name is IGOR, not AIGOR

Pages: [1] 2   Go Up
Jump to: