Got Questions? Get Answers.
Discover MakerZone

MATLAB and Simulink resources for Arduino, LEGO, and Raspberry Pi

Learn more

Discover what MATLAB® can do for your career.

Opportunities for recent engineering grads.

Apply Today

Thread Subject:
Optimizing a selection problem

Subject: Optimizing a selection problem

From: Jordan

Date: 9 Oct, 2010 06:06:04

Message: 1 of 6

Dear Matlab users,

I am new to optimization problems and hope that someone may be able to help me find a solution.

I have two groups of 100 people, all of whom have two features (age and education). I would like to match up each individual with a similar person from the other group.

It is simple enough to start by picking the best matches from the group, but of course you are punished for this with bad pairings once you get to the bottom of the pool with ill-fitting leftovers. Optimizing pairings across the entire group for the minimum overall difference in age and education is a difficult problem that I need Matlab to solve.

Can anyone point me towards an appropriate function or algorithm? The optimization toolbox seems to be geared towards continuous functions, whereas this is quite a different problem. Sampling the entire set of possibilities does not seem practical owing to large combinatorials.

Thanks in advance,
Jordan

Subject: Optimizing a selection problem

From: Roger Stafford

Date: 9 Oct, 2010 16:28:05

Message: 2 of 6

"Jordan " <j333poppenk@removethethrees.princeton.edu> wrote in message <i8p0oc$fbe$1@fred.mathworks.com>...
> Dear Matlab users,
>
> I am new to optimization problems and hope that someone may be able to help me find a solution.
>
> I have two groups of 100 people, all of whom have two features (age and education). I would like to match up each individual with a similar person from the other group.
>
> It is simple enough to start by picking the best matches from the group, but of course you are punished for this with bad pairings once you get to the bottom of the pool with ill-fitting leftovers. Optimizing pairings across the entire group for the minimum overall difference in age and education is a difficult problem that I need Matlab to solve.
>
> Can anyone point me towards an appropriate function or algorithm? The optimization toolbox seems to be geared towards continuous functions, whereas this is quite a different problem. Sampling the entire set of possibilities does not seem practical owing to large combinatorials.
>
> Thanks in advance,
> Jordan
- - - - - - - - - - -
  See Bruno's suggestion today about using Delaunay triangulation in the thread "find nearest,closest value" at:

 http://www.mathworks.com/matlabcentral/newsreader/view_thread/243878

Roger Stafford

Subject: Optimizing a selection problem

From: Roger Stafford

Date: 9 Oct, 2010 16:50:05

Message: 3 of 6

"Jordan " <j333poppenk@removethethrees.princeton.edu> wrote in message <i8p0oc$fbe$1@fred.mathworks.com>...
> ........
> It is simple enough to start by picking the best matches from the group, but of course you are punished for this with bad pairings once you get to the bottom of the pool with ill-fitting leftovers. Optimizing pairings across the entire group for the minimum overall difference in age and education is a difficult problem that I need Matlab to solve.
> .......

  I'm afraid I made that suggestion about delaunay triangulation without thinking the matter though carefully. There are aspects of your problem that do not have an obvious solution via triangulation. I'll have to think on your problem some more. Consider my suggestion withdrawn.

Roger Stafford

Subject: Optimizing a selection problem

From: Roger Stafford

Date: 9 Oct, 2010 17:57:03

Message: 4 of 6

"Jordan " <j333poppenk@removethethrees.princeton.edu> wrote in message <i8p0oc$fbe$1@fred.mathworks.com>...
> .......
> Can anyone point me towards an appropriate function or algorithm?
> .......

  One more incomplete thought. I think I see a correspondence between this problem and the famous (infamous) traveling salesman problem which is known to be NP-hard. If that is so, you have posed a computational very difficult problem. What exactly is your idea of a criterion for choosing between two different pairings among the sets - a least sum of squares of some sort?

Roger Stafford

Subject: Optimizing a selection problem

From: Bruno Luong

Date: 9 Oct, 2010 19:19:04

Message: 5 of 6

"Jordan " <j333poppenk@removethethrees.princeton.edu> wrote in message <i8p0oc$fbe$1@fred.mathworks.com>...
> Dear Matlab users,
>
> I am new to optimization problems and hope that someone may be able to help me find a solution.
>
> I have two groups of 100 people, all of whom have two features (age and education). I would like to match up each individual with a similar person from the other group.
>
> It is simple enough to start by picking the best matches from the group, but of course you are punished for this with bad pairings once you get to the bottom of the pool with ill-fitting leftovers. Optimizing pairings across the entire group for the minimum overall difference in age and education is a difficult problem that I need Matlab to solve.
>
> Can anyone point me towards an appropriate function or algorithm? The optimization toolbox seems to be geared towards continuous functions, whereas this is quite a different problem. Sampling the entire set of possibilities does not seem practical owing to large combinatorials.
>

Take a look at Munkres's algorithm (Hungarian). There are several on FEX.

Bruno

Subject: Optimizing a selection problem

From: Steven_Lord

Date: 10 Oct, 2010 05:37:54

Message: 6 of 6



"Jordan " <j333poppenk@removethethrees.princeton.edu> wrote in message
news:i8p0oc$fbe$1@fred.mathworks.com...
> Dear Matlab users,
>
> I am new to optimization problems and hope that someone may be able to
> help me find a solution.
>
> I have two groups of 100 people, all of whom have two features (age and
> education). I would like to match up each individual with a similar person
> from the other group.
>
> It is simple enough to start by picking the best matches from the group,
> but of course you are punished for this with bad pairings once you get to
> the bottom of the pool with ill-fitting leftovers. Optimizing pairings
> across the entire group for the minimum overall difference in age and
> education is a difficult problem that I need Matlab to solve.
>
> Can anyone point me towards an appropriate function or algorithm? The
> optimization toolbox seems to be geared towards continuous functions,
> whereas this is quite a different problem. Sampling the entire set of
> possibilities does not seem practical owing to large combinatorials.

This sounds to me like the assignment variety of the (mathematical) marriage
problem:

http://en.wikipedia.org/wiki/Marriage_problem

There are probably implementations of the Hungarian algorithm on the File
Exchange; if not it's not that difficult an algorithm to implement, if I
remember correctly.

--
Steve Lord
slord@mathworks.com
comp.soft-sys.matlab (CSSM) FAQ: http://matlabwiki.mathworks.com/MATLAB_FAQ
To contact Technical Support use the Contact Us link on
http://www.mathworks.com

Tags for this Thread

What are tags?

A tag is like a keyword or category label associated with each thread. Tags make it easier for you to find threads of interest.

Anyone can tag a thread. Tags are public and visible to everyone.

Contact us