1
00:00:00,060 --> 00:00:07,710
So this problem refers to circle placement in a rectangle, so, um, as you can see in this example,

2
00:00:07,740 --> 00:00:13,620
we do have some information regarding the, uh, a number of circles.

3
00:00:14,070 --> 00:00:16,560
Let's assume that we do have any circles.

4
00:00:16,980 --> 00:00:24,090
And what we know about the problem is that, um, the radius of each circle is known as you can see,

5
00:00:24,090 --> 00:00:25,860
we can represent him by our eye.

6
00:00:26,370 --> 00:00:34,740
But the question is, how can we place them on a plain surface, on a rectangle shape surface without

7
00:00:34,740 --> 00:00:36,030
overlapping each other?

8
00:00:36,120 --> 00:00:40,720
And the surface of that, a specific rectangle is a minimal value.

9
00:00:41,280 --> 00:00:48,450
So in order to formulate that, we have to create some constraints on an object to function.

10
00:00:48,450 --> 00:00:54,900
The object of function is multiplication of L multiplied by W, which is lines and width of that rectangle.

11
00:00:55,290 --> 00:01:01,650
And for each pair of circles, we do need some constraints.

12
00:01:01,920 --> 00:01:09,630
For example, the distance between the center of these two circles should be bigger than our eye.

13
00:01:09,630 --> 00:01:19,530
Plus R.G. Square in order to avoid overlapping and also for X for each X and Y, which are representing

14
00:01:19,530 --> 00:01:25,240
the center of each circle, we should have the following two, um, constraints.

15
00:01:25,310 --> 00:01:30,780
OK, so these are actually each constraint is too constrained actually.

16
00:01:30,780 --> 00:01:41,520
So our eye is between our um X is bigger than our eye and is lower than W minus our eye and Y is bigger

17
00:01:41,520 --> 00:01:49,890
than our eye, less than L minus our Y because we don't want the circle to get out of this rectangle.

18
00:01:50,340 --> 00:01:59,730
OK, so in order to show you what's going on, first of all, we have to know the input data for this

19
00:01:59,730 --> 00:02:00,350
problem.

20
00:02:00,540 --> 00:02:12,090
It means that for every eye and a J for every eye, we have to know the radius of each circle.

21
00:02:12,690 --> 00:02:15,600
So in this way, we can, um.

22
00:02:17,220 --> 00:02:18,040
Work on it.

23
00:02:18,110 --> 00:02:27,960
OK, so, uh, let me show you the, um, so as you can see here, we do have six circles and, um,

24
00:02:27,960 --> 00:02:32,390
for solving the problem, we have to find the optimal locations of them.

25
00:02:33,030 --> 00:02:34,230
So, um.

26
00:02:35,180 --> 00:02:43,850
Here you can see the Python code required for solving that problem and as usual, we have to import

27
00:02:43,850 --> 00:02:45,170
the required packages.

28
00:02:45,170 --> 00:02:47,980
For example, Palomo matplotlib non-pay.

29
00:02:48,410 --> 00:02:50,180
We don't need a random package.

30
00:02:50,180 --> 00:02:59,480
So I removed a and also and we have to create an abstract model so we can then easily change the number

31
00:02:59,480 --> 00:03:01,110
of circles that if you want.

32
00:03:01,460 --> 00:03:12,080
So Model I and is a set model that J is another set which is an alias with the previous set or is a

33
00:03:12,080 --> 00:03:20,420
parameter um which is defined overset AI and also um we do need some constraints.

34
00:03:20,420 --> 00:03:22,730
OK, and some decision variables.

35
00:03:22,970 --> 00:03:34,730
The decision variables are dissenters, um coordinations X and Y which are um bounded with um or AI

36
00:03:34,730 --> 00:03:45,140
and uh a big number because as you saw in the formulation and each X is between for example L minus

37
00:03:45,140 --> 00:03:47,990
our AI, but we don't know the value of L.

38
00:03:48,320 --> 00:03:51,980
So for simplicity, I have chosen a big number here.

39
00:03:52,910 --> 00:04:01,560
The same philosophy holds for Y and also for W and L, so W and L are positive numbers between zero

40
00:04:01,570 --> 00:04:02,080
and hundred.

41
00:04:02,090 --> 00:04:06,920
For example, I have initialize all of them and also um.

42
00:04:08,570 --> 00:04:16,940
For every eye, not equal to J, we have some constraints, for example, here you can see that X and

43
00:04:16,970 --> 00:04:23,990
model that X, I want it minus Model X, J Square plus model Y.

44
00:04:24,140 --> 00:04:30,410
That's why I minus model Y, j square should be bigger than an expression like this.

45
00:04:30,410 --> 00:04:32,800
Are I plus Arjay Square.

46
00:04:33,230 --> 00:04:38,450
But you might ask me why didn't you say I am not equal to J use.

47
00:04:38,450 --> 00:04:40,460
And you said I greater than J.

48
00:04:40,910 --> 00:04:50,690
This is because if we calculate the distance between two circles and let's say one and two, then we

49
00:04:50,690 --> 00:04:53,620
don't need to calculate the distance between two and one.

50
00:04:53,720 --> 00:04:55,850
We just need to calculate it once.

51
00:04:56,660 --> 00:05:02,860
Then for the rest of them we should just keep the constraint and model that equation.

52
00:05:02,870 --> 00:05:05,250
One is following that specific rule.

53
00:05:05,280 --> 00:05:13,010
OK, so rule two is telling us X should be less than W minus R.

54
00:05:14,630 --> 00:05:19,220
Um, this is another constraint and the other constraint is for wise.

55
00:05:19,580 --> 00:05:25,840
So that's why I is less than equal to a model L minus R I um.

56
00:05:26,090 --> 00:05:32,570
And the objective function is the multiplication of model Dunstable units multiplied by model dot l

57
00:05:33,020 --> 00:05:36,590
and the objective function should be defined here.

58
00:05:37,040 --> 00:05:46,760
Models on object um is equal to objective rule is objective rule here in the sense is the minimization

59
00:05:47,030 --> 00:05:54,620
the solver chosen for solving this problem should be capable of solving non-linear programming.

60
00:05:55,640 --> 00:06:04,790
Then um the instance will be created using the DAT file associated with this example and then we will

61
00:06:04,790 --> 00:06:07,340
ask Palomo to solve it for us.

62
00:06:07,460 --> 00:06:11,270
OK, so let me run each time one by one.

63
00:06:11,880 --> 00:06:16,310
OK, and this one, number three.

64
00:06:16,970 --> 00:06:18,530
And the final one.

65
00:06:18,560 --> 00:06:27,350
OK, so as you can see here, the optimal locations of a circle is a specified and plotted.

66
00:06:27,620 --> 00:06:32,630
So let me give you a very quick introduction how I have plotted this graph.

67
00:06:32,780 --> 00:06:37,970
So first of all, we have created a fake is equal to plots.

68
00:06:38,360 --> 00:06:41,330
Um, that figure perfect size.

69
00:06:41,330 --> 00:06:44,380
So you specify the size of your figure here.

70
00:06:45,200 --> 00:06:54,230
And um, teta is a linear space between zero and two pi, which is divided into a hundred points.

71
00:06:55,580 --> 00:07:02,570
And also um I have used the scatter command for putting those dots.

72
00:07:03,710 --> 00:07:13,910
So for each value of X and Y as we have a for loop here, we put a dots here on the surface and the

73
00:07:13,910 --> 00:07:18,410
X center values are also, um, calculated.

74
00:07:19,800 --> 00:07:29,700
At the center of each plot is here, scatter is planned, plotting the circle and the X, C and by C,

75
00:07:29,700 --> 00:07:34,380
which is representing center values, are created here.

76
00:07:35,100 --> 00:07:38,310
And then, um, you can see the graph here.

77
00:07:38,340 --> 00:07:42,230
So the solution is graphically shown on these plots.

78
00:07:42,390 --> 00:07:46,890
I can also specify the labels for x axis and y axis.

79
00:07:47,980 --> 00:07:48,850
Thank you very much.