1

I want to do the following:

max: greatest(a1+b1+c1, a2+b2+c2, a3+b3+c3);
... constraints involving a1,a2,a3,b1,b2,b3,c1,c2,c3...

Since there is no greatest() function, I restructured it like this:

max: greatest_val;
greatest_val >= a1+b1+c1;
greatest_val >= a2+b2+c2;
greatest_val >= a3+b3+c3;
... constraints involving a1,a2,a3,b1,b2,b3,c1,c2,c3...

But this leads to a boundless problem as greatest_val can go to infinity.

How do I structure this problem so that it has upper and lower bounds??

Thanks in advance.

Antony Paul
  • 23
  • You're maximizing a convex function, so it's not a convex problem. Where does the problem come from? – littleO May 06 '15 at 10:02
  • @littleO

    I dont understand what you asked.

    I am a programer trying to solve the above problem using lp_solve (gplk). But when I run the above problem, I get this error: This problem is unbounded

     – Antony Paul May 06 '15 at 10:15
  • In a convex optimization problem, you minimize a convex function (or, equivalently, maximize a concave function). But if you want to maximize a convex function, then that is not a convex optimization problem, and so it might be much more difficult than simply solving a linear program. The function $f = \max(a_1 + b_1 + c_1,a_2 + b_2 + c_2,a_3 + b_3 + c_3)$ is convex, not concave, so maximizing $f$ is not a convex problem (and can't be solved using linear programming). However, if you have a small number of variables in your problem then other methods might work. – littleO May 06 '15 at 10:24
  • Are you sure this is really the problem you want to solve? The fact that it's not a convex optimization problem suggests that perhaps you should be solving a different problem. – littleO May 06 '15 at 10:25
  • Thank you for the reply. The problem I gave in the question is a very simplified version of what I am trying to do. The original problem contains more than 500 variables and more than 1000 constraints.

    This is the original problem: http://math.stackexchange.com/questions/1248146/which-optimization-class-does-the-following-problem-falls-into-lp-mip-cp-a

    I have been able to tackle several of the issues. But I am stuck at maximizing the maximum which is an integral part of the problem.

    Perhaps the problem (given in the link) is not an LP ?

     – Antony Paul May 06 '15 at 10:33

2 Answers2

2

It may seem strange, but you should try to minimise greatest_val. This will give you the smallest of the possible maxima. It is sometimes called a minimax problem.

tomi
  • 9,594
1

I like Tomi's suggestion for finding the smallest "greatest_val" that is at least as big as all of the individual sums. As an alternative, if you have access to routines that solve mixed integer linear programs, you might consider the following reformulation of your problem:

Define a new set of indicator variables $k_i$ and redefine your objective function as $\sum_{i=1}^{N}k_i(a_i+b_i+c_i)$ where $N$ represents the number of $(a,b,c)$ triples that you have. Define each $k_i$ to be either $0$ or $1$ (binary) and add the constraint that $\sum_{i=1}^{N}k_i=1$. Along with the binary constraints this additional constraint says that exactly one value of $k_i$ can be equal to $1$ and all the rest will be $0$.

You would keep all of the other constraints that you already have. Maximizing this new objective function will then seek to find the optimal $k_i$ and thus the largest value that $a_i+b_i+c_i$ can take on, subject to all the other constraints. If the problem is feasible then this should work for you.

SWilliams
  • 639
  • Thank you for your reply

    We have already tried that. But the problem is neither mathprog nor lpsolve allow us to multiply between two variables. They only allow multiplication between a constant and a variable.

    ie

    x >= k1 * a1 -> Not allowed
    x >= 2 * a1 -> Allowed

    Another complication is values of a1,a2,a3,b1,b2,b3,c1,c2,c3...should selected based on a large number of constraints which I did not include here

    This is the actual problem I am trying to solve: http://math.stackexchange.com/questions/1248146/which-optimization-class-does-the-following-problem-falls-into-lp-mip-cp-a

     – Antony Paul May 07 '15 at 08:58