0
$\begingroup$

Need help with the following exercise. I am unable to work out the objective function.

After months of closure due to Covid-19, a food court is preparing to re-open for business. However, safe management measures need to be implemented and one of these requires that there must be a distance of at least Dmin = $4$ between any two tables occupied by customers. The food court has a total of $12$ tables and they may not meet this requirement if all tables are occupied simultaneously. Furthermore, the tables are fixed and cannot be moved, and so there is a need to determine which of the $12$ tables can be selected for use so that the maximum number of tables are made available to customers at any time without violating the requirement, while the rest of the tables not selected will be marked with $X$s to indicate that they cannot be used. The location of each of the $12$ tables is known and specified by its respective $(X_i, Y_i)$ positional coordinates measured with respect to some reference point, for $i = 1, 2,\ldots,12$, as tabulated below. Which are the tables that should be selected for use? (It can be assumed that all distances and coordinates are expressed in consistent units.)

  • Table 1: $(X=3, Y=17)$

  • Table 2: $(X=4, Y=8)$

  • Table 3: $(X=5, Y=4)$

  • Table 4: $(X=5, Y=14)$

  • Table 5: $(X=7, Y=6)$

  • Table 6: $(X=8, Y=12)$

  • Table 7: $(X=13, Y=7)$

  • Table 8: $(X=14, Y=5)$

  • Table 9: $(X=16, Y=13)$

  • Table 10: $(X=17, Y=4)$

  • Table 11: $(X=17, Y=10)$

  • Table 12: $(X=18, Y=15)$

Improve this question
$\endgroup$
3
  • $\begingroup$ Welcome to OR.SE. I'm not sure I really understand your question, therefore, would you say please, what you mean by "the tables are fixed and cannot be moved"? Also, is the food court area predefined (if so, how much is it dimensions?) and do the tables have the same size? What about the dimensions of the tables? $\endgroup$
    – A.Omidi
    Oct 19, 2020 at 5:44
  • $\begingroup$ The tables are fixed and cannot be moved refers to their coordinates do not change. The area of the food court is not defined. To make the question easier, I assume that all the tables have the same size, however the dimensions is not make known to us. Therefore, I assume the Dmin refers to the center distance between 2 tables. $\endgroup$
    – Alibaba123
    Oct 19, 2020 at 17:47
  • $\begingroup$ Thanks for your explanation. As you mentioned "the tables are fixed", the problem is to find the number of combinations in which the two selected tables have been at least 4 unit of distance. A simple method would be, I assume that the tables are square. Please, see this link. By calculating the distance norm between the center of the tables and round up the results, in $5$ states you cannot select the tables. By removing the red states the rest of the combinations can be used. Is it useful? $\endgroup$
    – A.Omidi
    Oct 20, 2020 at 21:33

1 Answer 1

Reset to default
1
$\begingroup$

This is a maximum independent set problem on a graph with 12 nodes, which you can solve with one binary variable $z_i$ per node and one "conflict" constraint $z_i+z_j \le 1$ per edge. The objective is to maximize $\sum_i z_i$.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Thanks for the guide. I had did the constraint where 4 ≤ (x1-x2)^2 + (y1-y2)^2. However, I am not sure of how to form the equation for the objective function. $\endgroup$
    – Alibaba123
    Oct 19, 2020 at 4:28
  • $\begingroup$ You actually don't need the distances as variables, since the location does not change. So whether table $i$ is selected is given by $z_i\in\{0,1\}$. Then, you can precompute whether the tables $i$ and $j$ are too close to each other (i.e. $D_{i,j} < 4$). If this is the case, then you add the cut that Rob suggested, i.e. $z_i + z_j \leq 1$. $\endgroup$
    – Richard
    Oct 19, 2020 at 6:56
  • $\begingroup$ Sorry, I still don't quite get what you mean as I am quite new to excel solver. I did the constraint to know whether table is usable (e.g Table 2 and Table 5 does not fulfil the Dmin = 4, therefore only one table can be used) However, I do not know how to work out the equation such that the total number of table used is maximize. $\endgroup$
    – Alibaba123
    Oct 19, 2020 at 11:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.