Dtjytyk

How to write capital alpha?

Nose gear failure in single prop aircraft: belly landing or nose-gear up landing?

New Order #6: Easter Egg

How can I prevent/balance waiting and turtling as a response to cooldown mechanics

Tips to organize LaTeX presentations for a semester

What order were files/directories output in dir?

How to ask rejected full-time candidates to apply to teach individual courses?

What is the origin of 落第?

Why datecode is SO IMPORTANT to chip manufacturers?

Where is the Next Backup Size entry on iOS 12?

How to change the tick of the color bar legend to black

How can I save and copy a screenhot at the same time?

Why does electrolysis of aqueous concentrated sodium bromide produce bromine at the anode?

How can a team of shapeshifters communicate?

What is the chair depicted in Cesare Maccari's 1889 painting "Cicerone denuncia Catilina"?

Why is the change of basis formula counter-intuitive? [See details]

What initially awakened the Balrog?

Mounting TV on a weird wall that has some material between the drywall and stud

Monty Hall Problem-Probability Paradox

As a dual citizen, my US passport will expire one day after traveling to the US. Will this work?

Moving a wrapfig vertically to encroach partially on a subsection title

What is the "studentd" process?

What is the difference between a "ranged attack" and a "ranged weapon attack"?

NERDTreeMenu Remapping

Age matching optimization problem.

1

$begingroup$

A common problem in clinical studies is how to choose age-, and usually also gender-, matched pairs from two groups such as case/control. (case=has disease, control=not have).

After searching the web a bit, it seems like many researchers do it sort of by hand. To me it seems like this might fall into some standard class of optimization problems. I also haven't found an algorithm that tackles it from that point of view. The objective function could be something like the root-mean-square age difference.

Suppose I have $N$ subjects in the case group and $M$ subjects in the control group, with $N>M$. (In my case, $N=85, M=49$). Without doing any kind of sorting or pre-selection, i.e. being completely naive, there are an enormous number of potential pairings. Here is my count (I hope I'm doing this right):

Take the $M$ controls and put them in an arbitrary order. The first of these can be associated with a random one of $N$ in the case group. The next, with $N-1$, and so on down the line. So the total number of pairings is:

$$N(N-1)(N-2)cdots(N-M+1) = frac{N!}{(N-M)!}$$

That's a huge number. But maybe smart math people have figured out a clever solution to this problem.

Is this the best forum for this question?

optimization nonlinear-optimization

share|cite|improve this question

asked Mar 26 at 0:00

abalterabalter

29519

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  You calculation is good. To me it seems like you answered your own question and also explained the methodology, so, I’m not sure if there is anything left to answer. Nevertheless you have an intro paragraph where you hint at some other question, besides the one on computing the number of ways to match. If there is something else you wanted it may be good to specify that.
  $endgroup$
  – Michael
  Mar 26 at 0:32
  
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  You can find a random match equally likely over all options in polynomial time using the method you specified. If you have weights for each match you cold consider “max weight match” algorithms.
  $endgroup$
  – Michael
  Mar 26 at 0:40
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  I think you overestimate my knowledge of optimization. I happen to know the meaning of an objective function and have done Metropolis-Hastings optimization in the context of a physical system. That's about it :-/
  $endgroup$
  – abalter
  Mar 26 at 15:13
  

  
  
  
  

add a comment | 

1

$begingroup$

A common problem in clinical studies is how to choose age-, and usually also gender-, matched pairs from two groups such as case/control. (case=has disease, control=not have).

After searching the web a bit, it seems like many researchers do it sort of by hand. To me it seems like this might fall into some standard class of optimization problems. I also haven't found an algorithm that tackles it from that point of view. The objective function could be something like the root-mean-square age difference.

Suppose I have $N$ subjects in the case group and $M$ subjects in the control group, with $N>M$. (In my case, $N=85, M=49$). Without doing any kind of sorting or pre-selection, i.e. being completely naive, there are an enormous number of potential pairings. Here is my count (I hope I'm doing this right):

Take the $M$ controls and put them in an arbitrary order. The first of these can be associated with a random one of $N$ in the case group. The next, with $N-1$, and so on down the line. So the total number of pairings is:

$$N(N-1)(N-2)cdots(N-M+1) = frac{N!}{(N-M)!}$$

That's a huge number. But maybe smart math people have figured out a clever solution to this problem.

Is this the best forum for this question?

optimization nonlinear-optimization

share|cite|improve this question

asked Mar 26 at 0:00

abalterabalter

29519

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  You calculation is good. To me it seems like you answered your own question and also explained the methodology, so, I’m not sure if there is anything left to answer. Nevertheless you have an intro paragraph where you hint at some other question, besides the one on computing the number of ways to match. If there is something else you wanted it may be good to specify that.
  $endgroup$
  – Michael
  Mar 26 at 0:32
  
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  You can find a random match equally likely over all options in polynomial time using the method you specified. If you have weights for each match you cold consider “max weight match” algorithms.
  $endgroup$
  – Michael
  Mar 26 at 0:40
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  I think you overestimate my knowledge of optimization. I happen to know the meaning of an objective function and have done Metropolis-Hastings optimization in the context of a physical system. That's about it :-/
  $endgroup$
  – abalter
  Mar 26 at 15:13
  

  
  
  
  

add a comment | 

$begingroup$

A common problem in clinical studies is how to choose age-, and usually also gender-, matched pairs from two groups such as case/control. (case=has disease, control=not have).

After searching the web a bit, it seems like many researchers do it sort of by hand. To me it seems like this might fall into some standard class of optimization problems. I also haven't found an algorithm that tackles it from that point of view. The objective function could be something like the root-mean-square age difference.

Suppose I have $N$ subjects in the case group and $M$ subjects in the control group, with $N>M$. (In my case, $N=85, M=49$). Without doing any kind of sorting or pre-selection, i.e. being completely naive, there are an enormous number of potential pairings. Here is my count (I hope I'm doing this right):

Take the $M$ controls and put them in an arbitrary order. The first of these can be associated with a random one of $N$ in the case group. The next, with $N-1$, and so on down the line. So the total number of pairings is:

$$N(N-1)(N-2)cdots(N-M+1) = frac{N!}{(N-M)!}$$

That's a huge number. But maybe smart math people have figured out a clever solution to this problem.

Is this the best forum for this question?

optimization nonlinear-optimization

share|cite|improve this question

asked Mar 26 at 0:00

abalterabalter

29519

$endgroup$

share|cite|improve this question

asked Mar 26 at 0:00

abalterabalter

29519

share|cite|improve this question

asked Mar 26 at 0:00

abalterabalter

29519

asked Mar 26 at 0:00

abalterabalter

29519

asked Mar 26 at 0:00

abalterabalter

29519

1 Answer
1

active

oldest

votes

2

$begingroup$

Here is an example way to fill in a specific model:

You have $m$ controls and $n$ subjects with $m leq n$. You have ages $a_1,...,a_m$ and $b_1,...,b_n$. Define

$$w_{ij}=(a_i-b_j)^2$$

You want to find a binary matching matrix $x=(x_{ij})$ that solves the “min weight match” problem of minimizing
$$ sum_{i =1}^msum_{j=1}^n x_{ij}w_{ij}$$
subject to $(x_{ij})$ being a valid matching. This is polynomially solvable and is equivalent to “max weight matching” under a simple transformation of weights.

---

I should mention the problem with general weights $w_{ij}$ is polynomial solvable via certain methods, but in fact the quadratic weight problem may be even easier...

share|cite|improve this answer

edited Mar 26 at 1:07

answered Mar 26 at 1:01

MichaelMichael

13.5k11429

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  But there are roughly $gamma(90)/gamma(37) approx 4.4mathrm{E}94$ possible matrices $x_{ij}$! What sort of optimization procedure would I use?
  $endgroup$
  – abalter
  Mar 26 at 15:17
  
  
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  To put the numbers ${a_1, a_2, ..., a_{200}}$ in order, there are $200!$ permutations to consider. This is more than the estimated number of atoms in the universe. Nevertheless, it can be done in polynomial time using basic algorithms. Similarly, there are basic algorithms for solving max-weight match problems. They are not trivial algorithms, but you could download a program to do it by googling "max weight match" or "min weight match."
  $endgroup$
  – Michael
  Mar 26 at 15:23
  
  
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  Fantastic! I already found a Python package for it NetworkX. I couldn't have found it if you had not given me the formal statement of the problem.
  $endgroup$
  – abalter
  Mar 26 at 15:58
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  My above factorial approximation should have $Gamma$ not $gamma$.
  $endgroup$
  – abalter
  Mar 26 at 16:12
  
  
  

  
  
  
  

add a comment | 

Your Answer

StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);

StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});

function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});


}
});

draft saved

draft discarded

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

Name

Email

Required, but never shown

StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3162498%2fage-matching-optimization-problem%23new-answer', 'question_page');
}
);

Post as a guest

Name

Email

Required, but never shown

2

$begingroup$

Here is an example way to fill in a specific model:

You have $m$ controls and $n$ subjects with $m leq n$. You have ages $a_1,...,a_m$ and $b_1,...,b_n$. Define

$$w_{ij}=(a_i-b_j)^2$$

You want to find a binary matching matrix $x=(x_{ij})$ that solves the “min weight match” problem of minimizing
$$ sum_{i =1}^msum_{j=1}^n x_{ij}w_{ij}$$
subject to $(x_{ij})$ being a valid matching. This is polynomially solvable and is equivalent to “max weight matching” under a simple transformation of weights.

---

I should mention the problem with general weights $w_{ij}$ is polynomial solvable via certain methods, but in fact the quadratic weight problem may be even easier...

share|cite|improve this answer

edited Mar 26 at 1:07

answered Mar 26 at 1:01

MichaelMichael

13.5k11429

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  But there are roughly $gamma(90)/gamma(37) approx 4.4mathrm{E}94$ possible matrices $x_{ij}$! What sort of optimization procedure would I use?
  $endgroup$
  – abalter
  Mar 26 at 15:17
  
  
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  To put the numbers ${a_1, a_2, ..., a_{200}}$ in order, there are $200!$ permutations to consider. This is more than the estimated number of atoms in the universe. Nevertheless, it can be done in polynomial time using basic algorithms. Similarly, there are basic algorithms for solving max-weight match problems. They are not trivial algorithms, but you could download a program to do it by googling "max weight match" or "min weight match."
  $endgroup$
  – Michael
  Mar 26 at 15:23
  
  
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  Fantastic! I already found a Python package for it NetworkX. I couldn't have found it if you had not given me the formal statement of the problem.
  $endgroup$
  – abalter
  Mar 26 at 15:58
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  My above factorial approximation should have $Gamma$ not $gamma$.
  $endgroup$
  – abalter
  Mar 26 at 16:12
  
  
  

  
  
  
  

add a comment | 

2

$begingroup$

Here is an example way to fill in a specific model:

You have $m$ controls and $n$ subjects with $m leq n$. You have ages $a_1,...,a_m$ and $b_1,...,b_n$. Define

$$w_{ij}=(a_i-b_j)^2$$

You want to find a binary matching matrix $x=(x_{ij})$ that solves the “min weight match” problem of minimizing
$$ sum_{i =1}^msum_{j=1}^n x_{ij}w_{ij}$$
subject to $(x_{ij})$ being a valid matching. This is polynomially solvable and is equivalent to “max weight matching” under a simple transformation of weights.

---

I should mention the problem with general weights $w_{ij}$ is polynomial solvable via certain methods, but in fact the quadratic weight problem may be even easier...

share|cite|improve this answer

edited Mar 26 at 1:07

answered Mar 26 at 1:01

MichaelMichael

13.5k11429

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  But there are roughly $gamma(90)/gamma(37) approx 4.4mathrm{E}94$ possible matrices $x_{ij}$! What sort of optimization procedure would I use?
  $endgroup$
  – abalter
  Mar 26 at 15:17
  
  
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  To put the numbers ${a_1, a_2, ..., a_{200}}$ in order, there are $200!$ permutations to consider. This is more than the estimated number of atoms in the universe. Nevertheless, it can be done in polynomial time using basic algorithms. Similarly, there are basic algorithms for solving max-weight match problems. They are not trivial algorithms, but you could download a program to do it by googling "max weight match" or "min weight match."
  $endgroup$
  – Michael
  Mar 26 at 15:23
  
  
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  Fantastic! I already found a Python package for it NetworkX. I couldn't have found it if you had not given me the formal statement of the problem.
  $endgroup$
  – abalter
  Mar 26 at 15:58
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  My above factorial approximation should have $Gamma$ not $gamma$.
  $endgroup$
  – abalter
  Mar 26 at 16:12
  
  
  

  
  
  
  

add a comment | 

$begingroup$

Here is an example way to fill in a specific model:

You have $m$ controls and $n$ subjects with $m leq n$. You have ages $a_1,...,a_m$ and $b_1,...,b_n$. Define

$$w_{ij}=(a_i-b_j)^2$$

You want to find a binary matching matrix $x=(x_{ij})$ that solves the “min weight match” problem of minimizing
$$ sum_{i =1}^msum_{j=1}^n x_{ij}w_{ij}$$
subject to $(x_{ij})$ being a valid matching. This is polynomially solvable and is equivalent to “max weight matching” under a simple transformation of weights.

---

I should mention the problem with general weights $w_{ij}$ is polynomial solvable via certain methods, but in fact the quadratic weight problem may be even easier...

share|cite|improve this answer

edited Mar 26 at 1:07

answered Mar 26 at 1:01

MichaelMichael

13.5k11429

$endgroup$

share|cite|improve this answer

edited Mar 26 at 1:07

answered Mar 26 at 1:01

MichaelMichael

13.5k11429

answered Mar 26 at 1:01

MichaelMichael

13.5k11429

answered Mar 26 at 1:01

MichaelMichael

13.5k11429