2

I would like to know what methods are applied for optimizing multi-variable expressions with a defined target.

I have a specific example I need help with, but I would like to be pointed into the right direction to apply the theory elsewhere.

The expression I need to optimize is given in the following equation:

$$t = \frac {2x + 2y + z + i + j +k} 4$$

Here all the variables including the target are constrained to be integers between 0 and 100 inclusive. (Apologies for not knowing how to express that symbolically)

So in summary I would like to know how to optimize this particular example, what branch of mathematics this type of problem is classified under? Also, What methods are typically used to solve problems like this?

Daniel Dunn
  • 23

1 Answers1

1

EDIT: I'm updating this to reflect the comments below.

If your constraints and objective function are all linear, then you can use linear programming. If all (or some) of the variables are further constrained to be integers, then you can use integer programming techniques.

As @Michael Grant comments, it seems that you're trying to minimize the maximum of the variables. You can achieve this by creating an artificial variable $M$ and minimizing it, thus:

$$ \begin{align} \textrm{Minimize}\quad & M\\ \textrm{subject to}\quad & \frac {2x + 2y + z + i + j +k} 4 - t = 0\\ & x \leq M\\ & \ldots\\ & k \leq M\\ & M \leq 100\\ \textrm{and}\quad &t, \ldots, k \in \mathbb Z^+ \end{align}$$

Théophile
  • 24,627
  • Apologies for the lack of clarity in my question, as I am unsure of the nature and typical form of the problem itself.

    The objective is to find, algebraically, what is the minimum value each variable can hold to satisfy the condition with a given value for $t$.

    In your example you state the solution as assigning a value to each of the variables to satisfy the condition.

    What it doesn't show (as far as I can see) is how the values are found systemically and if they are each minimal.

     – Daniel Dunn Apr 24 '15 at 13:02
  • What do you consider a minimal solution when there are multiple variables? Take a simpler problem like $x+y=10$, where we're looking for "minimum values" of positive integers $x$ and $y$. Is $(0,10)$ minimal? What about $(10,0)$ or $(5,5)$? – Théophile Apr 24 '15 at 13:08
  • Also, in my example, I set the variables to a given value because the problem as I wrote it (which is different from what you intended, I think) is trivial. If you did want to actually solve it systematically, you would use the techniques described in the Wikipedia link I gave. – Théophile Apr 24 '15 at 13:10
  • In the simpler case you state, the "minimal" solution would be where $x = 5$ and $y = 5$ because both values are the as small as they can be whilst satisfying the condition $x+y =10$ – Daniel Dunn Apr 24 '15 at 13:15
  • So in other words you are looking to minimize $\max{x,y,z,i,j,k}$. – Michael Grant Apr 24 '15 at 15:03
  • Thanks for the clarification. I've updated my answer. – Théophile Apr 24 '15 at 15:12