A clothing company is in the process of creating a set of new shipments sS. Each shipment combines a set of available clothing items from the set F. Each clothing item iF has an expected sales revenue of ri dollars, handling cost of ci and the total number of units available of item i is di. Also the maximum number of distinct shipments that can be made is equal to K. Finally for each shipment the total handling cost should not exceed 50% of the expected revenue. You have been hired by this company to help optimize the shipments that should be sent out in order maximize the total expected revenue. The company has decided to model the problem in the following way: Let S be the set of all feasible shipment patterns that can be created. Let ais be the number of clothing item i in shipment s. Let rs=iF aisri be the expected revenue from shipment s. Let variables xs be equal to 1 if shipment s will be sent, and 0 otherwise. Then the problem formulation follows: The first set of constraints makes sure that not more than the available amount is sent out for each item i. The last constraint makes sure that no more than K shipments are sent. Suppose you are given dual variables ai for the first set of constraints, for the last constraint. Now consider solving the LP relaxation of this problem and answer the following questions. (a) Write down a formula for the reduced cost for a variable xs. (b) Assuming that you are using column generation for solving the problem, explain how you might set up your pricing problem. Explain what the decision variables will be and write down the objective function and constraints. A clothing company is in the process of creating a set of new shipments sS. Each shipment combines a set of available clothing items from the set F. Each clothing item iF has an expected sales revenue of ri dollars, handling cost of ci and the total number of units available of item i is di. Also the maximum number of distinct shipments that can be made is equal to K. Finally for each shipment the total handling cost should not exceed 50% of the expected revenue. You have been hired by this company to help optimize the shipments that should be sent out in order maximize the total expected revenue. The company has decided to model the problem in the following way: Let S be the set of all feasible shipment patterns that can be created. Let ais be the number of clothing item i in shipment s. Let rs=iF aisri be the expected revenue from shipment s. Let variables xs be equal to 1 if shipment s will be sent, and 0 otherwise. Then the problem formulation follows: The first set of constraints makes sure that not more than the available amount is sent out for each item i. The last constraint makes sure that no more than K shipments are sent. Suppose you are given dual variables ai for the first set of constraints, for the last constraint. Now consider solving the LP relaxation of this problem and answer the following questions. (a) Write down a formula for the reduced cost for a variable xs. (b) Assuming that you are using column generation for solving the problem, explain how you might set up your pricing problem. Explain what the decision variables will be and write down the objective function and constraints
