XPRESS-MP Tutorial
Projects
Dash Associates
19th May 1999
1
XPRESS-MP ProjectsContents
Contents
Contents2
Overview4
Model Development: Visual XPRESS5
Burglar Bill5
Auction Problem6
Description6
Data6
Formulation6
Workshop Production Planning8
Chemical Production Planning9
Capital Budgeting10
Contract Allocation11
Manpower Planning12
Distribution Planning for a Brewery13
Parameters13
Indices13
Data14
Decision Variables14
Objective Function15
Constraints15
Purchasing with Price Breaks17
Hints17
Production Systems: Console XPRESS18
Auction Problem18
Other Models18
Infeasibility Analysis19
Explaining Infeasibility19
Irreducible Infeasible Sets19
Matrix Files21
Bespoke Systems 1: XPRESS Subroutine Libraries XMSL and XOSL22
Demonstration Examples22
Simple tasks22
Adding things22
Changing things22
Various23
A Binary Fixing Heuristic24
Outline of Program24
Extension24
Your Tasks24
Setting up a Problem from Scratch25
Extension25
Doing RHS Parametrics on a Global Problem26
Your Tasks26
Further Tasks26
Doing Objective Function Parametrics on a Global Problem27
Your Tasks27
Improving the Formulation of the Trimloss Problem28
Difficulties28
Possible Outline of an Algorithm28
Printing the Optimal Tableau29
Bespoke Systems 2: The XPRESS Subroutine Library EMOSL30
Demonstration Examples30
Simple tasks30
Using the view30
Getting model information30
Implementing a Special Solution Strategy for Models with Big M Variable Upper Bounds (MVUB) 31
Your Tasks31
Displaying Relevant Solution Statistics33
Your Task33
More to think about...33
Detecting Data Errors34
Your Task34
More to think about...34
Implementing a Fixing Heuristic for solving MIPs35
Extracting a Single Period Problem from a Multi-Period Problem37
Appendix - Compiling and Linking XPRESS Applications38
EMOSL Applications38
XOSL Applications38
Using Watcom C/C++38
Using Microsoft Visual C/C++39
Using the Microsoft Visual C/C++ Visual Development Environment39
Using Borland C/C++40
1
XPRESS-MP ProjectsOverview
Overview
This booklet is designed to give you practical experience across the whole XPRESS-MP family of products. It contains a number of projects which should be completed by users under general supervision. The projects cover a wide range of the functionality within the XPRESS-MP products.
Users should make full use of the documentation provided with XPRESS-MP, e.g., the on-line help and the reference manuals, when completing these projects. They should also seek to extend the examples given to experiment with different syntax in the XPRESS Modelling Language and features of the XPRESS-MP products.
The first set of projects should be completed using Visual XPRESS. They are designed to give experience with the model language and the features of Visual XPRESS. Visual XPRESS is ideal for developing models.
The second set of projects should be completed using the XPRESS Console Mode products, i.e., mp-model and mp-opt. These products are useful for deploying a model that has already been developed in a production system.
The final set of projects uses the XPRESS Subroutine Libraries and shows how bespoke optimisation systems can be constructed. Some of the more advanced projects implement heuristics for certain models.
Together with this booklet, various materials for each project are included in the projects directory on the course disk. The material includes models and data required for the projects and specimen solutions to the modelling and programming projects (use these wisely). Various other sample models and applications are included in the projects directory to provide supplementary material. See the file examples.txt in the projects directory for details.
The appendix gives details on how to compile XOSL and EMOSL applications.
1
XPRESS-MP ProjectsVisual XPRESS
Model Development: Visual XPRESS
Burglar Bill
This example aims to give practical experience with the basic features of Visual XPRESS including editing and debugging models, the model database, the on-line help and reference manual, optimisation tasks, and obtaining the solution and other optimality information. It should also increase familiarity with the basic syntax of the XPRESS Modelling Language.
Write the Burglar Bill problem as a new problem in Visual XPRESS. You are encouraged to look up the meaning or syntax of model statements or Visual XPRESS functions, making full use of the on-line help and the XPRESS-MP Reference Manual. Use the Quick Reference to Visual XPRESS (part of the on-line help) for assistance in setting up new problems, saving and opening problems, optimising problems etc.
You should write the model in a way that is helpful and meaningful to you, e.g., use your own names for variables, tables and constraints, write your own comments, etc.
Practice debugging the model (if necessary, make deliberate mistakes!). Once you have written the model, experiment with the optimisation functions and options of Visual XPRESS.
! Burglar Problem: Binary variable formulation
LET NItems = 8! Number of items
TABLES
VALUE(NItems)! Value of items
WEIGHT(NItems)! Weight of items
WTMAX! Max weight allowed for haul
DATA
! Item: 1 2 3 4 5 6 7 8
VALUE = 15,100, 90, 60, 40, 15, 10, 1
WEIGHT = 2, 20, 20, 30, 40, 30, 60, 10
WTMAX = 102
VARIABLES
x(NItems)! 1 if we take item i; 0 otherwise
CONSTRAINTS
MaxVal: SUM(i=1:NItems) VALUE(i)*x(i) $! Maximise the value
WtMax: SUM(i=1:NItems) WEIGHT(i)*x(i) < WTMAX! Weight restriction
BOUNDS
x(i=1:NItems) .BV.! All x are 0/1
END
Auction Problem
The purposes of this example are (i) to convert maths to the XPRESS Modelling Language; and (ii) to illustrate how to interface Visual XPRESS with Excel. Data for the XPRESS model should be taken from tables in the worksheet auc.xls and the results of optimisation put back into solution tables in the spreadsheet which can be displayed nicely inside Excel. All this is transparent to the end user.
Description
A company has certain amounts of a perishable item to sell each week and has invited bids for it. Potential purchasers can either bid for a specific amount in a certain week (a ‘Weekly’ bid) or for a certain amount of one or more ‘bundles’, which, if their bid is successful, gets them slightly different amounts each week for the whole period.
The company wants to get as much money as possible. Bidders will accept offers for fractions of their bids.
Data
Parameters
NWeeks / Number of weeks w consideredNBTypes / Number of bundle types t
NBBids / Number of bids i for bundles
NWBids / Number of bids j for weeks
Primary Data Tables
SUPPLY(w) / Supply of good in week wNWEEKB(w) / Number of weekly bids made for week w
BPROF(w,t) / Profile of bundle type t (fraction of quantity bid for in week w)
BBTYPE(i) / Type t of bundle in bundle bid i
BBQTY(i) / Quantity bid for in bundle bid i
BBPRICE(i) / Price offered for bundle bid i
WBWEEK(j) / Week for which week bid j made
WBQTY(j) / Quantity bid for in week bid j
WBPRICE(j) / Price offered for week bid j
Secondary Data Tables
WBSTART(w) / Start of bids for week w in WB tablesRefer to the spreadsheet to see how the data is stored externally. You will need to calculate the data table WBSTART inside the model.
Formulation
Let xi be the fraction of bundle bid i accepted and yi be the fraction of weekly bid j accepted (between 0 to 1).
Maximise Revenue:
Supply of Good:
Workshop Production Planning
This is the first of two LP formulation exercises. You must formulate the problem as an LP, write a model in Visual XPRESS, solve the problem, and check that the solution makes sense in the original problem context.
A firm has three workshops each working 40 hours per week. It can produce two products, the first of which sells at £108 and the second at £84. The only direct cost is labour at £5 per hour. The first product requires 5 hours in shop 1, 9 hours in shop 2, 7 hours in shop 3 and 10 man hours per unit. The second product requires 10 hours in shop 1, 2 hours in shop 2, 5 hours in shop3 and 8 man hours per unit.
Formulate an LP to plan the most profitable operation and solve it.
Chemical Production Planning
A chemical firm can produce three products, each of which requires the other two and labour as inputs in fixed proportions. The products cannot be bought, but are sold at fixed prices, and the wage rate is constant. The available labour force is limited, but plant capacity is adequate for all possible production plans. To produce one unit of product I, 0.4 units of product II, 0.3 units of product III and 3 units of labour are required. To produce one unit of product II, 0.2 units of product I, 0.6 units of Product III and 4 units of labour are required. To produce one unit of product III, 0.7 units of product I, 0.5 units of product II and 2 units of labour are required. The wage rate is £1; product I, sells at £80; product II at £70, and product III at £60. Available labour is 100 units.
Formulate an LP to determine the most profitable production plan and solve it.
The diagram shows per unit requirements and selling prices.
Capital Budgeting
This is the first of three MIP formulation exercises. You must formulate the problem as an LP, write a model in Visual XPRESS, solve the problem, and check that the solution makes sense in the original problem context.
We are considering which of the following eight projects to undertake in the next year. The only effective resource limits on us are the availability of investment capital in £k (CAV) and the availability of skilled personnel (PAV). So each project is evaluated for its return in £k (RET), and the resources used: capital (CAP) and personnel (PER).
The data for each project is:
Project / CAP / PER / RET1 / 104 / 22 / 124
2 / 53 / 14 / 75
3 / 29 / 7 / 42
4 / 187 / 36 / 188
5 / 98 / 24 / 108
6 / 32 / 10 / 56
7 / 75 / 20 / 88
8 / 200 / 41 / 225
The resource limits are CAV: 478 and PAV: 106.
Show that projects 1, 3, 5, 6 and 8 are selected.
Contract Allocation
A public utility, which is divided into six regional districts, wishes to allocate ten power generation contracts to its regions as cheaply as possible. The cost per unit of power generated by each region for each contract is known. If part of a contract is allocated to a region than it must be at least as big as a certain minimum size. For reliability reasons, no contract may be placed exclusively with only one district. Each district has a limited power generation capacity.
District / Max Output / Cost/Unit1 / 50 / 50
2 / 40 / 20
3 / 10 / 25
4 / 20 / 30
5 / 70 / 45
6 / 50 / 40
Contract / 1 / 2 / 3 / 4 / 5 / 6 / 7 / 8 / 9 / 10
Size / 20 / 10 / 30 / 15 / 20 / 30 / 10 / 50 / 10 / 20
Minimum contract size is 5 units
Manpower Planning
Over the next 6 months we have three projects which can be done. Each of these projects has a profile of manpower requirements over its lifetime, and a benefit which accrues each month when the project has been completed.
Our problem is to determine when each project is to start, subject to the constraint that in no month can we try to use more manpower than is available.
The data are as follows:
Project / Duration / Profile / Benefit per month1 / 3 / 3,4,2 / 10.2
3 / 3 / 4,1,6 / 12.3
3 / 4 / 3,2,12 / 4.2
e.g., project 1 takes 3 months. In its first month it uses 3 people, in its second, 4 people, and in its third, 2 people.
The total manpower availability is:
Month / 1 / 2 / 3 / 4 / 5 / 6Available / 5 / 6 / 5 / 5 / 6 / 5
Distribution Planning for a Brewery
This is a much larger model in terms of the number of data tables, sets of variables and sets of constraints than we have considered up to now. It is an exercise in converting a mathematical formulation into an XPRESS formulation, and should illustrate the power of the XPRESS notation in representing complex formulae succinctly.
In the UK brewing companies brew two major different types of beer, ale and lager. Each type comes in several varieties (liquid types), distinguished by taste, colour, flavour and strength and several other characteristics.
Most beers are sold in four major containers: cans, bottles, barrels and ‘cellar tank’. When packaged in the latter form the beer is delivered in bulk to a tank at the retail outlet (usually a pub) and then served to the customer straight from the tank. Not all liquid types go into each container, and in fact the actual number of commodities (i.e. a liquid type in a specific container) is significantly smaller than the maximum theoretical number.
When a particular liquid is brewed at one of the breweries it is taken to a packaging unit to be placed in a container. Sometimes this journey is very short if, for instance, the packaging unit is sited adjacent to the brewery and connected to it by pipeline. But since packaging units are expensive it is sometimes necessary to transport liquid in bulk from the brewery to a packaging unit of the correct type.
Each brewery belonging to the company has a separate limited capacity for lager and for ale, but the capacity within these two sub-categories may be freely allocated to any of the liquid types. A packaging unit can only put liquids into one type of container.
After liquids have been put into containers (and have become a commodity) they are then transported to customer zones (demand points). These are typically depots owned by the company, or the premises owned by wholesalers or supermarkets.
Parameters
NALES / Number of alesNLAGER / Number of lagers
NL / Number of liquid types = NALES + NLAGER
NB / Number of breweries
NP / Number of packaging units
ND / Number of demand points
NC / Number of commodity types
NT / Number of container types
Indices
c / Commodityb / Brewery
p / Packaging unit
t / Pack type (container)
d / Demand point
l / Liquid type
Data
The company wished to consider the data as being driven by the commodities, that is, the combinations of liquid type in a particular container. A partial list might be
Commodity Number / Liquid / Container... / ... / ...
16 / B23L / Barrels
17 / B23L / Half pint bottles
18 / G26A / Pint bottles
... / ... / ...
Data were collected and assembled into the following tables
UCBP(p,b) / Unit transport cost from brewery b to packaging unit pUCPD(t,d,p) / Unit transport cost of pack-type t from packaging unit p to demand point d
LREQ(c) / Liquid required by commodity c
TREQ(c) / Container type required by commodity c
BCAP(b,2) / Brewing capacity at brewery b (1: Ale; 2: Lager)
PCAPTOT(p) / Total packaging capacity
DEMAND(c,d) / Final demand for commodity c at demand point d
CANBRW(l,b) / 1 if brewery b can brew liquid l
NCANB(l) / Number of breweries that can brew liquid l
MAXBRW(b) / Maximum amount that can be brewed at b
MINBRW(b) / Minimum amount that can be brewed at b
MAXPK(p) / Maximum amount that can be packed at p
MINPK(p) / Minimum amount that can be packed at p
Decision Variables
brew(l,b) / the amount of liquid l brewed at brewery b (only defined if the brewery can brew the liquid).ifb(l,b) / 1 if any liquid l is brewed at brewery b (only defined if the brewery can brew the liquid and there is more than one brewery that can brew the liquid); otherwise 0.
pk(l,p) / the throughput of liquid l through packaging unit p (only defined if the capacity of the packaging unit is non-zero)
ifp(l,p) / 1 if any of liquid l is packaged at packaging unit p (again, only defined if the packaging unit has non-zero capacity), 0 otherwise.
lq(b,l,p) / amount of liquid l sent from brewery b to packaging unit p (only defined if brewery b can brew liquid l)
pack(c,p) / amount of commodity c packed at packaging unit p (only defined if the packaging unit has a non-zero capacity)
x(p,c,d) / quantity of commodity c sent from packaging unit p to demand point d (only defined if the packaging unit has a non-zero capacity and the demand for commodity c at point d is non-zero)
Explicitly allowing for zero capacity at a packaging unit may seem peculiar, but one of the aims of the exercise was to consider the possible closure of one or more of the packaging units. Different scenarios could easily be considered by setting PACPTOT(p) = 0 for a packaging unit that was to be closed.
Objective Function
The objective function to be minimised was the total cost of transporting liquids from breweries to packaging units, plus the total cost of distributing commodities from packaging units to demand points. It would be easy to incorporate differential per unit brewing and packaging costs but these were not thought to be important in the initial stages of the study.
Constraints
1. Liquid balance at each brewery: each liquid/brew combination goes to some packaging unit.
2. Define the throughput of liquid l through packaging unit p as the total amount packaged of all commodities requiring liquid l.
3. The total amount of ale brewed at a brewery is less than or equal to its ale capacity, and correspondingly for lager.
4. Conservation of liquid going into the packaging units and being packed means that
5. The capacity limitation at the packaging unit means that
6. Conservation of each commodity leaving each packaging unit gives us the equations
7. Satisfying the demands for each commodity at each demand point exactly yields
8. The throughput of liquid l through p is zero if the ifp variable is zero, otherwise it must be greater than the minimum packaging level for any commodity and less than the maximum packaging capacity
This is a common formulation device. As the ifp variables are binary (0 or 1) then if the ifp variable is 0 the pk variable is zero, whilst if it is 1 then the pk is constrained to be less than the maximum value MAXPK and greater than the sensible minimum value MINPK. (These sorts of constraints occur sufficiently frequently for the semi-continuous variable construct to have been devised specially. For the sake of simplicity, they are not used here).
9. Constraints similar to 8 above, but applying to the brewing of liquids at breweries. These constraints only apply if there is more than one brewery which can brew a particular liquid.
So if ifb is 0 then brew is 0. But if an ifb is l then the brew must be at least the smallest sensible quantity to brew at the brewery but not more than the maximum amount that can be brewed by any brewery.