Draw Graph II (exer-graph1)
Define the directed graph in Figure 1 and draw it with the drawing tool of LPL.
In this blog, I will add a new post all 3-5 days. Each post contains a complete (optimization) problem, many of them are puzzles. Each problem consists of a comprehensive description of the problem, a description of the modeling (translation from spoken language to mathematical language), a mathematical formulation, an implementation in the LPL modeling language, and a link to solve the problem directly through the Internet. A full document is also downloadable as a PDF.
I start with easy puzzle problems, but later on, more complicated problems will be presented. Enjoy!
Define the directed graph in Figure 1 and draw it with the drawing tool of LPL.
Define the undirected graph in Figure 1 and draw it with the drawing tool of LPL.
Generate the following output using Write() and Format(), putting random digits into the cells as follows (it is used to print a time-table:
Generate the following output using Write() and Format(), putting random digits into the cells as follows:
Given are
This problem was originally stated by Peter Hubbard (Southampton University), organizer of the yacht rally of 42 boats and their crews. A important evening event in the yacht rally is to organize a party where each crew socializes with as many other crews as possible. Some of the boats are selected to serve as “host boats” where the party takes place, the other boats are the “guest boats”. The crews of the host boats stay on their boats for the whole party, while the crews of the guest boats visits the host boats. In order to socialize as much as possible, the guest crews only stay for 30 minutes at one host, then they visit another host boat. The whole party lasts 3 hours.
In a local golf club, there are 16 social golfers, each of whom plays golf once a week, and always in groups of 4. Find a schedule of 5 weeks, such that no golfer plays in the same group as any other golfer on more than one occasion, if it exists. If it does not exist, then find a schedule of “maximal socialisation”, that is, as few repeated pairs as possible. (Found at: http://www.csplib.org/Problems/prob010/).
There seems to be no efficient method to solve these two problems. So, before solving them, let’s pose another problem that is linked to them: The problem is to find the smallest number n (the largest unit fraction ) in Egyptian fraction expansion for the number 1, that is, find a and n, with n as small as possible with a ≤ n, such that:
Find the maximum diameter of n equal mutually disjoint circles – that means, they must not overlap each other – inside a larger unit circle with radius r = 1.
Find the maximum diameter of n mutually disjoint circles of equal size – that means, they must not overlap each other – inside a unit square. (“Inside a unit square” means that all circles must be completely inside the unit square (see [1]).