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.

At the beginning of a dinner party, several participants shake hands with each other. Show that the participants that shook hands an odd number of times must be even in number.

In an undirected connected graph G = (N, A), an Euler tour is a walk that starts at some node, visits each arc exactly once, and returns to the starting node. A graph is Eulerian if it contains an Euler tour. Show that in an Eulerian graph, the degree of every node is even. Next, show that if every node in a connected graph has an even degree, the graph is Eulerian. Establish the second result by describing an O(m) algorithm for determining whether a graph is Eulerian and, if so, will construct an Euler tour. (Hint: Describe an algorithm that decomposes any graph with only even-degree nodes into a collection of arc-disjoint cycles, and then converts the cycles into an Euler tour.)

Printing Neatly: Consider the problem of neatly printing a paragraph on a printer. The input text is a sequence of n words of lengths l1, l2, . . . , ln, measured in characters. We want to print this paragraph neatly on a number of lines that hold a maximum of M characters each. Our criterion of “neatness” is as follows. If a given line contains words i through j, where i ≤ j , and we leave exactly one space between words, the number of extra space characters at the end of the line is M-J+i- ∑_(k=i)^j▒l_k , which must be nonnegative so that the words fit on the line. We wish to minimize the sum, over all lines except the last, of the cubes of the numbers of extra space characters at the ends of lines. Give a dynamic-programming algorithm to print a paragraph of n words neatly on a printer. Analyze the running time and space requirements of your algorithm.

Suppose that a network G = (N, A) contains no negative cycle. In this network, let fij denote the maximum amount by which we can decrease the length of arc (i, j) without creating any negative cycle, assuming all other arc lengths are held constant. Describe an efficient algorithm for determining fij for each arc (i, j).

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.