In the process of manufacturing electronic circuit boards, holes have to be drilled in prints of rectangular shape; these holes have to be pairwise connected by conductive material. The head of the drilling equipment can only be moved horizontally and vertically from one hole to another (moves according to the shortest Manhattan distance between two holes). Usually, a large amount of holes has to be drilled in a board. Since moving the head of drill is a time consuming operation, the total distance that the head has to be moved should be minimized. Moreover, after the drilling process is completed, the head must return to its starting position. Suppose that there are some blocks on the circuit board, such that some paths between points may be closed due to the position of these blocks.

You are given the Cartesian coordinates of 10 points that must be drilled and 5 rectangular blocks and drilling machine is not allowed to pass through these blocks. For instance, in the figure below; The drill cannot move from A to C via the path marked with X. The drill can move from A to D. The drill can move from A to B etc.

Formulate the mathematical model for this problem. Clearly define the objective function, constraints, and parameters.

Points:

41	9
46	40
7	16
46	27
32	9
5	31
28	33
48	35
49	38
8	23
-	-

Rectangles:

38	10	2	3
9	6	2	3
11	14	3	3
8	15	2	2
11	20	2	3

Where first two rows indicate X and Y coordinates of the lower-left corner of the rectangle, while the 3rd and 4th rows are width and height respectively.

X A C X D B