sci.op-research

On Mar 26, 4:50=A0am, Johan L=F6fberg wrote:
> dallasfairb...@yahoo.com wrote:
> > I have a problem with mixed integer-valued and real-valued decision
> > variables. =A0The problem has a wide variety of constraints, but all are=

> > linear. =A0The 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." =A0All the
> > decision variables in the objective function are real-valued and
> > between 0 and 1. =A0I tried to use a piecewise linear approximation
> > (exponentiating the log of the product) for the objective function,
> > but that won't work. =A0I 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. =A0I know
> > that the objective function is a posynomial, but that's the extent of
> > my nonlinear programming knowledge. =A0I'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.). =A0I'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 =3D 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 =3D 1 - R_m * D_m_j, for all m and j
1-D_m_j =3D h_m_j, for all m and j
b_m_j =3D Sum_(over w in W(m)) (y_w_j * alpha_w_j), for all m and j.
f_k * b_m_j + g_k <=3D h_m_j, for all m, j, and k
0 <=3D h_m_j <=3D 1, for all m and j
b_m_j >=3D 0, for all m and j
y_w_l <=3D 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) <=3D 1, for all m
Sum_m (a_m_j) =3D 1, for all j in V
Sum_(over w in W(m)) (y_w_j) <=3D BIGM * a_m_j, for all j in V and all m
a_m_j <=3D Sum_(over w in W(m)) (y_w_j), for all j in V and all m

x_m_j =3D 0 or 1 for all m and j
y_w_j =3D 0 or 1 for all w in W and all j
a_m_j =3D 0 or 1 for all m and all j in V
0<=3D D_m_j <=3D1 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.