| |
 |
|
|
Science Forum Index » Math - Numerical Analysis Forum » Combinatorial Optimization Problem
Page 1 of 1
|
| Author |
Message |
| Jürgen Womser-Schütz |
 Posted: Thu Mar 01, 2007 9:54 am |
|
|
|
Guest
|
Hello,
I seek an algorithm or a strategy to find a good solution for the
following difficult problem.
Given is R^K, an affine subspace S of R^K with dim(S)=K-2 and
a compact grid G in R^K.
The grid G is generated by N numbers (same numbers in each coordinate).
The problem is to find the point of the grid which is near to S
(L_2 norm or if not possible L_1 norm).
The distance of an point in G to the affine subspace S can be calculated
using the orthogonal projection on the corresponding linear subspace S'.
But it is not possible to do this calculation for each point, because
the number of points is too large (K ~ 20 and N ~ 10).
I would be happy to have an efficient iterative algorithm which improves
a given initial solution.
Has somebody an idea?
Thanks in advance, Jürgen
PS: Prof. Spellucci told me some days ago that the problem is in the
field of integer optimisation. But I think it is not even a linear problem. |
|
|
| Back to top |
|
| Peter Spellucci |
| Posted: Thu Mar 01, 2007 9:54 am |
|
|
|
Guest
|
In article <es6lvi$iaa$1@news.albasani.net>,
=?ISO-8859-15?Q?J=FCrgen_Womser-Sch=FCtz?= <jws1954@gmx.e> writes:
Quote: Hello,
I seek an algorithm or a strategy to find a good solution for the
following difficult problem.
Given is R^K, an affine subspace S of R^K with dim(S)=K-2 and
a compact grid G in R^K.
The grid G is generated by N numbers (same numbers in each coordinate).
The problem is to find the point of the grid which is near to S
(L_2 norm or if not possible L_1 norm).
The distance of an point in G to the affine subspace S can be calculated
using the orthogonal projection on the corresponding linear subspace S'.
But it is not possible to do this calculation for each point, because
the number of points is too large (K ~ 20 and N ~ 10).
I would be happy to have an efficient iterative algorithm which improves
a given initial solution.
Has somebody an idea?
Thanks in advance, Jürgen
PS: Prof. Spellucci told me some days ago that the problem is in the
field of integer optimisation. But I think it is not even a linear problem.
I didn't say anything about linear ... there is also nonlinear integer
programming.
your grid "same numbers in each direction" : is this a complete
rectangular grid? then you could first project on the hypercube
which encloses the grid and use the solution as initial point for a
(in the L2-case) integer quadratic programming problem.
the L1-case can be translated into a linear program using additional
artificial variables and the solved by integer linear programming.
rounding the continuous solution to the grid is in general not the
optimal solution
hth
peter |
|
|
| Back to top |
|
| Michael Hennebry |
| Posted: Mon Mar 05, 2007 12:25 pm |
|
|
|
Guest
|
On Mar 1, 7:54 am, Jürgen Womser-Schütz <jws1...@gmx.e> wrote:
Quote: Given isR^K, anaffinesubspaceS ofR^Kwith dim(S)=K-2 and
a compact grid G inR^K.
The grid G is generated by N numbers (same numbers in each coordinate).
The problem is to find the point of the grid which is near to S
(L_2 norm or if not possible L_1 norm).
I'm not sure what a compact grid is.
I'm guessing that there exists a matrix M such that
for every x in G there exists an all-integer y
such that x = My.
One can select a matrix A and 2-vector b such that
for any x in S, Ax=b.
The answer is 0 iff AMy = b for some all-integer y.
If AM is rational, the question is easliy answered.
If the answer is not 0,
then a couple auxillary variables would be useful.
Select A and b so A is orthonormal.
w = Ax-b
Use |w|^2 as the objective for the L2 norm.
If you are willing to add many more constraints
in the interest of preserving linearity:
minimize
T T T
z >= (L Ax-L b)/|L A| for all real 2-vectors L
This implies
z>= |A[r,*]x - A[r,*]b|/|A[r,*]| for r in {1, 2}
For the L1 norm, I would solve
T
min 1 v
s.t.
x = My
Aw = b
v >= x-w
v >= w-x
y all integer
x, w, v real |
|
|
| Back to top |
|
| |
|
Page 1 of 1
All times are GMT - 5 Hours
The time now is Thu Aug 21, 2008 6:45 pm
|
|