Suppose I have feasible linear programming problems $P_1, \dots, P_n$.
Say $f$ assigns a feasible linear program its optimum value. How can I find a linear program $P'$, such that $f(P') = max(f(P_1), \dots, f(P_n))$? Preferably $P'$ is of size polynomial in the sizes of the $P_i$.
You can use a distinct set of variables for each linear program, and combine all the constraints. Then this will give you the concatentation of feasible solutions as the set of feasible solutions. Then, for each objective vector $c_j$, take the variables $x_i$ that correspond to that linear program, and set a constraint $y \geq \sum_i c_{ji} x_i$. Then set your objective function to be a huge constant times the sums of objective functions for your linear program, minus $y$. Then this linear program will optimize all your linear programs and then set $y$ to be the maximum value, because of the huge constant you put on the sum of objective values. This is almost what you asked for; $y$ stores the maximum value even though the objective function is not $y$. I believe the only way to get $y$ to be the objective function is if you wanted to take a min of max values, or a max of min values.
