0

I am new to optimization. How do I solve the below problem? Is it similar to the 0-1 knapsack problem?

There will be a meeting at New York and San Francisco offices. We will have to fly the participants to either one of these two offices. Let's say each office can accommodate half of the participants. Our goal is to assign each participant to an office in a way that the total travel cost for the company is minimized. What is this minimal cost? 

   SF NY 
A 500 700 
B 200 600 
C 400 500 
D 600 200

Output : 1400 (A:500 + B:200 + C:500 +D: 200)

callculus42
  • 30,550
mathopt
  • 121

1 Answers1

0

One approach is to calculate firstly the differences (absolute value) of the travel cost San Francisco and New York for each participant.

$A:200, B:400, C:100, D:400$

Now you look after the participant where you can save at most by choosing the destination with the lower travel cost. Here it is $B$ or $D$.

$B$ travels to San Francisco: Saving $400$, Cost: $\color{blue}{200}$

$D$ travels to New York: Saving $400$, Cost: $\color{blue}{200}$

It can be saved $200$ if we choose the lowest cost for $A$. This is more than in the case of $C$.

$A$ travels to San Francisco: Saving $200$, Cost: $\color{blue}{500}$

And finally $C$ has to travel to New York: Saving: $100$, Cost: $\color{blue}{500}$

callculus42
  • 30,550