COMP3910 – Combinatorial Optimisation - Coursework 2: Modelling Strong Formulations
COMP3910 – Combinatorial Optimisation Coursework 2: Modelling; Strong Formulations; Deadline:
Award:
This piece of summative coursework is worth 10% of your grade
Submission:
1) Write or type your answers inside the boxes of the current document. 2) Scan pages 1-4 using the MyPrint portal, including p. 1 (see instructions at Note that photos made by mobiles will not be marked. You should use university printers/scanners. 3) Upload one pdf-file containing pages 1-4 to Gradescope (see instructions at https://help.gradescope.com/article/ccbpppziu9-student-submitwork#submitting_a_pdf)
Question 1. [12 marks] A furniture company needs to make a decision about the mix of products to be manufactured next week. It has seven types of desks, each with a profit (£) per unit and a production time (man-hours) per unit as shown below:
| Desk 1 | Desk 2 | Desk 3 | Desk 4 | Desk 5 | Desk 6 | Desk 7|-----|-----|-----|-----|-----|-----|-----|-----| Profit (£ per unit) | 10 | 22 | 35 | 19 | 55 | 10 | 115 Production time (man-hours per unit) | 1.5 | 2.0 | 3.7 | 2.4 | 4.5 | 0.7 | 9.5
The company has 720 man-hours available in the coming week.
The following restrictions are also placed on the production. R1: If any amount of Desk 7 is to be produced, then an additional fixed cost of £2000 is incurred. R2: If any amount of Desk 6 is to be produced, then 80 man-hours are needed for production line set-up and hence the (effective) number of man-hours available falls to 720-80=640. R3: If any amount of Desk 1 is to be produced, then Desks 2 and 3 cannot be produced. R4: If Desk 4 is to be produced, then at least 10 desks of that type should be produced.
Formulate an ILP to determine the quantities of desks to be produced in order to maximise the profit. Use the following variables: • ?? (?? ≥ 0 and integer) for the number desks of type ? to be produced (? = 1,2, … ,7), • ?? (?? ∈ {0,1}) to indicate whether desk ? is to be produced (?? = 1) or not (?? = 0).
Present an ILP, without explaining how it is derived. If the model uses some numbers which are calculated based on the problem input, then present the formulae (no need to explain). As a sample answer, consider the final model for Problem 2 from Worksheet 5-6 (p. 9 of the solutions file). Do not include unnecessary constraints and unnecessary variables.
Question 2 [5 marks] Consider the Production Planning problem (Example 7) from Chapter 6, and the corresponding MILP: max ? = 5?1 +7?2 +3?3 s. t. 3?1 +4x2 +2?3 −36? ≤ 30, 4?1 +6?2 +2?3 +36? ≤ 76, ?1 ≤ 7, ?2 ≤ 5, ?3 ≤ 9, ?1 −9?1 ≤ 0, ?2 −9?2 ≤ 0, ?3 −9?3 ≤ 0, ?1 +?2 +?3 ≤ 2,
?1 , ?2 , ?3 ≥ 0, ?, ?1 , ?2 , ?3 ∈ {0,1}.
The disjunctive constraints
3?1 + 4?2 + 2?3 ≤ 30 or 4?1 + 6?2 + 2?3 ≤ 40
are modelled as
3?1 + 4?2 + 2?3 ≤ 30 + ?′ ?, (1) 4?1 + 6?2 + 2?3 ≤ 40 + ? (1 − ?). (2)
One possible choice is ? = 36 (see Chapter 6). In fact a smaller value of ?′ can be selected. Find such a value. Provide a justification.
Question 3 [23 marks] Consider an instance of the scheduling problem given by the table:
| Job ? | 1 2 3 4 5 |
|---|---|
| Release time ?? | 0 2 14 27 40 |
| Processing time ?? | 6 18 10 17 16 |
| Due date ?? | 27 22 23 61 59 |
Find an optimal solution by the branch-and-bound algorithm. Present the search tree. Use the depth-first strategy, selecting each time the most promising node among all child nodes of the same parent node. Number the nodes of the tree in the order they are obtained. State the optimal solution and the optimal objective value. The full description of the problem is given on pages 5-6, together with the details of the B&B algorithm. Present the search tree. Number the nodes of the tree in the order they are obtained. Mark the nodes by corresponding partial schedules. For example, the node marked by (*,,,,) is the root of the tree; the node marked by (1,∗,∗,∗,∗) is one of the child nodes. For each node either specify its LB or explain why the node is discarded without calculating its LB. State the initial UB and indicate how it is updated. Mark the node corresponding to the optimal schedule. Output a job permutation which defines an optimal schedule and the optimal objective value.
Problem description and instructions for Question 3.
A small garage specialises in car painting. The garage has sufficient room to keep multiple cars, but only one car can be painted at a time. For a job j, which corresponds to painting car j, three parameters are given:
- release time rj (the time when car j is delivered to the garage for painting);
- processing time pj (the time it takes to paint car j);
- due date dj (the time by which it is desirable to complete job j). The jobs can be completed in any order. A manager needs to decide in which order the jobs should be performed. Since it might not be possible to observe due dates for all jobs, the manager aims to provide a fair service to the customers, so that the maximum lateness is as small as possible. Consider an instance with 5 jobs and the data given in the table below.
| Job ? | 1 2 3 4 5 |
|---|---|
| Release time ?? | 0 2 14 27 40 |
| Processing time ?? | 6 18 10 17 16 |
| Due date ?? | 27 22 23 61 59 |
A schedule is defined by a job sequence. The starting time ?? of job ? should satisfy the release time constraint ?? ≥ ?? . If job ? starts at time ?? , then its completion time is ?? = ?? + ?? and its lateness is ?? = ?? − ?? . (1)
Notice that if job ? is completed before its due date, then ?? is negative.
For example, if the jobs are processed in the order (1,3,2,4,5), then the Gantt chart of the schedule is shown in Fig. 1. Notice that there is an idle interval caused by the release time ?3 = 14 of job 3.
Fig. 1: The Gantt chart of the schedule given by job sequence (1,3,2,4,5) The maximum lateness ?max for the above schedule is calculated as ?max = max{?1 , ?2 , ?3 , ?4 , ?_5} = max{─21, 20, 1, ─2, 16} = 20.
In a schedule with a different job order, the values of Lj will be different, and therefore the value of the maximum lateness Lmax might also be different.
Branching
The root of the search tree corresponds to an empty job sequenced (∗,∗,∗,∗,∗). Here ∗ in the job sequence indicates that no job has yet been assigned to the corresponding position in the sequence. We start by generating all child-nodes for (∗,∗,∗,∗,∗). They correspond to allocating one job to the first position. Thus for the 5-job instance, there are 5 nodes in level 1: (1,∗,∗,∗,∗), (2,∗,∗,∗,∗), (3,∗,∗,∗,∗), (4,∗,∗,∗,∗), (5,∗,∗,∗,∗). With the depth-first strategy, we compute LBs for all partial solutions in level 1, select the one with the smallest LB and branch from there. (It might be possible to eliminate some nodes straightaway without computing LBs; add a brief justification if you decide to do so.)
If a node (?1 ,,,,) is selected in level 1, then we create 4 child-nodes, which correspond to allocating one of the remaining 4 jobs to position 2, compute LBs for all partial solutions in level 2, select the one with the smallest LB (or eliminate some nodes straightaway) and branch from there. The process continues until in the last level, 4 jobs are allocated, as the allocation of the 5th job is obvious. The solutions at that level are of the form (?1 , ?2 , ?3 , ?4 ,∗).
An outline of one round of branching, which leads to the leaf-level, is presented in the figure. Notice that this is just an outline. You need to label the nodes by indicating the partial solutions they represent, to state an LB for each node (or the reason it is eliminated), to indicate how the UB is updated, and to perform further branching, if the stopping criterion is not reached. You also need to number the nodes in the order they are obtained
Upper bounding
An initial upper bound can be based on schedule (1,3,2,4,5) shown in Fig. 1. Since the maximum lateness of that schedule is 20, we set UB=20. Whenever a better solution is found with an objective value smaller than UB, we replace UB by that smaller value.
Lower bounding
Consider a partial solution obtained after k jobs have been assigned to the first k positions.
j1 j2 ??1 … jk ??2 … time ???
Fig. 2: A partial solution with k jobs assigned to the first k positions
Clearly, the maximum lateness ?max of any complete solution, that has the initial part of the schedule as in Fig. 2, can be estimated as ?max ≥ max{?′ , ?′′ },
where ?′ is the actual maximum lateness of the jobs which have been assigned to the first k positions, ?′ = max{??1 , ??2 , … , ??? },
and L” is the lower bound on the maximum lateness of the remaining unscheduled jobs. As we do not know an optimal sequence of the unscheduled jobs and there is no efficient algorithm for finding it, we consider a relaxed problem, which is easier to solve. We allow processing unscheduled jobs with pre-emption:
- any unscheduled job ? can be preempted and resumed later on;
- for every job, the total duration of its parts should be equal to the job processing time ?? .
The relaxed subproblem, defined for the unscheduled jobs processed with pre-emption, can be solved efficiently by the following algorithm: at every decision point ? which corresponds to a completion time or a release time of some job, schedule an available job with the smallest due date. A job ? is available at time ? if it has not been processed in full before ?, and ?? ≤ ? (job ? is released at time ? or earlier). Note that the formulated rule finds an optimal solution to the problem with pre-emption allowed. It provides a correct lower bound for scheduling jobs without pre-emption.
To illustrate the rule, consider calculating a lower bound for the partial schedule (1,∗,∗,∗,∗). We assume (temporarily) that unscheduled jobs {2,3,4,5} can be processed with pre-emption.
- The first decision point is time ? = 6, when job 1 is completed and unscheduled jobs {2,3,4,5} may start. The only available job at ? = 6 is job 2 (?2 ≤ ?), and we assign job 2 to start at time ? = 6.
- The next decision point is time ? = 14, when job 3 becomes available. There are two available jobs {2,3} at ? = 14. Since ?2 < ?3 (22 < 23), processing of job 2 continues without interruption.
- The next decision point is time ? = 24, when job 2 is completed. The only available job at ? = 24 is job 3, and we assign job 3 to start at time ? = 24.
- The next decision point is time ? = 27, when job 4 becomes available. There are two available jobs {3,4} at ? = 27. Since ?3 < ?4 (23 < 61), processing of job 3 continues without interruption.
- At time ? = 34 job 3 is completed. The only available job at ? = 34 is job 4, and we assign job 4 to start at time ? = 34.
- The next decision point is time ? = 40, when job 5 becomes available. Since ?5 < ?4 (59 < 61), we preempt job 4 and start job 5.
- Finally at time ? = 56 job 5 is completed. We then allocate the remaining part of job 4. The resulting scheduling is illustrated by Fig. 3. The lower bound for (1,,,,) is ?? = max{?′ , ?′′ } = max{−21, 2, 11, −3, 6} = 11.
