Prev: Extension of Variation vs Variation of Extension
Next: smallest gap for 253! = 10^500?? #4.09 Correcting Math
From: 海涛 朱 on 23 Jul 2010 17:14
On Jul 23, 3:35 pm, "Greg Neill" <gneil...(a)MOVEsympatico.ca> wrote:
> ?? ? wrote:
> > Let me make it more clear. How to get a solution for variables, that
> > maximun the positive number of variables. That means, make as much of
> > the variables positive. I think that's not linear problem
>
> It's a linear programming problem.
>
> It is equivalent to plotting the areas or volumes
> represented by each of the constraints on a set of
> multidimensional cartesian axes, then concentrating
> on the volume that represents the solution set (the
> set of points that could possibly satisfy all the
> constraints).  In that volume you want to look for
> the point that best satisfies your goal.  Often this
> point will lie at a vertex of the resulting volume's
> shape.

So, how about maximum the "count" of variables, instead of the value,
that are positive?
From: Ray Vickson on 23 Jul 2010 17:16
On Jul 23, 12:15 pm, 海涛 朱 <zhuht...(a)gmail.com> wrote:
> Let me make it more clear. How to get a solution for variables, that
> maximun the positive number of variables. That means, make as much of
> the variables positive. I think that's not linear problem

Sorry: I did not see this when I posted my previous message.

You should still use non-strict inequalities and require non-negative
variables. So, in abstract terms, your problem is: for inequalities
sum_{j} a_{i,j)*x_j <= b_i (i=1,...,m) and variables x_j >= 0
(j=1,...,n), maximize the number of positive x_j. If, *instead* of
asking whether x_j = 0 or x_j > 0 you pick some small e > 0 and
require that either x_j = 0 or x_j >= e, then you can model the
problem as a -mixed-integer_ programming problem: let y_j = 0 or 1 be
a binary variable. We want to have y_j = 0 if x_j = 0 and y_j = 1 if
x_j >= e. If you know a priori an upper bound U on the x_j (could have
a different U_j for each separate j), you can model this as: x_j <=
U*y_j and x_j >= e*y_j, x_j >=0, y_j = 0 or 1. Note that when y_j = 0
these say that x_j <= 0 and x_j >= 0 (hence x_j = 0), while when y_j =
1 they say x_j <= U (redundant) and x_j >= e. Now you want to maximize
sum y_j. So, the final formulation is max sum_{j} y_j, subject to
sum_{j} a_{i,j}*x_j <= b_i for i = 1, 2, ..., m, x_j >= 0, x_j <=
U*y_j, x_j >= e*y_j, y_j = 0,1 .

I think this is the best you can do (that is, either have x = 0 or x
>= e); the problem of having either x = 0 or x > 0 is not easily
formulatable in standard optimization form.

For more on mixed integer programming, see
http://www.sce.carleton.ca/faculty/chinneck/po/Chapter13.pdf (esp. >=
page 6) or
http://mat.gsia.cmu.edu/orclass/integer/integer.html .

R.G. Vickson
From: Greg Neill on 23 Jul 2010 18:17
?? ? wrote:
> On Jul 23, 3:35 pm, "Greg Neill" <gneil...(a)MOVEsympatico.ca> wrote:
>> ?? ? wrote:
>>> Let me make it more clear. How to get a solution for variables, that
>>> maximun the positive number of variables. That means, make as much of
>>> the variables positive. I think that's not linear problem
>>
>> It's a linear programming problem.
>>
>> It is equivalent to plotting the areas or volumes
>> represented by each of the constraints on a set of
>> multidimensional cartesian axes, then concentrating
>> on the volume that represents the solution set (the
>> set of points that could possibly satisfy all the
>> constraints). In that volume you want to look for
>> the point that best satisfies your goal. Often this
>> point will lie at a vertex of the resulting volume's
>> shape.
>
> So, how about maximum the "count" of variables, instead of the value,
> that are positive?

You "look" at the portion of the volume where there
are positive values. Check each volume vertex for
the count of positives. You may have to think up your
own search method, but you'll still want to narrow
the search area by constructing the solution set for
your constraints.


From: 海涛 朱 on 23 Jul 2010 18:21
On Jul 23, 5:16 pm, Ray Vickson <RGVick...(a)shaw.ca> wrote:
> On Jul 23, 12:15 pm, 海涛 朱 <zhuht...(a)gmail.com> wrote:
>
> > Let me make it more clear. How to get a solution for variables, that
> > maximun the positive number of variables. That means, make as much of
> > the variables positive. I think that's not linear problem
>
> Sorry: I did not see this when I posted my previous message.
>
> You should still use non-strict inequalities and require non-negative
> variables. So, in abstract terms, your problem is: for inequalities
> sum_{j} a_{i,j)*x_j <= b_i (i=1,...,m) and variables x_j >= 0
> (j=1,...,n), maximize the number of positive x_j. If, *instead* of
> asking whether x_j = 0 or x_j > 0 you pick some small e > 0 and
> require that either x_j = 0 or x_j >= e, then you can model the
> problem as a -mixed-integer_ programming problem: let y_j = 0 or 1 be
> a binary variable. We want to have y_j = 0 if x_j = 0 and y_j = 1 if
> x_j >= e. If you know a priori an upper bound U on the x_j (could have
> a different U_j for each separate j), you can model this as: x_j <=
> U*y_j and x_j >= e*y_j, x_j >=0, y_j = 0 or 1. Note that when y_j = 0
> these say that x_j <= 0 and x_j >= 0 (hence x_j = 0), while when y_j =
> 1 they say x_j <= U (redundant) and x_j >= e. Now you want to maximize
> sum y_j. So, the final formulation is max sum_{j} y_j, subject to
> sum_{j} a_{i,j}*x_j <= b_i for i = 1, 2, ..., m, x_j >= 0, x_j <=
> U*y_j, x_j >= e*y_j, y_j = 0,1 .
>
> I think this is the best you can do (that is, either have x = 0 or x>= e); the problem of having either x = 0 or x > 0 is not easily
>
> formulatable in standard optimization form.
>
> For more on mixed integer programming, seehttp://www.sce.carleton.ca/faculty/chinneck/po/Chapter13.pdf(esp. >=
> page 6) orhttp://mat.gsia.cmu.edu/orclass/integer/integer.html.
>
> R.G. Vickson

Thank you! But is there any tools that help to solve this kind of
problem?
From: Ray Vickson on 23 Jul 2010 18:32
On Jul 23, 3:21 pm, 海涛 朱 <zhuht...(a)gmail.com> wrote:
> On Jul 23, 5:16 pm, Ray Vickson <RGVick...(a)shaw.ca> wrote:
>
>
>
> > On Jul 23, 12:15 pm, 海涛 朱 <zhuht...(a)gmail.com> wrote:
>
> > > Let me make it more clear. How to get a solution for variables, that
> > > maximun the positive number of variables. That means, make as much of
> > > the variables positive. I think that's not linear problem
>
> > Sorry: I did not see this when I posted my previous message.
>
> > You should still use non-strict inequalities and require non-negative
> > variables. So, in abstract terms, your problem is: for inequalities
> > sum_{j} a_{i,j)*x_j <= b_i (i=1,...,m) and variables x_j >= 0
> > (j=1,...,n), maximize the number of positive x_j. If, *instead* of
> > asking whether x_j = 0 or x_j > 0 you pick some small e > 0 and
> > require that either x_j = 0 or x_j >= e, then you can model the
> > problem as a -mixed-integer_ programming problem: let y_j = 0 or 1 be
> > a binary variable. We want to have y_j = 0 if x_j = 0 and y_j = 1 if
> > x_j >= e. If you know a priori an upper bound U on the x_j (could have
> > a different U_j for each separate j), you can model this as: x_j <=
> > U*y_j and x_j >= e*y_j, x_j >=0, y_j = 0 or 1. Note that when y_j = 0
> > these say that x_j <= 0 and x_j >= 0 (hence x_j = 0), while when y_j =
> > 1 they say x_j <= U (redundant) and x_j >= e. Now you want to maximize
> > sum y_j. So, the final formulation is max sum_{j} y_j, subject to
> > sum_{j} a_{i,j}*x_j <= b_i for i = 1, 2, ..., m, x_j >= 0, x_j <=
> > U*y_j, x_j >= e*y_j, y_j = 0,1 .
>
> > I think this is the best you can do (that is, either have x = 0 or x>= e); the problem of having either x = 0 or x > 0 is not easily
>
> > formulatable in standard optimization form.
>
> > For more on mixed integer programming, seehttp://www.sce.carleton.ca/faculty/chinneck/po/Chapter13.pdf(esp. >=
> > page 6) orhttp://mat.gsia.cmu.edu/orclass/integer/integer.html.
>
> > R.G. Vickson
>
> Thank you! But is there any tools that help to solve this kind of
> problem?

Of course; see the links provided. The links are broken; they should
be

http://www.sce.carleton.ca/faculty/chinneck/po/Chapter13.pdf

and

http://mat.gsia.cmu.edu/orclass/integer/integer.html

You can even solve small-scale versions of the problem using the EXCEL
Solver, which might be good for problems having no more than about 10
a_i variables. This is for the built-in default version; you can
purchase larger versions that allow handling thousands of variables.

R.G. Vickson

First  |  Prev  | 
Pages: 1 2
Prev: Extension of Variation vs Variation of Extension
Next: smallest gap for 253! = 10^500?? #4.09 Correcting Math