How to sort expressions/compare two expressions

[Bob3D2000]

Hello,

TLDR: how do I make a list of Expressions that is sorted by the values to which each Expression would evaluate?

Full question:

I'm using Optano with the Gurobi solver in C# (using VS2019) to minimise the sum of the lowest 5% of a set of weighted values (the weights being the variables added to the model).

To the find the lowest 5% I need to sort the values calculated by the model. One way or another, I need to be able to compare two values, but I can't work out how. If I have List<Expression> the Sort() method doesn't work for obvious reasons.

Instead, because it's more efficient and is much simpler code than a sorting algorithm (which I have also tried to no avail, using selection sorting), I have a little foreach that finds the correct position in a list into which to insert the new value so that I end up with a sorted list.

Expression[] expressionPairForMin = new Expression[2];
expressionPairForMin[0] = weightedValueTemp; //The new Expression I want to insert into the sorted list.
foreach (Expression weightedValue in allWeightedValues)
{
    expressionPairForMin[1] = weightedValue;
    //if (weightedValueTemp < weightedValue) { break; } //What I want to do, which doesn't work of course.
    if (Expression.Equals(Expression.Minimum(expressionPairForMin), weightedValueTemp)) { break; } //One of several ideas I've tried.
    insertPosition++;
}
portfolioWeightedReturns.Insert(insertPosition, weightedValueTemp);

The if I have there is trying to say: if the minimum of the two Expressions is the same as the first Expression, then the first Expression must be the smaller of the two.

Later, I take the sum (using Expression.Sum) of the first n values (which is what's returned as an Expression for the Objective).

My code works if I use Expression.Evaluate on the objective with hardcoded weights as input variables and use the double values more directly, but not when I run the solver. It just doesn't sort the list in that case, as the if never returns true and so weightedValueTemp is always inserted at the end of the list.

Regards.

[OPTANO Team]

Hi,

to rephrase it with my words:

1. run some optimization model
2. take the variable values and evaluate some expressions with them
3. order the expressions by the evaluation value and take n of them
   

you'd might review this code, I think that would be a match.

// See https://aka.ms/new-console-template for more information
using OPTANO.Modeling.Optimization;
using OPTANO.Modeling.Optimization.Configuration;

// all modeling config and scope just to have manuel variable names
var config = new Configuration();
config.NameHandling = NameHandlingStyle.Manual;

using (var scope = new ModelScope(config))
{

    // create two variables
    var x = new Variable("x", 0, 100, OPTANO.Modeling.Optimization.Enums.VariableType.Integer);
    var y = new Variable("y", 0, 100);


    // create some expressions (might be part of constraints if a solver is used)
    var myExpressions = new Expression[]
    {
        2 * x + y,
        0 * x + 100 * y,
        x * -1 - 15 * y
    };

    // this is the same format, a Solver.Solve().VariableValues would give
    var resultsFromSolver = new Dictionary<string, double>();
    resultsFromSolver.Add(x.Name, 100);
    resultsFromSolver.Add(y.Name, 10);


    // evaluate each expression with the variable values provided and return a tuple with expression and value, then order by value ascending
    var prioList = myExpressions.Select(e =>
        new { Expression = e, Value = e.Evaluate(resultsFromSolver) }).OrderBy(e => e.Value);

    // print the results
    foreach (var prioItem in prioList)
    {
        Console.WriteLine($"{prioItem.Expression}: {prioItem.Value}");
    }
}

Best

jp

[Bob3D2000]

Thank you very much for replying, JP, it's much appreciated.

I think the order is somewhat different though. The objective I'm trying to minimise itself depends on the order of items. I've used Excel to illustrate what I'm trying to do.

The Items are from a CSV file. Each row is a day. In this example there are 100 days (these are random numbers for the purposes of illustration). The Weights are the variables subject to constraints.

I take the sumproduct of each day's items and the weights, as shown in the formula. This gives me a list of values and I take the mean of the lowest five days. I need the solver to find the combination of weights that provide the minimum of this value.

This is easy in Excel because I can use PERCENTILE.INC(D3:D102,0.05) and take the sum of values less than the result divided by the count of values less than the result. Then I can use Excel solver with cell I7 as the Objective and set 'By Changing Variable Cells' to F2:H2. (I don't actually need cells G7:G106.)

In real use there could be hundreds of Items with corresponding weights (and thousands of days) and it needs to be automated, so Excel is no good, even though it works for small examples.

The difficulty I'm having then, is how to write an expression, or set of expressions, that includes the sorting of 'column D', or that otherwise finds the lowest n values (n is always x% of the number of days in the data).

I have spent many hours trying to figure this out. I really hope it's possible!

Regards,
Bob3D

[Bob3D2000]

Or another way to think about it is, "how to write an expression that represents the mean of the lowest N expressions in an unordered list?" Note also that, although not shown in my illustration earlier, this includes negative values.

[OPTANO Team]

Yap. Thanks for the update. The total number of expressions M is known as well as the number of lowest rows N going into the mean. right?

best

jp

[Bob3D2000]

That's right, yes.

Regards,

Bob3D

[OPTANO Team]

I think this works for your case. A few restrictions apply:

* The variables are not "secured" in both directs, this shall be changed if the objective is to maximize

* All SumProducts are expected to be non-negative. That might be fixed by an additional constraint

* There is a valid estimation about the largest SumProduct to be stored in BigM

Happy to answer questions, if something comes up.

Best

jp

            var config = new Configuration();

            config.NameHandling = NameHandlingStyle.Manual;

            // some numbers from your excel, each representing one row
            var debugValues = new double[]
                { 0.500942, 0.4832977, 0.4062116, 0.7408317, 0.719787, 0.15725, 0.201882, 0.224514, 0.234532, 0.239922 };


            // just an index range. might be replaced with the real base index of your rows
            var index = Range(0, debugValues.Length).ToList();
           
           
            // shall be bigger as the largest possible SumProduct Value.
            var BigM = 1d;

            // average of n=5
            var n = 5;

            using (var scope = new ModelScope(config))
            {

                var model = new Model("nth minimum");
               
                // true (1), if row is in smallest nth values
                var sumProductInN =
                    new VariableCollection<int>(model, index, "SumProductInN", (i) => $"AvgItem for Row {i}", variableTypeGenerator:(i) => VariableType.Binary);

                // variable representing the sumproduct of each row of your excel
                var sumproducts =
                    new VariableCollection<int>(model, index, "SumProducts", (i) => $"SumProduct for Row {i}");

                // the value of the nth largest number
                var floatingLimit = new Variable("floatingLimit");

                // the average, is a book keeper variable, might be replaced by expression directly
                var avg = new Variable("avg");

                // min my average
                model.AddObjective(new Objective(avg), "minimal avg");

                // calculate avg of all variables, that are smaller than the limit a.k.a. are the smallest n and just take their nth fractile
                model.AddConstraint(Expression.Sum(index.Select(i => sumProductInN[i] * sumproducts[i] / n)) == avg);

                // we want n numbers to be part of the average calculation. not more, not less
                model.AddConstraint(Expression.Sum(index.Select(i => sumProductInN[i])) == n);


                foreach (var i in index)
                {
                   
                    // replace with correct calculation of sumproducts (value1 * weight1 + value2 * weight2 ...)
                    model.AddConstraint(sumproducts[i] == debugValues[i]);

                    // find the limit, which is equal to the nth largest value
                    model.AddConstraint(floatingLimit + (1 - sumProductInN[i]) * BigM >= sumproducts[i]);

                }

                // solve, you might want to add package OPTANO.Modeling.Gurobi
                var solver = new GurobiSolver();
                solver.Solve(model);


                // print the average
                WriteLine($"{avg.Value}");

                foreach (var i in index)
                {
                    // Print each variables-is-in-the-average
                    WriteLine($"{i}: {sumproducts[i].Value} {sumProductInN[i].Value}");
                }

            }

It prints on my console

ptimal solution found (tolerance 0.00e+00)
Best objective 2.114800000000e-01, best bound 2.114800000000e-01, gap 0.0000%

User-callback calls 208, time in user-callback 0.00 sec

0,21162000000000003
0: 0,500942 0
1: 0,4832977 0
2: 0,4062116 0
3: 0,7408317 0
4: 0,719787 0
5: 0,15725 1
6: 0,201882 1
7: 0,224514 1
8: 0,234532 1
9: 0,239922 1

[Bob3D2000]

Thanks, JP.

I've spent a few hours trying to make it work with the sumproduct calculation but without success. I've replaced 'debugValues' with a list of expressions called 'sumProductItems' that looks like the screenshot below. The numbers are from the CSV file and 'Item_1', etc. are the names of the weight variables I need to find the values for, i.e. the values that give the lowest possible mean of the lowest n sumproducts (equivalent to F2:H2 in my Excel example).

(I put a break in and took the screenshot after it had added three days. There are thousands of days and potentially hundreds of items.)

No matter what a do - and I've tried a lot of things - the solver just returns 0 for the average and 0 for all the solution weights variables. I'm going a bit potty!

[OPTANO Team]

Hi,

The Expressions look ok, but keep in mind, they need to become constraints by comparing 2 expressions (look at my code for AddConstraint). I have introduced sumproducts for this case, just make sure, that sumproduct[i] == ##the first of your expressions## and so on. After all, make sure they are added to the model.

Additionally, Item_i need to be pushed to some value different from 0. If they are "free" variables, the solver might just set them to 0 and that would be the valid optimal solution.

When you add the following lines to your code, just before you run solver.Solve(...)

               foreach (var constraint in model.Constraints)
               {
                    Console.WriteLine(constraint);
               }

It will print the model (you can do so in your debugging session as well). Double check, that all constraints are set.

best

jp

[Bob3D2000]

I've got it working now. I am daft sometimes - I forgot to put in my 'weights must sum to 1' constraint! Also, it seems that to deal with negative sumproducts all I needed to do was set the lower bounds on the sumproduct and floatingLimit variables to -1 instead of the default 0 and it gives the right answer.

It took me a bit of time to understand what your code does. It's quite clever. You have to think a bit differently but this and your help is helping me understand how Optano works.

The only thing left is something I forgot about and forget to mention, which is that I need to minimise the magnitude of the average of the lowest n sumproducts. This is slightly awkward as the nature of the input data means the average of the lowest in is always negative (essentially, positive ones are good days and negative ones are bad, so I need to find the average of the n worst days and minimise how bad that is).

I tried replacing avg in the objective with Expression.Absolute(avg) but now it minimise to 0 and gives incorrect weights. So I thought, okay, if I switch the sign on the sumproducts and minimise the average of the largest ones, that will give the right answer. But I can't work out how to do that. It might be that I haven't fully understood

model.AddConstraint(floatingLimit + (1 - sumProductIsInN[i]) * BigM >= sumProducts[i]);

well enough.

Regards,

Bob3D

[OPTANO Team]

Hi,

in linear optimization system, Absolute() is quite a different function as well. It creates a binary internally.

Regarding the magnitude:  Would a linear shift be an appropriate solution? Could the largest maginate be estimated upfront?

One can minimize a max of expressions. A simple way is https://docs.optano.com/modeling/current/api/OPTANO.Modeling.Optimization.Operators.Max.html

model.AddConstraint(floatingLimit + (1 - sumProductIsInN[i]) * BigM >= sumProducts[i]);

is a tricky expression. It pushes the the binary variable sumProductIsInN to 0, if sumProducts is larger than the floatingLimit. The floatingLimit will equal the nth largest number in the model.

If that's a commercial project, you might benefit from an or expert's help regarding modeling tweaks to save your time. Just an idea.

Best

jp

[Bob3D2000]

I wanted to say a quick thank you for all your help. It's very much appreciated.

I've decided to take a different tack and calculate it parametrically using the Gaussian density function and the standard deviation. This boils down the problem to a formula I can use for the objective function. It took me a little while to pin down all the right maths but everything works now.

Thanks again!

[OPTANO Team]

Hi,

sure. Moving as much logic as possible in the preprocessing phase is usually a quite good approach.

Thanks for your feedback, happy to hear you got it finally running.

Please recommend using optano modeling and this optano forum to your colleagues.

best

jp