C# Simple Constrained Weighted Average Algorithm with/without Solver

Question

I'm at a loss as to why I can't get this seemingly simple problem solved using Microsoft Solver Foundation.

All I need is to modify the weights (numbers) of certain observations to ensure that no 1 observation's weight AS A PERCENTAGE exceeds 25%. This is for the purposes of later calculating a constrained weighted average with the results of this algorithm.

For example, given the 5 weights of { 45, 100, 33, 500, 28 }, I would expect the result of this algorithm to be { 45, 53, 33, 53, 28 }, where 2 of the numbers had to be reduced such that they're within the 25% threshold of the new total (212 = 45+53+33+53+28) while the others remained untouched. Note that even though initially, the 2nd weight of 100 was only 14% of the total (706), as a result of decreasing the 4th weight of 500, it subsequently pushed up the % of the other observations and therein lies the only challenge with this.

I tried to recreate this using Solver only for it to tell me that it is the solution is "Infeasible" and it just returns all 1s. Update: solution need not use Solver, any alternative is welcome so long as it is fast when dealing with a decent number of weights.

var solver = SolverContext.GetContext();
var model = solver.CreateModel();

var decisionList = new List<Decision>();
decisionList.Add(new Decision(Domain.IntegerRange(1, 45), "Dec1"));
decisionList.Add(new Decision(Domain.IntegerRange(1, 100), "Dec2"));
decisionList.Add(new Decision(Domain.IntegerRange(1, 33), "Dec3"));
decisionList.Add(new Decision(Domain.IntegerRange(1, 500), "Dec4"));
decisionList.Add(new Decision(Domain.IntegerRange(1, 28), "Dec5"));
model.AddDecisions(decisionList.ToArray());

int weightLimit = 25;
foreach (var decision in model.Decisions)
{
    model.AddConstraint(decision.Name + "weightLimit", 100 * (decision / Model.Sum(model.Decisions.ToArray())) <= weightLimit);
}
model.AddGoal("calcGoal", GoalKind.Maximize, Model.Sum(model.Decisions.ToArray()));

var solution = solver.Solve();
foreach (var decision in model.Decisions)
{
    Debug.Print(decision.GetDouble().ToString());
}
Debug.Print("Solution Quality: " + solution.Quality.ToString());

Any help with this would be very much appreciated, thanks in advance.

Answer 1

I ditched Solver b/c it didn't live up to its name imo (or I didn't live up to its standards :)). Below is where I landed. Because this function gets used many times and on large lists of input weights, efficiency and performance are key so this function attempts to do the least # of iterations possible (let me know if anyone has any suggested improvements though). The results get used for a weighted average so I use "AttributeWeightPair" to store the value (attribute) and its weight and the function below is what modifies the weights to be within the constraint when given a list of these AWPs. The function assumes that weightLimit is passed in as a %, e.g. 25% gets passed in as 25, not 0.25 --- ok I'll stop stating what'll be obvious from the code - so here it is:

    public static List<AttributeWeightPair<decimal>> WeightLimiter(List<AttributeWeightPair<decimal>> source, decimal weightLimit)
    {
        weightLimit /= 100; //convert to percentage

        var zeroWeights = source.Where(w => w.Weight == 0).ToList();
        var nonZeroWeights = source.Where(w => w.Weight > 0).ToList();

        if (nonZeroWeights.Count == 0)
            return source;

        //return equal weights if given infeasible constraint
        if ((1m / nonZeroWeights.Count()) > weightLimit)
        {
            nonZeroWeights.ForEach(w => w.Weight = 1);
            return nonZeroWeights.Concat(zeroWeights).ToList();
        }

        //return original list if weight-limiting is unnecessary
        if ((nonZeroWeights.Max(w => w.Weight) / nonZeroWeights.Sum(w => w.Weight)) <= weightLimit)
        {
            return source;
        }

        //sort (ascending) and store original weights
        nonZeroWeights = nonZeroWeights.OrderBy(w => w.Weight).ToList();
        var originalWeights = nonZeroWeights.Select(w => w.Weight).ToList();

        //set starting point and determine direction from there
        var initialSumWeights = nonZeroWeights.Sum(w => w.Weight);
        var initialLimit = weightLimit * initialSumWeights;
        var initialSuspects = nonZeroWeights.Where(w => w.Weight > initialLimit).ToList();
        var initialTarget = weightLimit * (initialSumWeights - (initialSuspects.Sum(w => w.Weight) - initialLimit * initialSuspects.Count()));
        var antepenultimateIndex = Math.Max(nonZeroWeights.FindLastIndex(w => w.Weight <= initialTarget), 1); //needs to be at least 1        
        for (int i = antepenultimateIndex; i < nonZeroWeights.Count(); i++)
        {
            nonZeroWeights[i].Weight = originalWeights[antepenultimateIndex - 1]; //set cap equal to the preceding weight
        }
        bool goingUp = (nonZeroWeights[antepenultimateIndex].Weight / nonZeroWeights.Sum(w => w.Weight)) > weightLimit ? false : true;

        //Procedure 1 - find the weight # at which a cap would result in a weight % just UNDER the weight limit
        int penultimateIndex = antepenultimateIndex;
        bool justUnderTarget = false;          
        while (!justUnderTarget)
        {
            for (int i = penultimateIndex; i < nonZeroWeights.Count(); i++)
            {
                nonZeroWeights[i].Weight = originalWeights[penultimateIndex - 1]; //set cap equal to the preceding weight
            }

            var currentMaxPcntWeight = nonZeroWeights[penultimateIndex].Weight / nonZeroWeights.Sum(w => w.Weight);
            if (currentMaxPcntWeight == weightLimit) 
            {
                return nonZeroWeights.Concat(zeroWeights).ToList();
            }
            else if (goingUp && currentMaxPcntWeight < weightLimit)
            {
                nonZeroWeights[penultimateIndex].Weight = originalWeights[penultimateIndex]; //reset
                if (penultimateIndex < nonZeroWeights.Count() - 1)
                    penultimateIndex++; //move up
                else break;
            }
            else if (!goingUp && currentMaxPcntWeight > weightLimit)
            {
                if (penultimateIndex > 1)
                    penultimateIndex--; //move down
                else break;
            }
            else
            {
                justUnderTarget = true;
            }
        }

        if (goingUp) //then need to back up a step
        {
            penultimateIndex = (penultimateIndex > 1 ? penultimateIndex - 1 : 1);
            for (int i = penultimateIndex; i < nonZeroWeights.Count(); i++)
            {
                nonZeroWeights[i].Weight = originalWeights[penultimateIndex - 1];
            }
        }

        //Procedure 2 - increment the modified weights (subject to a cap equal to their original values) until the weight limit is hit (allowing a very slight overage for the last term in some cases)
        int ultimateIndex = penultimateIndex;
        var sumWeights = nonZeroWeights.Sum(w => w.Weight); //use this counter instead of summing every time for condition check within loop
        bool justOverTarget = false;
        while (!justOverTarget)
        {
            for (int i = ultimateIndex; i < nonZeroWeights.Count(); i++)
            {
                if (nonZeroWeights[i].Weight + 1 > originalWeights[i])
                {
                    if (ultimateIndex < nonZeroWeights.Count() - 1)
                        ultimateIndex++;
                    else justOverTarget = true;
                }
                else
                {
                    nonZeroWeights[i].Weight++;
                    sumWeights++;
                }
            }

            if ((nonZeroWeights.Last().Weight / sumWeights) >= weightLimit)
            {
                justOverTarget = true;
            }
        }

        return nonZeroWeights.Concat(zeroWeights).ToList();
    }

    public class AttributeWeightPair<T>
    {
        public T Attribute { get; set; }
        public decimal? Weight { get; set; }
        public AttributeWeightPair(T attribute, decimal? count)
        {
            this.Attribute = attribute;
            this.Weight = count;
        }
    }