Mixing
Modified assignment problems: Is there a name for this type?
Clash Royale CLAN TAG#URR8PPP
up vote
0
down vote
favorite
I observed particle motion within an experiment with two cameras. One was on the left, the other was on the right. I need to link identical trajectories viewed in the left camera to their counterpart in the right camera.
The left view obtains a set of $N_L$ trajectories $l_i_i=1^N_L$. The right view obtains a set of $N_R$ trajectories $r_i_i=1^N_R$. Probably $N_Lneq N_R$ due to measurement error.
Each pairing of trajectories $l_i$ and $r_j$ defines a cost $C_ij$. Since $N_Lneq N_R$, some trajectories will not pair up. Therefore a dummy row and dummy column must be appended to the cost matrix $[C_ij]$, and it has dimension $(N_L+1)times (N_R+1)$.
I need to find an assignment $x_ij$. I believe its constraints should be
$x_ij in 0,1$
$sum_i=1^N_Lx_ij = 1 $ if $jneq N_R+1$
$sum_j=1^N_Rx_ij = 1 $ if $ineq N_L+1$
$sum_i=1^N_Lx_ij leq N_L $ if $j = N_R+1$
$sum_j=1^N_Rx_ij leq N_R $ if $i = N_L+1$
The difference between this problem and a standard assignment problem is that more than one particle can be unlinked.
I'm certain this problem is well-studied, but I don't know much about this type of mathematics. Maybe someone could point me in the right direction for a solution? Any help or background would be appreciated. I will probably be implementing any solution in python, if that's relevant. Thanks!
linear-algebra linear-programming
asked Jul 21 at 6:49
kevinkayaks
1184
add a comment |Â
up vote
0
down vote
favorite
I observed particle motion within an experiment with two cameras. One was on the left, the other was on the right. I need to link identical trajectories viewed in the left camera to their counterpart in the right camera.
The left view obtains a set of $N_L$ trajectories $l_i_i=1^N_L$. The right view obtains a set of $N_R$ trajectories $r_i_i=1^N_R$. Probably $N_Lneq N_R$ due to measurement error.
Each pairing of trajectories $l_i$ and $r_j$ defines a cost $C_ij$. Since $N_Lneq N_R$, some trajectories will not pair up. Therefore a dummy row and dummy column must be appended to the cost matrix $[C_ij]$, and it has dimension $(N_L+1)times (N_R+1)$.
I need to find an assignment $x_ij$. I believe its constraints should be
$x_ij in 0,1$
$sum_i=1^N_Lx_ij = 1 $ if $jneq N_R+1$
$sum_j=1^N_Rx_ij = 1 $ if $ineq N_L+1$
$sum_i=1^N_Lx_ij leq N_L $ if $j = N_R+1$
$sum_j=1^N_Rx_ij leq N_R $ if $i = N_L+1$
The difference between this problem and a standard assignment problem is that more than one particle can be unlinked.
I'm certain this problem is well-studied, but I don't know much about this type of mathematics. Maybe someone could point me in the right direction for a solution? Any help or background would be appreciated. I will probably be implementing any solution in python, if that's relevant. Thanks!
linear-algebra linear-programming
asked Jul 21 at 6:49
kevinkayaks
1184
Assignment problems with $n ne m$ are sometimes called unbalanced. I believe you can remove your last two constraints as they are never binding.
– Erwin Kalvelagen
Jul 23 at 11:13
Would you think appending $N_L$ rows and $N_R$ dummy columns with all costs infinite in each except for one would do this?
– kevinkayaks
Jul 24 at 2:13
@ErwinKalvelagen also may I ask what you mean by 'binding'?
– kevinkayaks
Jul 24 at 2:42
Non-binding means if you remove a constraint, the solution does not change. Binding is the other way around: when removed, the solution will change.
– Erwin Kalvelagen
Jul 24 at 13:27
Are you sure the solution does not change? Without those additional constraints it would not be possible, under the given matrix structure, to leave more than one trajectory un-assigned. Do you mean there exists an alternate formulation which leaves the solution unchanged?
– kevinkayaks
Jul 24 at 19:02
add a comment |Â
up vote
0
down vote
favorite
up vote
0
down vote
favorite
I observed particle motion within an experiment with two cameras. One was on the left, the other was on the right. I need to link identical trajectories viewed in the left camera to their counterpart in the right camera.
The left view obtains a set of $N_L$ trajectories $l_i_i=1^N_L$. The right view obtains a set of $N_R$ trajectories $r_i_i=1^N_R$. Probably $N_Lneq N_R$ due to measurement error.
Each pairing of trajectories $l_i$ and $r_j$ defines a cost $C_ij$. Since $N_Lneq N_R$, some trajectories will not pair up. Therefore a dummy row and dummy column must be appended to the cost matrix $[C_ij]$, and it has dimension $(N_L+1)times (N_R+1)$.
I need to find an assignment $x_ij$. I believe its constraints should be
$x_ij in 0,1$
$sum_i=1^N_Lx_ij = 1 $ if $jneq N_R+1$
$sum_j=1^N_Rx_ij = 1 $ if $ineq N_L+1$
$sum_i=1^N_Lx_ij leq N_L $ if $j = N_R+1$
$sum_j=1^N_Rx_ij leq N_R $ if $i = N_L+1$
The difference between this problem and a standard assignment problem is that more than one particle can be unlinked.
I'm certain this problem is well-studied, but I don't know much about this type of mathematics. Maybe someone could point me in the right direction for a solution? Any help or background would be appreciated. I will probably be implementing any solution in python, if that's relevant. Thanks!
linear-algebra linear-programming
asked Jul 21 at 6:49
kevinkayaks
1184
I observed particle motion within an experiment with two cameras. One was on the left, the other was on the right. I need to link identical trajectories viewed in the left camera to their counterpart in the right camera.
The left view obtains a set of $N_L$ trajectories $l_i_i=1^N_L$. The right view obtains a set of $N_R$ trajectories $r_i_i=1^N_R$. Probably $N_Lneq N_R$ due to measurement error.
Each pairing of trajectories $l_i$ and $r_j$ defines a cost $C_ij$. Since $N_Lneq N_R$, some trajectories will not pair up. Therefore a dummy row and dummy column must be appended to the cost matrix $[C_ij]$, and it has dimension $(N_L+1)times (N_R+1)$.
I need to find an assignment $x_ij$. I believe its constraints should be
$x_ij in 0,1$
$sum_i=1^N_Lx_ij = 1 $ if $jneq N_R+1$
$sum_j=1^N_Rx_ij = 1 $ if $ineq N_L+1$
$sum_i=1^N_Lx_ij leq N_L $ if $j = N_R+1$
$sum_j=1^N_Rx_ij leq N_R $ if $i = N_L+1$
The difference between this problem and a standard assignment problem is that more than one particle can be unlinked.
I'm certain this problem is well-studied, but I don't know much about this type of mathematics. Maybe someone could point me in the right direction for a solution? Any help or background would be appreciated. I will probably be implementing any solution in python, if that's relevant. Thanks!
linear-algebra linear-programming
asked Jul 21 at 6:49
kevinkayaks
1184
asked Jul 21 at 6:49
kevinkayaks
1184
asked Jul 21 at 6:49
kevinkayaks
1184
asked Jul 21 at 6:49
kevinkayaks
1184
1184
Assignment problems with $n ne m$ are sometimes called unbalanced. I believe you can remove your last two constraints as they are never binding.
– Erwin Kalvelagen
Jul 23 at 11:13
Would you think appending $N_L$ rows and $N_R$ dummy columns with all costs infinite in each except for one would do this?
– kevinkayaks
Jul 24 at 2:13
@ErwinKalvelagen also may I ask what you mean by 'binding'?
– kevinkayaks
Jul 24 at 2:42
Non-binding means if you remove a constraint, the solution does not change. Binding is the other way around: when removed, the solution will change.
– Erwin Kalvelagen
Jul 24 at 13:27
Are you sure the solution does not change? Without those additional constraints it would not be possible, under the given matrix structure, to leave more than one trajectory un-assigned. Do you mean there exists an alternate formulation which leaves the solution unchanged?
– kevinkayaks
Jul 24 at 19:02
add a comment |Â
Assignment problems with $n ne m$ are sometimes called unbalanced. I believe you can remove your last two constraints as they are never binding.
– Erwin Kalvelagen
Jul 23 at 11:13
Would you think appending $N_L$ rows and $N_R$ dummy columns with all costs infinite in each except for one would do this?
– kevinkayaks
Jul 24 at 2:13
@ErwinKalvelagen also may I ask what you mean by 'binding'?
– kevinkayaks
Jul 24 at 2:42
Non-binding means if you remove a constraint, the solution does not change. Binding is the other way around: when removed, the solution will change.
– Erwin Kalvelagen
Jul 24 at 13:27
Are you sure the solution does not change? Without those additional constraints it would not be possible, under the given matrix structure, to leave more than one trajectory un-assigned. Do you mean there exists an alternate formulation which leaves the solution unchanged?
– kevinkayaks
Jul 24 at 19:02
Assignment problems with $n ne m$ are sometimes called unbalanced. I believe you can remove your last two constraints as they are never binding.
– Erwin Kalvelagen
Jul 23 at 11:13
Assignment problems with $n ne m$ are sometimes called unbalanced. I believe you can remove your last two constraints as they are never binding.
– Erwin Kalvelagen
Jul 23 at 11:13
Would you think appending $N_L$ rows and $N_R$ dummy columns with all costs infinite in each except for one would do this?
– kevinkayaks
Jul 24 at 2:13
Would you think appending $N_L$ rows and $N_R$ dummy columns with all costs infinite in each except for one would do this?
– kevinkayaks
Jul 24 at 2:13
@ErwinKalvelagen also may I ask what you mean by 'binding'?
– kevinkayaks
Jul 24 at 2:42
@ErwinKalvelagen also may I ask what you mean by 'binding'?
– kevinkayaks
Jul 24 at 2:42
Non-binding means if you remove a constraint, the solution does not change. Binding is the other way around: when removed, the solution will change.
– Erwin Kalvelagen
Jul 24 at 13:27
Non-binding means if you remove a constraint, the solution does not change. Binding is the other way around: when removed, the solution will change.
– Erwin Kalvelagen
Jul 24 at 13:27
Are you sure the solution does not change? Without those additional constraints it would not be possible, under the given matrix structure, to leave more than one trajectory un-assigned. Do you mean there exists an alternate formulation which leaves the solution unchanged?
– kevinkayaks
Jul 24 at 19:02
Are you sure the solution does not change? Without those additional constraints it would not be possible, under the given matrix structure, to leave more than one trajectory un-assigned. Do you mean there exists an alternate formulation which leaves the solution unchanged?
– kevinkayaks
Jul 24 at 19:02
add a comment |Â
active
oldest
votes
active
oldest
votes
active
oldest
votes
active
oldest
votes
active
oldest
votes
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2858291%2fmodified-assignment-problems-is-there-a-name-for-this-type%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Assignment problems with $n ne m$ are sometimes called unbalanced. I believe you can remove your last two constraints as they are never binding.
– Erwin Kalvelagen
Jul 23 at 11:13
Would you think appending $N_L$ rows and $N_R$ dummy columns with all costs infinite in each except for one would do this?
– kevinkayaks
Jul 24 at 2:13
@ErwinKalvelagen also may I ask what you mean by 'binding'?
– kevinkayaks
Jul 24 at 2:42
Non-binding means if you remove a constraint, the solution does not change. Binding is the other way around: when removed, the solution will change.
– Erwin Kalvelagen
Jul 24 at 13:27
Are you sure the solution does not change? Without those additional constraints it would not be possible, under the given matrix structure, to leave more than one trajectory un-assigned. Do you mean there exists an alternate formulation which leaves the solution unchanged?
– kevinkayaks
Jul 24 at 19:02