Re: Enumeration of Integer "solutions" of a convex set (Sort of Nonlinear programming, I think)
- From: Proginoskes <CCHeckman@xxxxxxxxx>
- Date: Fri, 10 Aug 2007 08:08:29 -0000
On Aug 9, 4:26 pm, Binesh Bannerjee <binesh-
dated-1187306204.f4f...@xxxxxxxxx> wrote:
Hi.
I have something that's sort of a nonlinear programming problem...
I have an objective function that's nonlinear (and not convex, or a
quadratic) and, the solutions I need should have integer parameters.
The _constraints_ however, are all linear. like
(a X + b Y + c >= 0, {X, Y} >= 0)
(There will almost certainly be more variables, but, around the order of
20 at the most)
So, there were two approaches I was thinking of. Maybe I'll just _see_ how
big the set of _all_ integer solutions is within that space, and maybe just
try them _all_ out. If the set is small enough, then I'll just do that.
So, the first question would be: How does one enumerate the set of integer
solutions within a convex set (made up of linear constraints)? In two-d,
given three points, I know how to test whether something is inside the
triangle or not. Is there an equivalent for n-dimensions?
Yes. You test ALL the linear inequalities in your system. (And note
that you won't necessarily get a triangle in 2-D.)
As to how to generate the solutions, well, choose all possible values
for your first variable (x_1), which your inequalities will hopefully
do, so that you know that x_1 is between A and B. Then for each i
between A and B, replace x_1 with i in the inequalities, simplify
them, and repeat for the n-1 variables you have left. Once you have
those, you can tack i on in front of the solutions. Then test your
point once more (verifying that all the inqualities are true is small
compared with the rest of the running time), and if all the inqualites
are true, output the point.
If that yields too many test cases tho, I suppose I'll have to look
into nonlinear/integer programming... Unfortunately, I'm not at a
stage where I could even properly formulate a question on that yet.
But, any books/websites pointers, suggestions whatever, would be
much appreciated!
You don't state what kind of function your objective function IS. You
say it's not linear, and not quadratic, but that's like saying that I
didn't have an apple for breakfast, in that you _still_ don't have an
idea what I ate.
--- Christopher Heckman
.
- References:
- Enumeration of Integer "solutions" of a convex set (Sort of Nonlinear programming, I think)
- From: Binesh Bannerjee
- Enumeration of Integer "solutions" of a convex set (Sort of Nonlinear programming, I think)
- Prev by Date: Why is it so difficult?
- Next by Date: Re: Fourier transform of a Cantor function
- Previous by thread: Enumeration of Integer "solutions" of a convex set (Sort of Nonlinear programming, I think)
- Next by thread: How can we prove this set is dense in R?
- Index(es):
Relevant Pages
|
