Algorithm : hierachical problem. How do I approach this.

[kuda25]

Hi All.

I have been asked to develop code that works out all the possible structures a brokerage firm can take to maximise the charges it takes.

If we assume that there are N management levels and under each level there are k types of brokers. For each type of broker the commission charges are different and will depend on the volumes sold. There are no restrictions to number of certain type of agent that the firm direct manager can have.

Given the total volumes for the firm, work out all possible structures that the firm can organise it’s brokers.

To illustrate this.

Lets assume we have a firm with 2 manager levels and 2 agent types on the bought level. i.e. a single manager who can chose to have any number of combinations of the 2 agent types.

If he manages $100mn and lets say the minimum a single agent can manage is $10mn.
He could chose to have any combination as long as it adds up to $100mn. This could be
• 10 agent type 1 agents managing 10 mn each
• 5 agent type1 agents managing 20mn each
• a combination of agent 1 and agent type 2 managing various amounts.
• 10 agent type 2 managing 10m each.
There are a lot of possible combinations and this only gets more complex when you increase the possible number of levels.

Any ideas?

Worth pointing out that this should be done in VBA.

 

[SkipVought]

Hi,

What design approch or code do you currently have?

What results do you currently get?

Where are the problems?

Skip,
[sub]
Just traded in my old subtlety...
for a NUANCE![/sub]

 

[jges]

Is there a maximum amount an agent can handle?
In the example given, the manager can have from 1 - 10 agents, if there is a max amount we can pare that down a bit.

 

[MajP]

As described this sounds like a simple combinatorics problem, but clearly there is a lot of missing information you would have to describe. Probably could be done simply in Excel.

However, I believe that this is likely a linear program assignment model. My guess is you are looking to maximize or minimize some value based on some given constraints. Excel provides several add ins to solve linear and simple non linear programs. These problems are normally of the form

Maximize or Minimize some objective function
Subject to the following constraints

Right now the only constraint I see is that total managed must equal Total managed by firm. If you want a better answer try to answer the following;

1) What is the objective function? What thing/s do you want to maximize or minimize?
total number of agents?
total number managers?
different types of agents?

2) What are your constraints:
limit on types of agents?
limit on max/min amount managed by level
limit on max/min amount managed by agent
limits on number of levels
etc.

3) What are your data vectors?
commission charges by volume
salary by type of broker
etc.


This is a whole discipline of Operations Research that deals with these models.
However depending on the complexity of your model, you may want be able to
1) do a simple spread sheet model
2) Solve with an add-in like excel solver or Crystal Ball
3) Solve with a deterministic home grown combinatoric model using vb and just loopin the possibilities
4) Go to some bigger Linear/Non linear solver like GAMS


Bottom line you would need to provide a whole lot more information in order for anyone to guess what is needed.

 

[MajP]

did not see that this was the second part of the post. Appears some of the input vectors and constraints are in the spread sheet.

From what I see it looks pretty clear that this is linear optimization model. I also missed that you have the basis for the objective function:
Maximize Charges

Here is some very clear reading on the basic approach

http://markmail.org/download.xqy?id=kv3eemhevr6rrhdm&number=1

This is an interesting problem. The assignments to different levels of management, if that is unconstrained, may make this a very complex problem. But if that is constrained to N levels you may be able to iterate through N different optimization models.

A pure optimized model, may be beyond your tools, but you could probably come up with a good Heuristic. With this kind of model you may start with a proposed structure. Then through code replace a node (agent, manager) at a time and see you can improve on overall charges. If the model improves, and still meets your constraints then continue in that direction. If it gets worse go in a different direction.

I can show you an example in vb using that approach. It solves a "traveling salesman problem" of the shotest route connecting all state capitals. This is considered an NP-hard problem. The heuristic; however, gives a very close solution. Basically you start with a best guess route connecting all the cities. Then pick a city, break its connections and reconnect to 2 other cities. If it shortens the overall route then keep it else try a different city. You could probably code a similar type of solution.

However, depending on the constraints you may be able to simply loop all possible configurations.

 

[kuda25]

Thank you all for the feedback... Still working my way through it. A few new things to read up on, new to modelling.

@SkipVought. Still trying to work out what approach, not started on the code yet.
@Jges. There isn't a limit to how much an agent can handle.

@MajP could you please send me the travelling salesman example.

 

[MajP]

Like I said, this problem sounds very much as if it can be modeled and solved as a linear optimization model. I would first become very familar with your solver add-in that ships with excel. It is somewhat rudimentary, but you may be able to optimize some or all of your problem depending on the complexity.

http://courses.washington.edu/samcrs/LPsolver.pdf

I will dig up the TSP model, but basically it does what is called a 2-opt replacement solution. This is a pretty efficient heuristic that gives reasonable answers. Not sure if you will get much out of it, I do not think it will be to useful for your model. However, it is member of a class of "improving heuristic algorithms". In other words start with a possible solution and use different methods to change the solution. If you improve the overall solution continue making those types of changes.

So your choices are
1) Deterministic model. See if you can loop all the possibilities. If you have a limit of K manager levels, N type of agents, limit of M agents per level. You may be able to loop all possibilities. However, this may realistically be impossible.
The 50 state trip has 50! possibilities which even if it takes fraction of seconds for each iteration takes hundreds of cpu years to solve.
2) Linear Program. May be able to model all or part as a LP in Solver. May model part and then loop the model. I do not know enough of your problem, but it is possible that this is a very complex LP and too difficult to model
3) Improving algorithm heuristic. If you can not model as an LP then see if you can iteratively improve the solution. There is a whole family of algorithms to do this.


I have done a lot of optimization models both using software and home grown heuristics. And I would strongly advise before sitting down and doing any code that you spend a lot of time to formulate and document the problem on paper. I may be reading too much into this, but from your brief description this sounds like it could be computationally complex and an exact solution maybe beyond what you can code or get from your current software. If you can clearly articulate the problem: Objective function, constraints, decision variables, upper and lower bounds,input data we can help formulate a possible solution. If you just provide a bunch of code and spreadsheets, unlikely anyone can dig into it.