Spring 2019 – ISE 2404 – Deterministic OR – I Semester Project – Part II
Due Date: May 13th, 2019 (by 10 am EST)
Read this document carefully and completely before starting second part of the semester project.
General Instructions
• This part of the project will constitute 15% of your final grade and must be performed by teams same as for Part I of the semester project. In case because of any major conflict, you plan to change your team, you are required to get approval from the instructor.
• Please note that submitting another team’s work or part of it as your own team’s work (including sharing any part of your code with any other team) is plagiarism and will result in grade zero for the projects of both teams and other appropriate actions.
• In case your team refer to any book or research paper other than the textbook for this project, please cite the reference in your report.
• Make sure you satisfy all the following requirements regarding delivery of your project outcomes.
Delivery Requirements for Part II
You will lose points if you do not follow the items below exactly:
• Create one .mod file for each formulation (FOCP-Primal, FOCP-Dual, and SUDOKU, a total of three files). Please name each file with the first names of the team members followed by the formulation name. Example: The file name of .mod file for formulation FOCP-Primal submitted by John Lee and Nikita Jolie should be JohnNikita_FOCP-Primal.mod. The same rule applies to all other files.
• Comments in the code are absolutely necessary. Comments should be such that one could understand the whole problem and model just by reading your code and comments. In particular all parameters, variables, the objective function, and constraints should have associated comments clearly explaining them. The comments should be self-contained and not refer to the problem description. Make your best effort to make your .mod files neat, clear and readable. We will not spend time deciphering disorderly files.
• Names of the variables and parameters in your .mod files should be the same as the notations specified in the problem description.
• Your model file should be completely independent of the data such that any problem with any size can be solved using it just by changing the data in the data file.
• Your script files should run correctly and generate exactly the output that you will submit in your report.
• By the due date the following items must be delivered following the stated instructions:
o A zip file named with the first names of your team members (e.g. JohnNikita.zip in the example above) containing your model, data, script, .mps, and cplex log files.
o A report paying attention to the following requirements:
The report should have a cover sheet containing the names of team
members and the Hokie Honor Code.
The report should have sections corresponding to the sections of this document and contain the requested output in each section presented in appropriately designed tables in a clean format as well as answers to all questions posed in each section. The answers should clearly argue the reasons, if needed but be concise and to the point. The report should not contain copy of your .mod, .dat, script, and cplex log files.
o On or before the due date, send to me (ise-2404-g@vt.edu) the zip file containing all aforementioned files as well as the pdf (no other format is acceptable) of your report as attachments to one email. The email must be sent by only one of your team members. The email should contain the name of all your team members and their emails must be in the cc line.
o A hard copy of the report (not the codes) must be submitted on the due date too (Delivery Location: 227 Durham Hall). This hard copy must be printed double-sided in a clean format.
PROJECT DESCRIPTION – PART II
Fiber Optic cabling prOblem
A fiber optic cabling company XYZ wants to know how to allocate its machines to make the various types of fiber optic cables that it will produce during a quarter-year time horizon. The sales department has forecast demands for each of the 15 types of cables that are to be produced during this quarter. Table 1 gives the demand, the variable cost, and the selling price for each type of cable. The plant operates continuously during the quarter, i.e., 13 weeks, 7 days a week, and 24 hours a day.
There are two types of machines: Duplex and regular. Duplex machines can be used to make all types of cables and are the only machines that can produce certain types of cables. Table 1 gives the rate of production for each type of cable on each type of machine. Note that if the production rate for a type of cable on a regular machine is zero, it cannot be produced on a regular machine. Also if a type of cable can be produced on either type of machine, its production rates are equal. There are 90 regular machines and 15 Duplex machines. For this project, the time requirement to change over a machine from one type of cable to another is assumed to be negligible.
Cables produced at the XYZ company proceed to the finishing department in the plant and are then sold. Any cables that are not produced in the plant because of limited machine capacity will be bought from the outside market (i.e., outsourced or subcontracted), finished at the XYZ company, and sold at the selling price. Table 1 gives the outside market cost for each type of cable.
Problem 1. (50 points) Management would like to know how to allocate the machines to the types of cables and which cables to buy on the market. Using AMPL and CPLEX, solve your
2
linear programming model formulated in Part I with the objective of maximizing profit. Report the optimal solution value and the optimal solution.
Table 1. Problem Data
Cable
Demand (in yards)
Selling Price ($/yard)
Duplex Rate (yard/hour)
Regular Rate (yard/hour)
Plant Cost ($/yard)
Outside Cost ($/yard)
1
16500
0.987
4.653
0.00
0.6573
0.80
2
52000
0.831
4.653
0.00
0.555
0.70
3
45000
0.831
4.653
0.00
0.655
0.85
4
22000
0.855
4.653
0.00
0.5542
0.70
5
76500
1.0375
5.194
5.194
0.6097
0.75
6
110000
0.84
3.809
3.809
0.6153
0.75
7
122000
0.88
4.185
4.185
0.6477
0.80
8
62000
1.102
5.232
5.232
0.4880
0.60
9
7500
1.243
5.232
5.232
0.5029
0.70
10
69000
0.95
5.232
5.232
0.4351
0.60
11
70000
1.4
3.733
3.733
0.6417
0.80
12
82000
0.97
4.185
4.185
0.5675
0.75
13
10000
0.85
4.439
4.439
0.4952
0.65
14
3800000
0.625
5.232
5.232
0.3128
0.45
15
62000
0.698
4.185
4.185
0.5029
0.70
Problem 2. (50 points) Formulate the dual of the linear programming formulation for the Fibre Optic Cabling Problem. Use general algebraic notation and the format studied in ISE 2404 to present your dual model. Using AMPL and CPLEX, solve this dual linear program and report the optimal solution value and the optimal solution.
Problem 3. (50 points) Perform a thorough sensitivity analysis of your (primal) linear programming formulation by modifying cost coefficients, constraint matrix, and/or RHS of the constraints. [This problem requires creativity in modifying the data parameters such that this analysis provide the management some insight about its operations. Please present your results and observation, using charts and graphs with complete description, in the report assuming that your team is a consultant firm seeking consultancy contract from this cable company.]
SudOku
Problem 3. (50 points) Using AMPL and CPLEX, solve your mathematical formulation for two instances/examples of general Sudoku puzzle for 9 × 9 matrix. Report the optimal solution for both instances, i.e. provide solved Sudoku puzzle, and verify your solution.
Sudoku is a well-known puzzle in which given a matrix of size 9 × 9 with certain cells filled by numbers, the goal is to fill the matrix such that each column, row, and 3 × 3 submatrix contains numbers 1 through 9 exactly once.
3