More complicated objective function?

[joshrickert]

@bchevalier asked in my other issue thread if I had feedback on using this module. Making a new ticket just to keep things clean.

Stable so far, but then I discovered my use case is a bit beyond the scope of this library. I am not even sure if this is possible using the simplex method (or whatever algorithm you are using), but I thought I would at least bring it up.

Essentially, I discovered that my particular application required a solution near the center of the solution set. In a perfect scenario, I could specify an ideal ratio between two of my variables, and then have the solver help me find the closest possible solution to that ratio. Reorganized as a minimization objective, my scenario looked like this: MIN( ABS( variableA / variableB - optimalRatio ) ). I could also reorganize a bit to get that ABS out of there, but I wouldn't be sure where to go from there.

Is there any way to accomplish this with this library? I did notice the ReformatLP method that seems to give some advanced functionality, but I haven't dug into it.

[bchevalier]

The issue is that your problem is not linear if you divide two variables (i.e variableA / variableB is forbidden). But if you want to try to get close to an ideal ratio you could formulate your problem the following way:

variableA = ratio * variableB where ratio is your ideal ratio.

But this solution might not be feasible. If you want to make sure to obtain a feasible solution you could do as follow: minimize error subject to variableA - ratio * variableB <= error and variableA - ratio * variableB >= -error where error is a variable.

By solving this you should find the feasible solution that puts the ratio between A and B as close as possible to the ideal ratio.

[JWally]

I'm not sure if this is a dead end, or if you can feng sui it some more into working for you, but one of the problems I have in my test suite, I force a ratio between 2 things like this:

{
    "name": "Berlin Air Lift Ratio Problem",
    "optimize": "capacity",
    "opType": "max",
    "constraints": {
        "plane": {
            "max": 44
        },
        "person": {
            "max": 512
        },
        "cost": {
            "max": 300
        },
        "fake": {
            "equal": 0
        }
    },
    "variables": {
        "brit": {
            "capacity": 20000,
            "plane": 1,
            "person": 8,
            "cost": 5,
            "fake": -5
        },
        "yank": {
            "capacity": 30000,
            "plane": 1,
            "person": 16,
            "cost": 9,
            "fake": 1
        }
    },
    "ints": {
      "brit": 1,
      "yank": 1
    }}

By giving the Americans a fake value of 1, and the British a fake value of -5, and setting a constraint that fake === 0; this locks in your ratio of say 5:1. Not the exact answer, but hopefully something to start with. I'll think some on it.

[JWally]

It looks like it might be doable; I'm just trying to wrap my head around exactly how: If you start like how I have set up above, and define the ratio in the variable with fake attributes, and set the objective function to Minimize the Absolute Value of fake, you win.

http://www.ms.unimelb.edu.au/~moshe/620-362/Lecture_Notes/lp_tricks.pdf http://lpsolve.sourceforge.net/5.1/absolute.htm

and

www.ohio.edu/people/melkonia/math3200/regression.doc

@joshrickert if you do piece it together, please share! I'm curious now.

[joshrickert]

Wow, thanks so much for all of your research on this. From what I understand of the test cases supplied with #20, I could use my current constraints as high-weighted constraints and then use @JWally's technique for forcing a ratio with a low-weighted constraint. Or is it the other way around, where lower-weighted constraints get a stronger priority? I'm also curious what would happen if I use weights with a large differential, like assigning 1000 to one constraint and 1 to the other.

I should have time to give it a shot and report back.

[bchevalier]

Higher weight means that not satisfying the constraint will be more penalizing. That does not mean that the constraint with the higher weight will be satisfied. As in the example you gave, assigning 1000 to one constraint and 1 to the other does not imply the constraint with a weight of 1000 will be satisfied. I guess you have to test to see if it satisfies you.

Another system I am thinking of, is adding priorities to constraints (by default the priority would be maximum), so you could specify what constraints have to be satisfied in priority. In your example you might want to assign a high priority to the constraint you deem important, rather than giving it a high weight of 1000.

[bchevalier]

Hey @joshrickert, I was wondering if we could consider this issue resolved? Also, quick survey, were you able to use this solver for your use case?

[JWally]

Think I figured this out, but its ugly.

Say you're trying to figure out this problem where you want your ratio of Brit to Yank to be as close to 1.5 as possible while adhering to the constraints.

{
    "optimize": "ABS((brit / yank) - 1.5)",
    "opType": "max",
    "constraints": {
        "plane": {"max": 44},
        "person": {"max": 512},
        "cost": {"max": 300000},
        "yank": {"min": 16},
        "brit": {"min": 25}
    },
    "variables": {
        "brit": {
            "plane": 1,
            "person": 8,
            "cost": 5000,
            "brit": 1
        },
        "yank": {
            "plane": 1,
            "person": 16,
            "cost": 9000,
            "yank": 1
        }
    },
};

To make this make more sense, I'm moving this out of JSON format and into a "mathier" format:

minimize:
abs(1 brit / 1 yank) - 1.5;
s.t.
planes: 1 brit 1 yank <= 44;
people: 8 brit 16 yank <= 512;
cost: 5000 brit 9000 yank <= 300000;
US_Planes: 1 yank >= 16;
 UK_Planes: 1 brit >= 25;

Step 1 is to ignore the absolute value (x) - 1.5 portion until later. Step 2 is to leave the numerator as the objective function Step 3 is to move everything from the RHS to the LHS as a new "fake" variable Step 4 is to move the denominator to the constraints portion of the LP where it = 1

So the above (ignoring the abs portion for now) becomes:

minimize:
1 brit;
s.t.
planes: 1 brit 1 yank -44 fake <= 0;
people: 8 brit 16 yank - 512 fake <= 0;
cost: 5000 brit 9000 yank -300000 fake <= 0;
US_Planes: -1 yank + 16 fake >= 0;
UK_Planes: -1 brit + 25 fake >= 0;
denominator: 1 yank = 1

to add back in the abs portion (it gets ugly here to accommodate for the JSON formatting) do this:

1. Whatever ratio you're trying to hit, subtract it from your current objective function
2. Add a new constraint to the model that is the same as the objective function but must be greater than 0.

The model now becomes this:

1 brit - 1.5;
s.t.
planes: 1 brit 1 yank -44 fake <= 0;
people: 8 brit 16 yank - 512 fake <= 0;
cost: 5000 brit 9000 yank -300000 fake <= 0;
US_Planes: -1 yank + 16 fake >= 0;
UK_Planes: -1 brit + 25 fake >= 0;
denominator: 1 yank = 1;
abs_objective: 1 brit - 1.5 >= 0;

Which becomes the following JSON model:

{ opType: 'min',
  optimize: '_obj',
  constraints: 
   { planes: { max: 0 },
     people: { max: 0 },
     cost: { max: 0 },
     us_planes: { max: 0 },
     uk_planes: { max: 0 },
     denominator: { equal: 1 },
     fixed: { equal: 1 },
     abs_obj: {min: 0}},
  variables: 
   { brit: { _obj: 1, planes: 1, people: 8, cost: 5000, uk_planes: -1, abs_obj: 1 },
     fixed: { _obj: -1.5, fixed: 1, abs_obj: -1.5 },
     fake: { planes: -44, people: -512, cost: -300000, us_planes: 16, uk_planes: 25 },
     yank: { planes: 1, people: 16, cost: 9000, us_planes: -1, denominator: 1 } } }

which yields the following:

{ feasible: true,   result: 0,   fake: 0.05681818,   yank: 1,   fixed: 1,   brit: 1.5 }

To get your optimal values, divide everything in your solution set by the fake variable:

{"yank":17.600000563200016,"brit":26.400000844800026}

Whats interesting is if you set the ratio at 2, you get this:

{ feasible: false,   result: 0,   fake: 0.07142857,   yank: 1.14285714,   fixed: 1,   brit: 2 } 

Which is in-feasible, but; the results it gives after division are valid:

{brit: 28, yank: 16}

which gives a ratio of 1.75.

@bchevalier does this solution make sense? Does it look correct?

Here's where I got the idea from: http://web.mit.edu/lpsolve/doc/

[bchevalier]

I think we actually gave @joshrickert a way to solve his issue. The problem you suggest derived from the Berlin airlift problem can be formulated as follow using the trick in my first comment of this issue:

        "optimize": "errorRatio",
        "opType": "min",
        "constraints": {
            "plane": {"max": 44},
            "person": {"max": 512},
            "cost": {"max": 300000},
            "yankees": {"min": 16},
            "brits": {"min": 25},
            "ratioMin": {"min": 0},
            "ratioMax": {"max": 0}
        },
        "variables": {
            "brit": {
                "plane": 1,
                "person": 8,
                "cost": 5000,
                "brits": 1,
                "ratioMin": 1,
                "ratioMax": 1
            },
            "yank": {
                "plane": 1,
                "person": 16,
                "cost": 9000,
                "yankees": 1,
                "ratioMin": -2,
                "ratioMax": -2
            },
            "error": {
                "errorRatio": 1,
                "ratioMin": 1,
                "ratioMax": -1
            }
        }

which returns the following result:

 { constraints: 5,
     variables: 3,
     evaluation: 4,
     time: 0.014545894,
     iter: undefined,
     solutionSet: { error: 4, brit: 28, yank: 16 },
     feasible: true },

Just like using your method we get the result {brit: 28, yank: 16 } but no extra work is required.

I think we can close this issue.

[JWally]

Agree, I'll close it.

Sent from my iPhone

On Dec 9, 2015, at 12:47 AM, Brice notifications@github.com wrote:

I think we actually gave @joshrickert a way to solve his issue. The problem you suggest derived from the Berlin airlift problem can be formulated as follow using the trick in my first comment of this issue:

    "optimize": "errorRatio",
    "opType": "min",
    "constraints": {
        "plane": {"max": 44},
        "person": {"max": 512},
        "cost": {"max": 300000},
        "yankees": {"min": 16},
        "brits": {"min": 25},
        "ratioMin": {"min": 0},
        "ratioMax": {"max": 0}
    },
    "variables": {
        "brit": {
            "plane": 1,
            "person": 8,
            "cost": 5000,
            "brits": 1,
            "ratioMin": 1,
            "ratioMax": 1
        },
        "yank": {
            "plane": 1,
            "person": 16,
            "cost": 9000,
            "yankees": 1,
            "ratioMin": -2,
            "ratioMax": -2
        },
        "error": {
            "errorRatio": 1,
            "ratioMin": 1,
            "ratioMax": -1
        }
    }

which returns the following result:

{ constraints: 5, variables: 3, evaluation: 4, time: 0.014545894, iter: undefined, solutionSet: { error: 4, brit: 28, yank: 16 }, feasible: true }, Just like using your method we get the result {brit: 28, yank: 16 } but no extra work is required.

I think we can close this issue.

— Reply to this email directly or view it on GitHub.

[joshrickert]

I definitely appreciate all your help and hard work creating a solution for this. I've been working to get it implemented in my application since yesterday. Sorry for letting the issue on your tracker get a bit stale.

I do think the solutions you've presented should work, so yes, it's fine to close this. I'll let you know how it goes.

[joshrickert]

Got really close, but still don't have it working. The problem is that my use case involves something of a pivot from how the Berlin airlift problem is set up. Here's what my situation looks like:

{
    "optimize": "ABS((propertyA / propertyB - 1.5))",
    "opType": "min",
    "constraints": {
        "propertyA": {"min": 100, "max": 300 },
        "propertyB": {"min": 150, "max": 350 },
        "propertyC": {"max": 200 },
    },
    "variables": {
        "item1": {
            "quantity": 1,
            "propertyA": 65,
            "propertyB": 25,
            "propertyC": 20
        },
        "item2": {
            "quantity": 1,
            "propertyA": 20,
            "propertyB": 50,
            "propertyC": 15
        },
        /* etc... the list continues. */
    }
}

The solutions you discussed will work great if I need to force a ratio between item1 and item2, but I haven't figured out a way to apply that to properties of those items.

I think I am somewhat guilty of presenting an XY Problem, however. While the solution above would be the most ideal, there might be some satisfactory alternatives.

Basically, I have been trying to find a solution where are all of the items are relatively balanced with each other and located near the midpoint of the propertyA and propertyB ranges. If I can accomplish that, optimizing for the ratio is just icing on the cake.

I have thought of a couple ways to do this.

First, I could run the solver.Solve() method multiple times, perhaps minimizing and then maximizing the quantity property. Then I could take the mean of those values and see if it works. But there aren't really any guarantees that the midpoint lies inside the feasible region, even if the vertices do.

Alternatively, is there a way to output all of the vertices the solver steps over while it's working? Perhaps I could just look at a big array of vertices and manually select the best one. I was somewhat inspired by the solver.MultiObjective() writeup you recently added to the documentation.

[bchevalier]

Ah, interesting (thanks for the XY Problem explanation, it was insightful). Indeed, I can propose this solution to your problem:

"constraints": {
            "propertyA": { "equal": 200, "weight": 1 },
            "propertyB": { "equal": 250, "weight": 1 },
            "propertyC": { "max": 200 }
        },
        "variables": {
            "item1": {
                "propertyA": 65,
                "propertyB": 25,
                "propertyC": 20
            },
            "item2": {
                "propertyA": 20,
                "propertyB": 50,
                "propertyC": 15
            }
        }

I think your problem will be best solved by a QP solver (a functionality I intend to implement some time next year). If you were to use a QP solver you might want to reformulate your objective function as follow: min (propertyA - 200)^2 + (propertyA - 250)^2

Alternatively, is there a way to output all of the vertices the solver steps over while it's working?

No, but it could be added. Are you sure it would be interesting to you?

[JWally]

here's a hacked together function to go through the steps that I did above. Not sure if this is what you're interested in though:

function fixit(model, numerator, denominator, target){

    // Set up our new model
    var new_model = {
        "opType": "min",
        "optimize": "obj",
        "constraints": {
            "abs_obj": {"min": 0},
            "denom": {"equal": 1},
            "fixed": {"equal": 1}
        },
        "variables": {
            "fake": {},
            "fixed": {
                "fixed": 1,
                "obj": -1 * target,
                "abs_obj": -1 * target
            }
        }
    }

    // get arrays of names
    var vars = Object.keys(model.variables),
        cstr = Object.keys(model.constraints);

    // Create a holding spot for the variables
    for(var x in vars){
        new_model.variables[vars[x]] = {};
    }

    // Build out our constraints...
    // And load up our fake variable
    for(x in cstr){
        for(var y in model.constraints[cstr[x]]){
            // For the Constraints
            new_model.constraints[cstr[x] + "_" + y] = {};
            new_model.constraints[cstr[x] + "_" + y][y] = 0;

            // For the Faker
            new_model.variables.fake[cstr[x] + "_" + y] = 
                model.constraints[cstr[x]][y] * -1;
        }
    }

    // Go over the variables
    for(x in model.variables){
        // Run over the attributes
        for(y in model.variables[x]){
            // Check to see if there's a constraint on it...
            if(model.constraints[y]){
                // Go over the maxs and mins
                for(var z in model.constraints[y]){
                    // assign the new attribute
                    new_model.variables[x][y + "_" + z] = model.variables[x][y];

                    // But wait! There's more!
                    if(numerator === y){
                        new_model.variables[x]["obj"] = model.variables[x][y];
                        new_model.variables[x]["abs_obj"] = model.variables[x][y];
                    }

                    if(denominator === y){
                        new_model.variables[x]["denom"] = model.variables[x][y];
                    }

                }
            }
        }
    }

    return new_model;
}

Where you would go:

var model = {
    "optimize": "meh",
    "opType": "min",
    "constraints": {
        "propertyA": {"min": 100, "max": 300 },
        "propertyB": {"min": 150, "max": 350 },
        "propertyC": {"max": 200 },
    },
    "variables": {
        "item1": {
            "quantity": 1,
            "propertyA": 65,
            "propertyB": 25,
            "propertyC": 20
        },
        "item2": {
            "quantity": 1,
            "propertyA": 20,
            "propertyB": 50,
            "propertyC": 15
        }
    }
}

var a = fixit(model, "propertyA", "propertyB", 1.5);
a = solver.Solve(a);
console.log(a);

which returns this:

{feasible: true, item1: 0.02, item2: 0.01, fake: 0.005}

divide item 1 by fake gives you 4. Divide item 2 by fake gives you 2.

plug 4 and 2 into the objective function and you get this:

[JWally]

@joshrickert not sure if you would have been notified of this or not (promise I'm not fishing for compliments :D ) with the issue being closed, but in case you haven't the above method is (yet) another approach. Feel free to re-open if you have questions / whatever.

[joshrickert]

Justin, your and Brice's help has been awesome here. I think both of the recent solutions you've proposed should solve the issue. I may even use them both in case I need a fallback. I'll let you know if there's any trouble.