in front of you are n pistons which can move up and down. consider the following:1) each piston start at some arbitrary height which you are given2) all the pistons are interconnected such that a move in one will also move the others to move. this relationship is given by the nxn matrix H.3) the cost of moving each piston is given by a nx1 vector Cgoal: find a constant K such that flattening the pistons to height = K is the cheapest currently, my knowledge toolbox only contains linear programming (simplex method) and quadratic programming. not sure how to approach this problem

i guess you take a ruler, place it horizontally over the pistons, then start pushing it down, until all pistons are at given hight K. that must be the cheapest path.

not necessarily...suppose the 1st piston is sticking out and the rest are already level. all pistons are independent. and the 1st piston is very expensive to move...it would be cheaper to raise the others rather than pushing down the first.anyhow, i was hoping for a mathematical solution rather than a practical one

My 2 c .the simplex method should be quite good (i think the Nelder Mead one).You put the constrain (your goal to reach) abs(x_n-K)=0 (the hyperplane at K) and you define in the merit function for the cost min( C_n)Something like that initial state = nxn matrix Hfinal state: nxn matrix with K in every elementcost: if you move the i piston then the cost is C_i merit function (your simplex surface): abs(K-H)+costs(i) (you have to consider a n+1D simplex, n for the number of pistonsd and other dimension to minimize for the step number Not really sure if it would works because I fear that your merit surface is highly not continous. in my case what i would try in MC method to try first and then coupled it with genetic optimimization.Example :You generate 500 paths (P_i) to arrive at K At each path you associate the cost C_i (maximum cost Cmax, min cost Cmin, average cost Cmean).You keep only the path with C_i [Cmin-Cmean] and then you check the similarity in those paths.Then you make "hybridation" of your path I mean you identify the bad "genes" and then you relaunch your MC simulation by only changing the bad genes and so one. It should converge to optimum but it is a quite hard method to implement.I advise you very much to put this problem in the brainteaser forum because I really think there is a kind of formula for that.

Maybe a stupid remark, but how can you even be sure that it is possible to get all the pistons at the same height? Since all pistons are interconnected and moving one piston makes all the others move, I think I could imagine a system where the pistons would never reach the same height, no matter what you do.I think you should first determine if they can reach the same height(s) and then worry about finding the cheapest height to do it. But I do realize this is not exactly the answer you are looking for.

QuoteOriginally posted by: FlyingDutchmanMaybe a stupid remark, but how can you even be sure that it is possible to get all the pistons at the same height? Since all pistons are interconnected and moving one piston makes all the others move, I think I could imagine a system where the pistons would never reach the same height, no matter what you do.I think you should first determine if they can reach the same height(s) and then worry about finding the cheapest height to do it. But I do realize this is not exactly the answer you are looking for.sorry i forgot to mention in the question. given the relationship matrix is invertible

QuoteOriginally posted by: iniestanot necessarily...suppose the 1st piston is sticking out and the rest are already level. all pistons are independent. and the 1st piston is very expensive to move...it would be cheaper to raise the others rather than pushing down the first.didn't you say the H was invertible? it'll be the same sh.t