MA306 Combinatorial Optimisation

1.Formulate, but do not solve, the following mathematical problems:

 

i) A courier traveling to Europe can carry up to 60 kilograms of a commodity. Each kilogram of such commodity can be sold for £35. The round trip air fare is £450 and
includes a checked and a carry-on luggage of up to 25 kilograms (combined), any kilogram in excess will cost £6 each. Ignore possible profits on the return trip, and formulate the problem that answers the question whether the courier should travel to Europe or not, and if they do it, how much of the commodity should be taken along in order to maximise the profits.

 

ii) The marketing group of we-can-sell-anything Company is considering the options for the new advertising campaign program. After some market study, the group
identified a selected number of options with their details below:

The objective of the group is to maximise the number of customers reached, subject to the limitations of resources given by the last column of the table. In addition the following constraints have to be met.

 

For the campaign to be accepted it requires that either Radio or Newspaper is supported.

 

The company cannot advertise in both Facebook and Twitter at the same time.

 

Formulate the integer programming model that allows to identify the best advertisement strategy.

 

2. Considering the problem of a nation that wants to plan its energy generation. Energy can be generated through five systems j ∈ {1, 2, 3, 4, 5}: nuclear plants (j = 1), coal plants (j = 2), combined cycle gas turbine (CCGT) plants (j = 3), wind turbines (j = 4), and solar cells (j = 5).

 

Each system has a specific power capacity, building cost, and level of CO2 emission. Only a limited number of plants of the same type can be built. The nation also has a limited budget to spend in the construction of the respective plants, and they need to satisfy certain demand. Furthermore, there is an upper limit on the permitted CO2 emissions. The goal of this problem is to find the appropriate number of plants that satisfy all the above conditions.

 

i) Define your parameters and decision variables.

 

ii) Formulate the constraint that ensures that the chosen mix of energy meet the demand.

 

iii) Formulate the constraint that ensures that the chosen mix of energy is within the total budget.

 

iv) Formulate the constraint that ensures that the chosen mix of energy stays within permitted levels of CO2.

 

v) Formulate the constraint that ensures that the number of each type of plants does not exceed the maximum allowed.

 

vi) Does this problem need an objective function? Justify.

 

vii) Write down the full IP.

 

3. You are working in a mine as a geologist, and you have to determine the best selection of 5 out 10 possible sites. Label the sites as s1, s2, ..., s10 and the respective expected profits as p1, p2, ..., p10. Consider the following constraints:

 

i) If site s2 is explored, then site s3 also has to be explored.

 

ii) Exploring sites s1 and s7 will prevent you from exploring site s8.

 

iii) Exploring sites s3 or s4 will prevent you from exploring site s5.

 

Formulate an integer program to determine the best exploration scheme.

 

4. Let {A, B} be two indivisible single unit products, and u1, u2, u3 three interested buyers. The following table depicts how much each buyer is willing to pay for every subset of products, and the objective of the problem is to maximise the total payments.

 

Meaning for example that buyer u2 is willing to pay £9 for product A, and £10 for the bundle {A, B}. Notice also that if someone buys A, then the bundle {A, B} cannot be bought by someone else.

 

a) Model the problem as an integer program.

 

b) Find by inspection the optimal solution.

 

c) How do your answers for a) and b) change if buyer u3 has a total budget of £15.