Prepare for discussion in class at 10.00 of Wednesday,
February 24.
A company manufactures multiple products. The products are seasonal with demand varying weekly, monthly, or quarterly. To use its work force and capital equipment efficiently, the company wishes to “smooth” production, storing pre-season production to supplement peak-season production. The company has a warehouse with fixed capacity R that it uses to store all the products it produces. Its decision problem is to identify the production levels of all the products for every week, month, or quarter of the year that will permit it to satisfy the demands incurring the minimum possible production and storage costs.
We can view this warehousing problem as a multicommodity flow problem defined on an appropriate network. For simplicity, consider a situation in which the company makes two products and the company needs to schedule its production for each of the next four quarters of the year. Let dj1 and dj2 denote the demand for products 1 and 2 in quarter j. Suppose that the production capacity for the jth quarter is uj1 and uj2, and that the per unit cost of production for this quarter is cj1 and cj2. Let hj1 and hj2 denote the storage (holding) costs per unit of the two products from quatrter j to quarter j+1.
Model the warehousing problem by means of the multicommmodity flow model and represent graphically the network in the two products four periods case.
The schedule of games of real leagues in sports is affected by a large number of requirements, preferences, and idiosyncrasies. For instance, for the Major League Baseball in USA, the schedule must balance the number of weekend games each team plays in its home stadium, balance monthly home game counts, balance summer home game counts, limit number of consecutive games on the road, meet television requests, and handle many other constraints. There are even teams that do not want to play at home on the starting day of hunting season! Meeting all of these requirements is far beyond human capability, but is an ideal task for integer programming.
Let’s begin with an initial generalized round-robin problem. We have ten teams, named 1 through 10. In this schedule, teams play in pairs and we are not concerned with "home games" or "away games". Every team plays once per week.
Teams 1, 2, 3, 4 and 5 are in one division and teams 6, 7, 8, 9 and 10 are in another. We will begin with every team playing every other team once, but will then create schedules where teams play X games against opponents in their own division and Y games against those outside their division for (X,Y) = (2,1), (3,1), (3,2) and (4,1).
As an objective, the league would rather play divisional games later in the season. We can model this by assigning a value to divisional games depending on the week in which they occur. For Week 1 (the first week), we will have a value of 0, Week 2 has a value of 1, Week 3 has value 2, Week 4 has a value of 4, and so on, so Week k has value 2(k−2) for a divisional game in that week. What is the maximum value schedule possible?
Model this problem as an integer programming problem, write the model in COMET and solve it. You may use Table 1 to get inspiration and to check the solution for the case (1,1) and 6 teams. Once you obtained a solution check whether it satisfies all requirements. Does the resulting "optimal solution" match our intuition as to what an answer should look like? What is the most divisional games a week can have?
Include in the model the following extensions.
Find a (X,Y) which is hard to solve and modify the model in order to help finding a solution faster. In particular, consider the branch and bound algorithm and the linear relaxation that has to be solved. Try to strengthen your formulation by introducing “cuts”, that is additional constrains that satisfy two properties:
VARIABLES Team i 1 1 1 1 1 2 2 2 2 3 3 3 4 4 5 Team j 2 3 4 5 6 3 4 5 6 4 5 6 5 6 6 Week 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 4 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 5 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 CONSTRAINTS Correct Number of Games Played Count 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 Goal 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 One game per slot 1 2 3 4 5 6 1 0 0 0 0 0 0 2 0 0 0 0 0 0 3 0 0 0 0 0 0 4 0 0 0 0 0 0 5 0 0 0 0 0 0 OBJECTIVE Objective 0 Coefficients 1 0 0 0 0 0 0 2 1 1 1 1 1 1 3 2 2 2 2 2 2 4 4 4 4 4 4 4 5 8 8 8 8 8 8