1. Homepage
  2. Homework
  3. COMP3910 – Combinatorial Optimisation - Coursework 2: Modelling Strong Formulations
This question has been solved

COMP3910 – Combinatorial Optimisation - Coursework 2: Modelling Strong Formulations

Engage in a Conversation
COMP3910Combinatorial OptimisationModellingStrong FormulationsUKUniversity of Leeds

COMP3910 – Combinatorial Optimisation Coursework 2: Modelling; Strong Formulations; Deadline: CourseNana.COM

Award: CourseNana.COM

This piece of summative coursework is worth 10% of your grade CourseNana.COM

Submission: CourseNana.COM

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) CourseNana.COM

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: CourseNana.COM

                | 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 CourseNana.COM

The company has 720 man-hours available in the coming week. CourseNana.COM

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. CourseNana.COM

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). CourseNana.COM

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. CourseNana.COM

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, CourseNana.COM

?1 , ?2 , ?3 ≥ 0, ?, ?1 , ?2 , ?3 ∈ {0,1}. CourseNana.COM

The disjunctive constraints CourseNana.COM

3?1 + 4?2 + 2?3 ≤ 30 or 4?1 + 6?2 + 2?3 ≤ 40 CourseNana.COM

are modelled as CourseNana.COM

3?1 + 4?2 + 2?3 ≤ 30 + ?′ ?, (1) 4?1 + 6?2 + 2?3 ≤ 40 + ? (1 − ?). (2) CourseNana.COM

One possible choice is ? = 36 (see Chapter 6). In fact a smaller value of ?′ can be selected. Find such a value. Provide a justification. CourseNana.COM

Question 3 [23 marks] Consider an instance of the scheduling problem given by the table: CourseNana.COM

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. CourseNana.COM

Problem description and instructions for Question 3. CourseNana.COM

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: CourseNana.COM

  • 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) CourseNana.COM

Notice that if job ? is completed before its due date, then ?? is negative. CourseNana.COM

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. CourseNana.COM

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. CourseNana.COM

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. CourseNana.COM

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.) CourseNana.COM

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 ,∗). CourseNana.COM

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 CourseNana.COM

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. CourseNana.COM

Lower bounding

Consider a partial solution obtained after k jobs have been assigned to the first k positions. CourseNana.COM

j1 j2 ??1 … jk ??2 … time ??? CourseNana.COM

Fig. 2: A partial solution with k jobs assigned to the first k positions CourseNana.COM

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{?′ , ?′′ }, CourseNana.COM

where ?′ is the actual maximum lateness of the jobs which have been assigned to the first k positions, ?′ = max{??1 , ??2 , … , ??? }, CourseNana.COM

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: CourseNana.COM

  • 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. CourseNana.COM

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. CourseNana.COM

  • 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.

Get in Touch with Our Experts

WeChat WeChat
Whatsapp WhatsApp
COMP3910代写,Combinatorial Optimisation代写,Modelling代写,Strong Formulations代写,UK代写,University of Leeds代写,COMP3910代编,Combinatorial Optimisation代编,Modelling代编,Strong Formulations代编,UK代编,University of Leeds代编,COMP3910代考,Combinatorial Optimisation代考,Modelling代考,Strong Formulations代考,UK代考,University of Leeds代考,COMP3910help,Combinatorial Optimisationhelp,Modellinghelp,Strong Formulationshelp,UKhelp,University of Leedshelp,COMP3910作业代写,Combinatorial Optimisation作业代写,Modelling作业代写,Strong Formulations作业代写,UK作业代写,University of Leeds作业代写,COMP3910编程代写,Combinatorial Optimisation编程代写,Modelling编程代写,Strong Formulations编程代写,UK编程代写,University of Leeds编程代写,COMP3910programming help,Combinatorial Optimisationprogramming help,Modellingprogramming help,Strong Formulationsprogramming help,UKprogramming help,University of Leedsprogramming help,COMP3910assignment help,Combinatorial Optimisationassignment help,Modellingassignment help,Strong Formulationsassignment help,UKassignment help,University of Leedsassignment help,COMP3910solution,Combinatorial Optimisationsolution,Modellingsolution,Strong Formulationssolution,UKsolution,University of Leedssolution,