Clients want to ensure that during the development phase of an AX implementation methodologies stay efficient.  Whether that means making the right business decision or solving the problem the right way through X++, efficiency is always a key concern.  Recently, we ran into a situation at a client where a business flow required that cases of inventory be picked in an efficient manner to be loaded onto a truck; taking into consideration a desired goal and multiple inventory locations, each location with a potential different quantity.  This is a common and well documented problem called the subset sum problem.  In subset sum, you attempt to reach a certain sum (goal) given a list of values.

The decision was easy: implement a subset sum algorithm into AX that would allow for the inventory to be loaded from different locations, attempting to get as close as possible to the eventual goal (in this case, a sales order).  The problem: how do you implement a subset sum algorithm in AX, and especially when in a time crunch?

We first looked into implementing Microsoft Solver Foundation 3.1, and quickly found how powerful the tool was for implementing common computer science problems (such as the traveling salesman problem and the subset sum problem).  While powerful, MSF 3.1 ended up being a bit of overkill for what we needed, which was just an efficient implementation of subset sum in X++.

Computational time is a constant concern when developing high-usage functionality, so that needed to be taken into consideration during development.  The eventual decision was to design a randomization algorithm that could quickly iterate through all potential inventory locations and try to combine groups of inventory to meet the sales order quantity (the goal, in this case).  The base algorithm is below, with comments to explain what is happening throughout the code.  This job is very easy to customize and allows for high-volume testing of the algorithm if need-be.

static void subsetsum_randomization(Args _args)

{

boolean testMode = true;

// our goal

int goal = 62;

// <tolerance> – the percentage at which we say a goal needs to be me

// i.e. a tolerance is .1, if a goal is 100 and our sum is at 90, the goal will be “reached”

// introduce stricter tolerance levels to increase precision

// <tcount> – the counter to increase tolerance level

// i.e. at tcount iterations, the tolerance level will decrease by 1%

// this value is set for testing purposes later on as the original container length times ten

real tolerance = 0.00;

int tcount    = 0;

int tLimit;

// iteration counter to avoid overflow

counter icount = 0;

// start and end times for algorithm speed

utcDateTime utcStart;

utcDateTime utcEnd;

// instantiate set & length

container lpncon;

int origLen;

// the lists to manipulate

container used, unused;

// for loop iterator)

int i;

// value and index for easy access

int leftVal, rightVal, lefti, righti;

// running sum of the used list

int usedSum = 0;

// initialize randomization for con building

Random Random = new Random();

int coin;

// TEST PURPOSES ONLY

if (!testMode)

{

lpncon = [ 50, 61 , 64, 59, 67 , 81, 45, 63 ];

}

while ( conLen(lpncon) < 100 && testMode)

{

lpncon += [( 15 + Random.nextInt() mod 30)];

}

// set original length & tolerance iterator

origLen = conLen(lpncon);

tlimit  = origLen * 10;

// set start time

utcStart = DateTimeUtil::utcNow();

// build used & unused lists

for (i = 0; i < origLen; i++)

{

if (conPeek (lpncon, i) == goal)

{

used = [conPeek(lpncon, i)];

usedSum = conPeek(lpncon, i);

info( “Result found prematurely.”);

utcEnd = DateTimeUtil::utcNow();

info( strFmt(‘Optimization took %1 seconds with a tolerance of %2.’ , DateTimeUtil::getDifference(utcEnd, utcStart), tolerance));

info( strFmt(‘Goal: %1 | Optimization: %2 | Result set: %3′ , goal, usedSum, con2Str(used)));

return;

}

// get index & val of next int in orig list

lefti = 1 + (Random.nextInt() mod conLen(lpncon));

leftVal = conPeek(lpncon, lefti);

// reset coin

coin = ( 1 + Random.nextInt() mod 100);

// determine which list to add to

if ((coin > 50 && usedSum < goal) || conLen(used) == 0 )

{

// add to used list

used += [leftVal];

// update sum

usedSum += leftVal;

}

// otherwise, add to unused

else

{

unused += [leftVal];

}

// delete from orig list

lpncon = conDel(lpncon, lefti, 1);

}

// now we have 2 lists, one that’s kind of close, one that’s extra numbers.  try to optimize within tolerance acceptance

while ((usedSum < (goal – (goal * tolerance))) || (usedSum > (goal + (goal * tolerance))) && icount < 100000)

{

// tolerance handler

if (tcount == tLimit)

{

tolerance += 0.01;

tcount    = 0;

}

// if sum is too big

if (usedSum > (goal + (goal * tolerance)))

{

lefti    = 1 + Random.nextInt() mod conLen(used);

leftVal  = conPeek(used, lefti);

used    = conDel(used, lefti, 1);

usedSum -= leftVal;

unused  += [leftVal];

}

// if sum is too small

else if (usedSum < (goal – (goal * tolerance)))

{

righti   = 1 + Random.nextInt() mod conLen(unused);

rightVal = conPeek(unused, righti);

used    += [rightVal];

usedSum += rightVal;

unused  = conDel(unused, righti, 1);

}

icount++;

tcount++;

}

utcEnd = DateTimeUtil::utcNow();

info( strFmt(‘Optimization took %1 seconds with a tolerance of %2.’ , DateTimeUtil::getDifference(utcEnd, utcStart), tolerance));

info( strFmt(‘Goal: %1 | Optimization: %2 | Result set: %3′ , goal, usedSum, con2Str(used)));

}

Essentially, the algorithm randomly builds up two lists to begin with: one that imprecisely attempts to reach our goal (but not going over), and the other is the remainder inventory quantities.  Then, the left hand list (our attempted goal) has elements randomly removed and ones from the right inserted.  If we haven’t reached the goal with tolerance in mind, we randomly remove a left element and insert it into the right container.  In a speedy manner, a list is built and the result printed out in an infolog.  That result contains our goal, our closest match to the goal, the list of quantities required to reach our goal, the eventual allowed tolerance, and the computational time required.

The randomization algorithm may seem inefficient because we are randomly grabbing elements from a container to try to reach our goal.  It’s actually an extremely efficient solution computationally, as removing and reinserting values into containers is not taxing on a system at all.  This algorithm can run over thousands of iterations before reaching 1 second in operation time, so it’s a great solution for clients worried about efficiency and keeping AX fast.  In the end, this implementation of subset sum did exactly what we needed it to in just a few lines of code and using the basic container manipulation that X++ provides us.