Operation research Interview Questions

Questions about optimization in logistics

Operations Research Analyst

Interviewed at R+L Carriers

3.5★

May 7, 2019

Questions about optimization in logistics

crew day off allocation provlem

Operations Research Engineer

Interviewed at Wheels Up

3★

Dec 2, 2020

crew day off allocation provlem

Cutting stock problem. The production of paper or cloth often uses the following process. We first produce the paper on long rolls which we then cut to meet specific demand requirements. The cutting stock problem is to meet the specified demand by using the minimum number of rolls. Suppose that the rolls all have length L and that we have a demand of di for smaller rolls of size Li • There might be many ways to cut any roll into smaller rolls. For example, if L = 50 and the Li have lengths 10, 15, 25, 30, we could cut the rolls into several, different patterns: for example, (1) 5 rolls of size 10; (2) 3 rolls of size 15; (3) 2 rolls of size 10 and 1 roll of size 25. Note that in the first pattern, we use the entire roll of size L, but in the other two patterns we incur a waste of 5. Let P denote the collection of all patterns, and for any pattern p ∈ P, let ni,p denote the number of small rolls of size Li in pattern p. (a) Letting xp be a nonnegative integer variable indicating how many rolls we cut into pattern p, show how to formulate the cutting stock problem of finding the fewest number of large rolls to meet the specified demands as an optimization model with a variable for each cutting pattern. (b) Suppose that we wish to cut a single roll of size L into sub-rolls and that we receive a profit of πi for every sub-roll of size Li that we use in the solution. Show how to formulate this problem as an integer knapsack problem. (c) Show how to use the column generation technique to solve the linear programming relaxation of the cutting stock problem in part (a), using knapsack problems of the form stated in part (b) to price out columns.

Senior OPerations Research Scientist

Interviewed at Optym

3.6★

Dec 24, 2022

Cutting stock problem. The production of paper or cloth often uses the following process. We first produce the paper on long rolls which we then cut to meet specific demand requirements. The cutting stock problem is to meet the specified demand by using the minimum number of rolls. Suppose that the rolls all have length L and that we have a demand of di for smaller rolls of size Li • There might be many ways to cut any roll into smaller rolls. For example, if L = 50 and the Li have lengths 10, 15, 25, 30, we could cut the rolls into several, different patterns: for example, (1) 5 rolls of size 10; (2) 3 rolls of size 15; (3) 2 rolls of size 10 and 1 roll of size 25. Note that in the first pattern, we use the entire roll of size L, but in the other two patterns we incur a waste of 5. Let P denote the collection of all patterns, and for any pattern p ∈ P, let ni,p denote the number of small rolls of size Li in pattern p. (a) Letting xp be a nonnegative integer variable indicating how many rolls we cut into pattern p, show how to formulate the cutting stock problem of finding the fewest number of large rolls to meet the specified demands as an optimization model with a variable for each cutting pattern. (b) Suppose that we wish to cut a single roll of size L into sub-rolls and that we receive a profit of πi for every sub-roll of size Li that we use in the solution. Show how to formulate this problem as an integer knapsack problem. (c) Show how to use the column generation technique to solve the linear programming relaxation of the cutting stock problem in part (a), using knapsack problems of the form stated in part (b) to price out columns.

A company is planning to hire employee on different day-shifts to meet its workload demand. The employees in each day-shift can work for at most five consecutive days and require two days weekly off. For example, if the day-shift for an employee starts on Monday, he/she will have weekly off on Saturday and Sunday, whereas, a day-shift starting on Wednesday will have weekly off on Monday and Tuesday. A day-shift can start on any day of the week (day 1 = Monday, ……, day 7 = Sunday). If cost of each shift is c_1,⋯,c_7 and workload demand for number of people on any given day i in the month is D_i,0≤i≤N (where N is the number of days in the week). Write a Mixed Integer Programming formulation to minimize the total wage cost by the company while ensuring that workload demand is fulfilled.

Senior OPerations Research Scientist

Interviewed at Optym

3.6★

Dec 24, 2022

A company is planning to hire employee on different day-shifts to meet its workload demand. The employees in each day-shift can work for at most five consecutive days and require two days weekly off. For example, if the day-shift for an employee starts on Monday, he/she will have weekly off on Saturday and Sunday, whereas, a day-shift starting on Wednesday will have weekly off on Monday and Tuesday. A day-shift can start on any day of the week (day 1 = Monday, ……, day 7 = Sunday). If cost of each shift is c_1,⋯,c_7 and workload demand for number of people on any given day i in the month is D_i,0≤i≤N (where N is the number of days in the week). Write a Mixed Integer Programming formulation to minimize the total wage cost by the company while ensuring that workload demand is fulfilled.

Complexity of Dijkstra's algorithm.