ISE 426 Homework 4

ISE 426: Optimization and Applications (Spring 2022) Instructor: Dr. Karmel S.Shehadeh Homework #4-Due via Course Site at 9 AM on April 11, 2022 Instructions • Show all of the work leading to the solution of each problem. Points are allocated to all of the steps of the solution process, not just the final answer. • I strongly encourage you to type all your assignment solutions using your favorite typesetting system (e.g., MS Word, L A T E X, etc.). For your convenience, a L A T E X template for typing your solution is available in the assignment folder on the Course Site . • If you write an AMPL code to solve any problem, you are required to provide a carefully and detailed commented version of the code in an appendix of the assignment . Note that your code is NOT a substitute for a detailed written explanation of the approach you take to solve the problem and your results. • Include a title page with assignment number, your name and contact information, and the names of all students that you discussed your assignment with (if any). Make sure that you scan/compile your HW work into a single and legible PDF file. “ Bonne chance! ”

ISE 426 Homework #4-Due via Course Site at 9 AM on April 11, 2022 Spring 2022 Question 1 (25 points). MILP Formulation for an Assignment Problem. There are two machines for processing jobs, each with an availability of 6 hours. Consider the following seven possible jobs with their respective profits and processing times. Table 1: Profit and processing time of each job Job 1 2 3 4 5 6 7 Profit p j 10 5 20 12 14 7 8 Processing time t j (in hour) 2.5 1.5 4.5 2.8 3 1.7 1.8 1.1 Formulate a mixed-integer linear program that determines the optimal job assignment on the two machines that maximize the total profit. In particular, clearly specify the (a) (5 points) Decision variables. (b) (3 points) Objective. (c) (7 points) Constraints. 1.2 Model and solve the problem using AMPL . In particular, produce a print-out of the following (a) (5 points) AMPL code (model and data). (b) (2.5 points) Optimal solution. (State clearly, in words, the optimal schedule) (c) (2.5 points) Optimal objective value. Lehigh University Page 1 of 5

ISE 426 Homework #4-Due via Course Site at 9 AM on April 11, 2022 Spring 2022 Question 3 (20 points). Fun with Binary Variables: Switching Constraints A firm must produce either 1000 units of product A and 1500 units of product B or 1500 units of product A and 1000 units of product B. There are three processes that can be used to produce these two products. Each process requires a certain number of labor hours and machines. The input and product of each process per hour is given in the following table. Input Product Labor (hr) Machine (unit) A (unit) B (unit) Process 1 20 35 40 42 Process 2 12 12 45 35 Process 3 25 28 36 44 There is 600 labor hours available at a cost of $12 per hour and an unlimited number of machines at a cost of $15 per unit. 1. ( 10 points) Formulate the problem as a mixed-integer linear program using appropriate binary variable(s) to decide the number of hours employed in each process at a minimum cost. Make sure you clearly state the decision variables, objective, and constraints of the problem. 2. ( 10 points) Suppose that the firm has one more option in the production requirement. Specifically, the firm can produce products A and B that satisfy either one of the following requirements. (a) 1000 units of product A and 1500 units of product B (b) 1200 units of product A and 1200 units of product B (c) 1500 units of product A and 1000 units of product B Formulate the problem with this new set of requirements as a mixed-integer linear program using appropriate binary variable(s) to decide the number of hours employed in each pro- cess at a minimum cost. Make sure you clearly state the decision variables, objective, and constraints of the problem. Food for thought (i.e., no need to answer): could you generalize the problem formulation in part 2 if the firm only needs to satisfy one of k > 3 different requirements? Lehigh University Page 3 of 5

ISE 426 Homework #4-Due via Course Site at 9 AM on April 11, 2022 Spring 2022 Question 4 (25 points). Fun with Binary Variables: Logical Conditions. Consider the following two binary variables x 1 ∈ { 0 , 1 } , x 2 ∈ { 0 , 1 } . I need your Superstar magic in using these variables to represent the outcome of the three logical operations AND, OR, XOR. The definition of these three operations is as follows: • Let y = ( x 1 AND x 2 ). That is, y = 1 if and only if x 1 and x 2 are 1, and 0 otherwise. • Let z =( x 1 OR x 2 ). That is, z = 1 if and only if at least one of these variables x 1 and x 2 is 1, and 0 otherwise. • Let v = ( x 1 XOR x 2 ). That is, v is 1 if and only if the variables x 1 and x 2 have different values, and is 0 otherwise. Table 2 shows the value of each variable z, y, v as a function of the value of x 1 and x 2 . The definition in the table is equivalent to the one given above. Table 2: Value of z, y, v as a function of x 1 and x 2 . y (AND) z (OR) v (XOR) x 2 = 0 x 2 = 1 x 2 = 0 x 2 = 1 x 2 = 0 x 2 = 1 x 1 = 0 0 0 0 1 0 1 x 1 = 1 0 1 1 1 1 0 4.1 ( 8 points ) Write a set of linear constraints that define y = ( x 1 AND x 2 ). The constraints should only involve the variables y , x 1 , and x 2 . 4.2 (8 points) Write a set of linear constraints that define z =( x 1 OR x 2 ). The constraints should only involve the variables z , x 1 , and x 2 . 4.3 (8 points) Write a set of linear constraints that define v = ( x 1 XOR x 2 ). You are allowed to introduce an additional auxiliary variable. Thus, the constraints should involve the variables v , x 1 , x 2 , and possibly an additional variable w . 4.4 (1 point) Any feedback on this question? Was it difficult? Fun? etc. Lehigh University Page 4 of 5