A Gentle Introduction to Linear Programming for Enchanters

What is this guide all about, anyways?

Let’s start by getting the obvious out of the way — I’ve been an unabashed online gamer in my checkered past, particularly in the realm of Massively Multiplayer Online Role-Playing Games (MMORPGs).  I’ve dabbled in several variants of the genre, including the most popular (currently), World of Warcraft (WoW).  WoW presently boasts over 10 million subscribers, making it the largest and most successful MMORPG to date.

For those of you not familiar with the game, think online, computer-based Dungeons and Dragons.  For the purposes of this article, the only things that are important to know is that you can train in various professions, including Enchanting, and you can buy and sell goods in the online economy.

An Enchanter can take a magical item and break it down into its constituent parts (this is the ‘willing suspension of disbelief’ part of the article).  Those components can then be used to enchant armor and weapons so they have better attributes. For more about enchanting than you ever thought existed, check out this article on the WoWWiki.

So after a long hiatus from the game, I logged into my mage, who happens to have Enchanting as a profession, and saw bags upon bags of enchanting components.  The question arose — what enchantments can I create using these components, and what’s the best use of these enchantments in terms of maximizing my profit in the online world?

It turns out that this is a classic linear programming problem.  So, good geek that I am, I worked the example and then wrote an article about it for posterity.

Linear What?

So if you thought the introduction to WoW and Enchanting was deep, I have bad news… the rabbit hole goes a lot deeper.  Linear programming is a specific optimization technique under the general heading of mathematical programming.  Basically, it seeks to find a mathematical solution to a problem with multiple constraints.  The usual example goes like this:

A wood shop can create tables or chairs. 
A table takes 8 linear feet of wood and 5 hours to make, a chair takes
4 linear feet of wood and 2 hours to make.  The shop has 500 linear
feet of wood available.  A table sells for $50 and a chair sells for
$30.  Given a 40-hour work week, how many tables and chairs should the shop make in order to
maximize profit?

This problem has all the elements needed for a linear programming solution:

1. A constrained resource or resources with multiple potential uses
2. A product mix distribution showing how resources can possibly be allocated
3. A cost or revenue component
4. An objective function that specifies what it is that you’re trying to maximize or minimize (in this case, profit).

The formal definition of what constitutes a candidate for linear programming is more complex, but this should suffice for starters.

In order to solve this problem using linear programming, we reformat it into a set of simultaneous linear equations and an objective function, as such:

Maximize 50*T + 30*C
subject to:
8*T + 4*C <= 500
5*T + 2*C <= 40
T >= 0
C >= 0

Taken line-by-line:

T represents the number of tables we should make
C represents the number of chairs we should make
50*T + 30*C represents the total profit we’ll make at $50/table and $30/chair
8*T + 4*C <= 500 constrains the amount of wood used to be less than or equal to 500 linear feet
5*T + 2*C <= 40 constrains the number of hours spent to be less than or equal to 40 hours
T >= 0 and C >= 0 constrain the model to positive outcomes only.

Using the ECLiPSe tool’s eplex linear program solver, we structure the program as such:

:- lib(eplex).

model(Vars, Obj):-
Vars = [T, C],
T $>= 0, C $>= 0,
8*T + 4*C $=< 500,
5*T + 2*C $=< 40,
optimize(max(50*T + 30*C), Obj).

Hopefully, aside from some syntactic flavoring, it should be clear how the equations are represented in the ECLiPSe program. Running this linear program, we get a result that looks like:

?- model(Vars, Obj).
Vars = [0.0, 20.0]
Obj = 600.0
Yes (0.00s cpu)

This says that the optimal solution given the constraints is to build 20 chairs for $600 profit.

Okay, fine.  How does this help me with Enchanting?

Glad you asked.  Hopefully by now it’s clear that the allocation of enchanting components to enchantments is basically the same type of problem as the tables and chairs shown above.

I am going to work through a set of increasingly complex examples to illustrate the techniques.  For now, I’ve limited the set of enchantments we are dealing with to those under skill 130.  Basically, after 130 there’s a new set of materials to use, so I would formulate separate solution programs to each group of enchantments that shared a pool of resources.  In order to create the linear program, we need some information:

1. The current prices of enchantments on your server. I will use arbitrary, made-up numbers for these examples, your mileage will vary.  The Auctioneer add-on would be a great source of these prices now that enchantments can be scribed and sold. Otherwise, you’d have to monitor the chat channels to see what the going rates are.  Your gut feeling is probably good enough.
2. The amount of each component that you have on your character.
3. The price per component if sold in the auction house (for later).  Could definitely use Auctioneer for that as well.
4. The “recipe” for each enchantment in terms of what components it requires (I’ll provide that for these examples).

For the first example, we won’t need a program to calculate the answer.  Given one Strange Dust, you can enchant a bracer with Minor Health or a chestpiece with Minor Health.  Given that the bracer enchantment sells for 2 silver and the chest for 4 silver, which would you do?

Clearly, chest for 4 silver is true for any number of Strange Dust.  While trivial, this is the pattern that we’ll use to build on.  What else can we do with just Strange Dust?

enchantment	strange dust	value
Bracer – Minor Health	1	5s
Chest – Minor Health	1	10s
Bracer – Minor Stamina	3	10s
Bracer – Minor Strength	5	15s
Boots – Minor Stamina	8	30s

Creating this as a linear program yields the following code:

:- lib(eplex).

solve(Vars, Cost) :-
model(Vars, Obj),
eplex_solver_setup(max(Obj)),
eplex_solve(Cost).

model(Vars, Obj):-
Vars = [E1, E2, E3, E4, E5],
E1 $>= 0, E2 $>= 0, E3 $>= 0, E4 $>= 0, E5 $>= 0,
E1 + E2 + 3*E3 + 5*E4 + 8*E5 $=< 100,
Obj = 5*E1 + 10*E2 + 10*E3 + 20*E4 + 30*E5.

Which results, somewhat intuitively given the way the prices scale with respect to number of dusts used, in the following optimal solution:

enchantment	strange dust	quantity
Bracer – Minor Health	1	0
Chest – Minor Health	1	100
Bracer – Minor Stamina	3	0
Bracer – Minor Strength	5	0
Boots – Minor Stamina	8	0

More advanced uses of linear programming will actually allow the user to determine at what prices and quantities the optimal point will shift.

So far, this is not terribly exciting (sorry!).  So let’s increase the complexity by adding in the next component used in low-level enchanting — Lesser Magic Essence.

The following enchantments can be created by using a combination of Strange Dust and Lesser Magic Essence:

enchantment	strange dust	lesser magic essence	value
Bracer – Minor Health	1	0	5s
Bracer – Minor Defense	1	1	5s
Chest – Minor Health	1	0	10s
Chest – Minor Absorption	2	1	20s
Chest – Minor Mana	0	1	15s
Cloak – Minor Resistance	1	2	30s
Bracer – Minor Stamina	3	0	20s
Chest – Lesser Health	2	2	30s
Bracer – Minor Spirit	0	2	5s
Bracer – Minor Strength	5	0	25s
Boots – Minor Stamina	8	0	30s

Putting this into a linear program (by now, it should become apparent that linear programs can frequently be generated by a scripting language from a matrix of data) and assuming we have 15 Strange Dust and 10 Lesser Magic Essences yields:

:- lib(eplex).

model(Vars, Obj):-
Vars = [E1, E2, E3, E4, E5, E6, E7, E8, E9, E10, E11],
integers(Vars),
E1 $>= 0, E2 $>= 0, E3 $>= 0, E4 $>= 0, E5 $>= 0,
E6 $>= 0, E7 $>= 0, E8 $>= 0, E9 $>= 0, E10 $>= 0, E11 $>=0,
E1 + E2 + E3 + 2*E4 + 0*E5 + E6 + 3*E7 + 2*E8 + 0*E9 + 5*E10 + 8*E11 $=< 15,
0*E1 + E2 + 0*E3 + E4 + E5 + 2*E6 + 0*E7 + 2*E8 + 2*E9 + 0*E10 + 0*E11 $=< 10,
optimize(max(5*E1 + 5*E2 + 10*E3 + 20*E4 + 15*E5 + 30*E6 + 20*E7 + 30*E8 + 5*E9 + 25*E10 + 30*E11), Obj).

and running that through ECLiPSe yields the following results:

?- model(Vars, Obj).
Vars = [0, 0, 15, 0, 10, 0, 0, 0, 0, 0, 0]
Obj = 300.0
Yes (0.00s cpu)

which basically says that for our 15 Strange Dust and 10 LMEs, we should make 15 Chest Minor Health enchantments and 10 Chest Minor Mana enchantments for 300 silver in profit.

Assuming there is a price change that makes Cloak – Minor Resistance and Chest – Lesser Health more attractive (at 50s each) would result in the following new objective function:

optimize(max(5*E1 + 5*E2 + 10*E3 + 20*E4 + 15*E5 + 50*E6 + 20*E7 + 50*E8 + 5*E9 + 25*E10 + 30*E11), Obj).

The new result of running the linear program would be:

?- model(Vars, Obj).
Vars = [0, 0, 10, 0, 0, 5, 0, 0, 0, 0, 0]
Obj = 350.0
Yes (0.00s cpu)

This suggests that it’s now more profitable (by 50s) to make 10 Chest – Minor Health and 5 Cloak – Minor Resistance enchantments.

Through skill level 130 there are 28 possible enchantments which are made up of 5 components.  However, the fact that the components can be sold in the auction house as components instead of being used for enchantment should be taken into account by the model.  Fortunately, with linear programming, this is a relatively straightforward change.  For each constraint, we need to account not only for that component’s use in the enchantments but also for the potential for that component to be sold independently.  We add the profit from selling that component to the objective function as well.  Therefore, we introduce two new variables: C1, which represents Strange Dust sold as s component, and C2, which is the Lesser Magic Essence.  We will arbitrarily assign 1s to the per-component cost of Strange Dust and 2s to the LME, resulting in the following program:

:- lib(eplex).

model(Vars, Obj):-
Vars = [E1, E2, E3, E4, E5, E6, E7, E8, E9, E10, E11, C1, C2],
integers(Vars),
E1 $>= 0, E2 $>= 0, E3 $>= 0, E4 $>= 0, E5 $>= 0,
E6 $>= 0, E7 $>= 0, E8 $>= 0, E9 $>= 0, E10 $>= 0, E11 $>=0, C1 $>= 0, C2 $>= 0,
E1 + E2 + E3 + 2*E4 + 0*E5 + E6 + 3*E7 + 2*E8 + 0*E9 + 5*E10 + 8*E11 + C1 $=< 15,
0*E1 + E2 + 0*E3 + E4 + E5 + 2*E6 + 0*E7 + 2*E8 + 2*E9 + 0*E10 + 0*E11 + C2 $=< 10,
optimize(max(5*E1 + 5*E2 + 10*E3 + 20*E4 + 15*E5 + 50*E6 + 20*E7 + 50*E8 + 5*E9 + 25*E10 + 30*E11 + 1*C1 + 2*C2), Obj).

The initial results are unchanged — at 1s for the dust and 2s for the LME, it’s still better to do the enchantments.  However, if we were to raise the profit from dust and LME to 20s and 30s, respectively, it would result in the following objective function:

optimize(max(5*E1 + 5*E2 + 10*E3 + 20*E4 + 15*E5 + 50*E6 + 20*E7 + 50*E8 + 5*E9 + 25*E10 + 30*E11 + 20*C1 + 30*C2), Obj).

?- model(Vars, Obj).
Vars = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 15, 10]
Obj = 600.0
Yes (0.01s cpu)

In this scenario, the optimal profit comes from just selling the dust and LME at the auction house and results in a hefty 600s profit.

Conclusion

Optimization, and particularly linear programming, are powerful tools for helping businesses (and gamers!) make informed decisions and analyze the impacts of different scenarios.  In the business world, these techniques are normally studied under the umbrella of Operations Research, along with simulation and network programming techniques.

Hopefully this has been a fun way to learn a little bit about optimization technologies!