sci.op-research

opresearchman wrote:
> On Mar 26, 4:50 am, Johan Löfberg wrote:
>> dallasfairb...@yahoo.com wrote:
>>> I have a problem with mixed integer-valued and real-valued decision
>>> variables. The problem has a wide variety of constraints, but all are
>>> linear. The objective function is composed of a subset of the
>>> decision variables and can be expressed as the sum of products of
>>> these variables:
>>> Minimize Sum_i ( Product_j x_i_j)
>>> Here "Sum_i" denotes the summation over the index "i." All the
>>> decision variables in the objective function are real-valued and
>>> between 0 and 1. I tried to use a piecewise linear approximation
>>> (exponentiating the log of the product) for the objective function,
>>> but that won't work. I won't explain why, but I expect that this
>>> won't surprise anyone.
>>> I know this is a nonlinear programming problem, but I'm hoping that
>>> someone has experience with this kind of nonlinear program. I know
>>> that the objective function is a posynomial, but that's the extent of
>>> my nonlinear programming knowledge. I'd appreciate any advice, any
>>> suggested references, or just gut feelings for solving such a problem
>>> to optimality.
>>> If I can't find a way soon, I'll have to make use of one or more
>>> heuristic methods (GA, Simulated Annealing, Tabu, GRASP, etc.). I'd
>>> also appreciate any thoughts on heuristic methods for such problems.
>>> Thanks in advance for any help.
>> Could you elaborate on "wide variety of constraints".
>>
>> If the linear constraints have a certain structure, you could be able to
>> rewrite the problem to a mixed integer geometric program, which can be,
>> if not efficiently, at least much more efficiently than a general MINLP.- Hide quoted text -
>>
>> - Show quoted text -
>
> I was hoping to avoid Mixed Integer Geometric Programming. I
> appreciate the advice though. There's a tutorial of GP on the web,
> and I've started reading it.
>
> It's a real problem; so, it's a little messy. I'll try to write out
> the formulation here. The decision variables are the z-values, D-
> values, h-values, y-values, b-values, x-values, and a-values.
> Everything else is a known quantity. Some info on the known values:
> the R-values are between 0 and 1, the alpha values are positive, the f-
> values are negative, the g-values are positive, and the F-values are
> all either 0 or 1. The f and g values are the slopes and y-intercepts
> respectively of a piecewise linear approximation. The set W is the
> set of indices for w and is partitioned into subsets:
> W = Union_m W(m)
> So, each value of the index m corresponds to one of these subsets, and
> I'm calling the subset W(m). Also, V is a subset of all the index
> values for the index j. All summations are over all indices unless
> otherwise noted. BIGM is the very large number that we all know and
> love.
>
> Minimize: Sum_j ( Product_m (z_j_m))
> Subject to:
> z_j_m = 1 - R_m * D_m_j, for all m and j
> 1-D_m_j = h_m_j, for all m and j
> b_m_j = Sum_(over w in W(m)) (y_w_j * alpha_w_j), for all m and j.
> f_k * b_m_j + g_k <= h_m_j, for all m, j, and k
> 0 <= h_m_j <= 1, for all m and j
> b_m_j >= 0, for all m and j
> y_w_l <= Sum_j (F_m_j_l * x_m_j), for all w in W(m), l in W, and all m
> Sum_j (x_m_j) <= 1, for all m
> Sum_m (a_m_j) = 1, for all j in V
> Sum_(over w in W(m)) (y_w_j) <= BIGM * a_m_j, for all j in V and all m
> a_m_j <= Sum_(over w in W(m)) (y_w_j), for all j in V and all m
>
> x_m_j = 0 or 1 for all m and j
> y_w_j = 0 or 1 for all w in W and all j
> a_m_j = 0 or 1 for all m and all j in V
> 0<= D_m_j <=1 for all m and all j
>
> Hopefully this doesn't confuse things. I have additional optional
> constraints for reducing the space of feasible solutions, but these
> are the essential ones. I'd be very thankful for any help.
>


If I am not mistaken, the constraint y_w_l <= Sum_j (F_m_j_l * x_m_j)
will destroy the GP structure, unless the cardinality on the right-hand
side is 1 for all constraints.

FYI, mixed integer GP examples and code is available here

http://control.ee.ethz.ch/~joloef/wiki/pmwiki.php?n=Tutorials.Geometric

You would probably benefit from performing some simple bound estimation
to avoid the large number (this can be done easily using the code).
Don't hesitate to contact me if you have any questions (it looks like an
interesting test-example)

Of course, if the problem is small enough, you can simply try to solve
it using a global solver