{"action":"created","issue":{"url":"https://api.github.com/repos/JWally/jsLPSolver/issues/19","labels_url":"https://api.github.com/repos/JWally/jsLPSolver/issues/19/labels{/name}","comments_url":"https://api.github.com/repos/JWally/jsLPSolver/issues/19/comments","events_url":"https://api.github.com/repos/JWally/jsLPSolver/issues/19/events","html_url":"https://github.com/JWally/jsLPSolver/issues/19","id":112901700,"number":19,"title":"Multi-Objective Optimization","user":{"login":"JWally","id":2482935,"avatar_url":"https://avatars.githubusercontent.com/u/2482935?v=3","gravatar_id":"","url":"https://api.github.com/users/JWally","html_url":"https://github.com/JWally","followers_url":"https://api.github.com/users/JWally/followers","following_url":"https://api.github.com/users/JWally/following{/other_user}","gists_url":"https://api.github.com/users/JWally/gists{/gist_id}","starred_url":"https://api.github.com/users/JWally/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/JWally/subscriptions","organizations_url":"https://api.github.com/users/JWally/orgs","repos_url":"https://api.github.com/users/JWally/repos","events_url":"https://api.github.com/users/JWally/events{/privacy}","received_events_url":"https://api.github.com/users/JWally/received_events","type":"User","site_admin":false},"labels":[],"state":"open","locked":false,"assignee":null,"milestone":null,"comments":6,"created_at":"2015-10-22T22:08:49Z","updated_at":"2015-10-23T16:52:37Z","closed_at":null,"body":"@bchevalier \r\n\r\nWhat are your thoughts on trying to handle optimization problems with multiple objectives?\r\nI've figured out a way to do it, but it's not pretty; and I wanted your input on the route I'm taking, and if its even worth including.\r\n\r\nHere's a use case:\r\n\r\n> Some diets allow you to eat as much junk food as you want and still lose weight and gain muscle\r\n> *as long* as your ratio of carbs to protein to fat stays in check.\r\n>\r\n> My optimal ratio requires me to eat 375 grams of carbs, 225 grams of protein, and 66.666 grams\r\n> of fat per day. I also want to eat as much bacon, cheese, and french fries as possible.\r\n>\r\n> How much of what should I eat to satisfy these requirements?\r\n\r\nBelow is what I'm proposing multi-opt models look like (no code changes need to happen with what you've done, since models with an array for the optimize attribute could be handled differently).\r\n\r\n```javaScript\r\n{ \r\n    \"name\": \"Food Problem\",\r\n    \"optimize\": [\r\n        {\"key\":\"bacon\", \"opType\": \"max\"},\r\n        {\"key\": \"cheddar cheese\", \"opType\": \"max\"},\r\n        {\"key\": \"french fries\", \"opType\": \"max\"}\r\n    ],\r\n    \"constraints\": { \r\n        \"carb\": { \"equal\": 375 },\r\n        \"protein\": { \"equal\": 225 },\r\n        \"fat\": { \"equal\": 66.666 } \r\n    },\r\n    \"variables\": { \r\n         \"egg white\":{ \"carb\": 0.0073, \"protein\": 0.109, \"fat\": 0.0017, \"egg white\": 1 },\r\n         \"egg whole\":{ \"carb\": 0.0072, \"protein\": 0.1256, \"fat\": 0.0951, \"egg whole\": 1 },\r\n         \"cheddar cheese\":{ \"carb\": 0.0128, \"protein\": 0.249, \"fat\": 0.3314, \"cheddar cheese\": 1 },\r\n         \"bacon\":{ \"carb\": 0.00667, \"protein\": 0.116, \"fat\": 0.4504, \"bacon\": 1 },\r\n         \"potato\": { \"carb\": 0.1747, \"protein\": 0.0202, \"fat\": 0.0009, \"potato\": 1 },\r\n         \"french fries\": { \"carb\": 0.3902, \"protein\": 0.038, \"fat\": 0.1612, \"french fries\": 1 }\r\n    } \r\n}\r\n```\r\nHere's what I've come up with so far, referencing the above model:\r\n\r\n1. Maximize and minimize the model for each attribute to be optimized\r\n```\r\nbacon: {most: 138, least: 0}\r\ncheese: {most: 189, least: 0}\r\nfries: {most: 388, least: 0}\r\n```\r\n\r\n2. Add a nonsense attribute to each variable that you'll use to solve on, since this solution works by updating constraints and making sure the model is feasible\r\n\r\n3. Create a function that accepts an array which represents what the min for each optimization attribute should be (or max if the attribute is being minimized).\r\n\r\nFor example, I could give it [44, 66, 115] (for bacon, cheese, and fries), and it would update the model to look like this:\r\n\r\n```javaScript\r\n    \"constraints\": { \r\n        \"carb\": { \"equal\": 375 },\r\n        \"protein\": { \"equal\": 225 },\r\n        \"fat\": { \"equal\": 66.666 },\r\n        \"bacon\": { \"min\": 44},\r\n        \"cheddar cheese\": { \"min\": 66 },\r\n        \"french fries\": { \"min\": 115 }        \r\n    }\r\n```\r\n\r\n3a. The function would then solve the model with these new constraints, returning the following:\r\n```\r\n{ feasible: true,\r\n  result: 3534.71621236,\r\n  bacon: 49.05518453,\r\n  'egg white': 1483.68745307,\r\n  potato: 1820.97357477,\r\n  'cheddar cheese': 66,\r\n  'french fries': 115}\r\n```\r\n\r\n3b. Compare the results for the optimization attributes to their potential best (step 1). For instance, for cheese in this example, you'd go:\r\n```javaScript\r\n   (66 - 0 (worst)) / (189(best) - 0(worst))\r\n```\r\n\r\nWhich returns 0.35. Multiply all of the results together to get 0.0366677. This is our score. Return it out.\r\n\r\n4. Create some optimization function (gradient descent?) that will maximize the score in as few steps as possible.\r\n\r\nBelow is what I have so far (since I can't upload it) where I use brute force to solve the above problem. Very un-refined at this point and very much a work in progress. \r\n\r\n```javaScript\r\n\r\nvar solver = require(\"./src/solver\");\r\n\r\n\r\nvar the_model = { \r\n    \"name\": \"Food Problem\",\r\n    \"optimize\": [\r\n        {\"key\":\"bacon\", \"opType\": \"max\"},\r\n        {\"key\": \"cheddar cheese\", \"opType\": \"max\"},\r\n        {\"key\": \"french fries\", \"opType\": \"max\"}\r\n    ],\r\n    \"constraints\": { \r\n        \"carb\": { \"equal\": 375 },\r\n        \"protein\": { \"equal\": 225 },\r\n        \"fat\": { \"equal\": 66.666 } \r\n    },\r\n    \"variables\": { \r\n         \"egg white\":{ \"carb\": 0.0073, \"protein\": 0.109, \"fat\": 0.0017, \"egg white\": 1 },\r\n         \"egg whole\":{ \"carb\": 0.0072, \"protein\": 0.1256, \"fat\": 0.0951, \"egg whole\": 1 },\r\n         \"cheddar cheese\":{ \"carb\": 0.0128, \"protein\": 0.249, \"fat\": 0.3314, \"cheddar cheese\": 1 },\r\n         \"bacon\":{ \"carb\": 0.00667, \"protein\": 0.116, \"fat\": 0.4504, \"bacon\": 1 },\r\n         \"potato\": { \"carb\": 0.1747, \"protein\": 0.0202, \"fat\": 0.0009, \"potato\": 1 },\r\n         \"french fries\": { \"carb\": 0.3902, \"protein\": 0.038, \"fat\": 0.1612, \"french fries\": 1 }\r\n    } \r\n};\r\n\r\nfunction Fit_Fx(){};\r\n\r\nFit_Fx.prototype.load = function(model){\r\n    \r\n    // Some variables to help\r\n    // keep track of stuff down\r\n    // below\r\n    var tmp_obj = {},\r\n        tmp_sol = {},\r\n        tmp_key = \"\",\r\n        tmp_num = 0;\r\n    \r\n    \r\n    // Create an object on *this* to house\r\n    // all of our fitness info\r\n    this._data = {\r\n        \r\n        // Where we hold the things\r\n        // we want to optimize\r\n        \"targets\": {},\r\n        \r\n        // This'll be easier than\r\n        // having to eat up `Object.keys`\r\n        \"keys\": [],\r\n        \r\n        // And we'll want a hard and fast\r\n        // version of the model\r\n        // so here\r\n        \"model\": JSON.parse(JSON.stringify(model))\r\n    };\r\n    \r\n    // Loop over the array of objectives\r\n    // storing the pertinents of each\r\n    // somewhere in our _data object\r\n    for(var i = 0; i < model.optimize.length; i++){\r\n        \r\n        // get the key we're working with\r\n        tmp_key = model.optimize[i].key;\r\n    \r\n        // Load the target's key into the \"Keys\" object\r\n        this._data.keys.push(tmp_key)\r\n    \r\n        // push the model's details into this._data.targets\r\n        tmp_obj = this._data.targets[model.optimize[i].key] = model.optimize[i];\r\n        \r\n        // add a best and worst to each of these objects\r\n        // not sure if we'll need them; but in case we do,\r\n        // it'll be nice #YAGNI\r\n        tmp_obj.best = 0;\r\n        tmp_obj.worst = tmp_obj.opType === \"max\" ? 1e99 : 0;\r\n\r\n    }\r\n    \r\n    // Loop over our keys, and figure out what the optimum\r\n    // is for each target in isolation...\r\n    for(i = 0; i < this._data.keys.length; i++){\r\n        \r\n        // since we're not doing anything *too* weird\r\n        // we don't need to `JSON.parse(stringify))`\r\n        // the model\r\n        tmp_obj = this._data.model;\r\n        \r\n        // set the model's optimize and optypes for best\r\n        tmp_obj.optimize = this._data.keys[i];\r\n        tmp_obj.opType = this._data.targets[tmp_obj.optimize].opType;\r\n        \r\n        // Solve the model\r\n        tmp_sol = solver.Solve(tmp_obj);\r\n       \r\n        // Update the best\r\n        this._data.targets[tmp_obj.optimize].best = tmp_sol.result;\r\n        \r\n        // Do the whole thing again, but aimed @ worst\r\n        tmp_obj.opType = tmp_obj.opType === \"max\" ? \"min\" : \"max\";\r\n        \r\n        // Solve the bad model\r\n        tmp_sol = solver.Solve(tmp_obj);\r\n        \r\n        // Note to self...\r\n        // this feels like shadow prices\r\n        // or something...\r\n        // Because this is aimed at \"trivial\"\r\n        // examples, this isn't expensive; \r\n        // but there's probably\r\n        // a lot more effecient way of\r\n        // doing this...\r\n        \r\n        // Update the worst\r\n        this._data.targets[tmp_obj.optimize].worst = tmp_sol.result;\r\n    }\r\n    \r\n    // Finally, give each variable some non-sense\r\n    // attribute to optimize\r\n    for(i in this._data.model.variables){\r\n        this._data.model.variables[i].fake_target = 1;\r\n    }\r\n    \r\n    \r\n}\r\n\r\n// Easy function to get details out\r\n// should we want them...\r\nFit_Fx.prototype.details = function(){\r\n    return this._data;\r\n}\r\n\r\n// Now we do the actual scoring function\r\nFit_Fx.prototype.score = function(vector){\r\n    \r\n    // Copy the model, get the keys, and targets\r\n    var model = this._data.model,\r\n        keys = this._data.keys,\r\n        targets = this._data.targets,\r\n        tmp_opt = \"\",\r\n        tmp_sol = {},\r\n        tmp_obj = {},\r\n        tmp_num = 0,\r\n        total = 1;\r\n        \r\n    // Update the model to go after the fake target\r\n    // and set optype to \"max\" because...who cares\r\n    model.opType = \"max\";\r\n    model.optimize = \"fake_target\";\r\n    \r\n    // Set Constraints based on the vectors\r\n    for(var i = 0; i < keys.length; i++){\r\n        model.constraints[keys[i]] = model.constraints[keys[i]] || {};\r\n        tmp_opt = targets[keys[i]].opType = \"max\" ? \"min\" : \"max\";\r\n        model.constraints[keys[i]][tmp_opt] = vector[i];\r\n    }\r\n    \r\n    // Solve it now!\r\n    tmp_sol = solver.Solve(model);\r\n    \r\n    // Make sure its feasible\r\n    if(tmp_sol.feasible){\r\n        \r\n        // Iterate over the keys again...\r\n        for(i = 0; i < keys.length; i++){\r\n            \r\n            tmp_obj = targets[keys[i]];\r\n            \r\n            // First off, does the key\r\n            // exist in the solution?\r\n            if(tmp_sol[keys[i]]){\r\n                if(tmp_obj.opType = \"max\"){\r\n                    tmp_num = (tmp_sol[keys[i]] - tmp_obj.worst) / (tmp_obj.best - tmp_obj.worst);\r\n                    total *= tmp_num;\r\n                } else {\r\n                \r\n                }\r\n            } else {\r\n            \r\n                // target doesn't exist in the solution\r\n                // set Return a score of 0\r\n                return 0\r\n            }\r\n        }\r\n        \r\n        // Return what we got\r\n        tmp_sol.score = total;\r\n        return tmp_sol;\r\n    } else {\r\n    \r\n        // Solution isn't feasible...\r\n        return 0;\r\n    }\r\n    \r\n}\r\n\r\nfunction loop_index(nbr, arry){\r\n    var rtrn = [];\r\n\r\n    for(var i = 0; i < arry.length; i++){\r\n        rtrn.push(nbr % arry[i]);\r\n        nbr = Math.floor(nbr / arry[i]);\r\n    }\r\n    return rtrn;\r\n}\r\n\r\n// Instantiate the function\r\nvar fitness = new Fit_Fx();\r\n\r\n// Load the model into the function\r\n// to set up scoring\r\nfitness.load(the_model);\r\n\r\n// Play Example for testing\r\n\r\nvar ary = [138, 189, 388],\r\n        tst = [],\r\n        tmp,\r\n        rslts = [],\r\n        global = {score: -1e99};\r\n        \r\nvar num = 11;\r\n\r\nfor(i = 0; i < num * num * num; i++){\r\n    tst = (loop_index(i,[num, num, num]).map(function(d, b){return d/(num - 1) * ary[b]}));\r\n    tmp = fitness.score(tst);\r\n    \r\n    if(tmp !== 0){\r\n        global = tmp.score > global.score ? tmp : global;\r\n    }\r\n}\r\n\r\n\r\nconsole.log(global);\r\n\r\n```\r\n\r\n\r\n\r\n\r\n"},"comment":{"url":"https://api.github.com/repos/JWally/jsLPSolver/issues/comments/150631443","html_url":"https://github.com/JWally/jsLPSolver/issues/19#issuecomment-150631443","issue_url":"https://api.github.com/repos/JWally/jsLPSolver/issues/19","id":150631443,"user":{"login":"JWally","id":2482935,"avatar_url":"https://avatars.githubusercontent.com/u/2482935?v=3","gravatar_id":"","url":"https://api.github.com/users/JWally","html_url":"https://github.com/JWally","followers_url":"https://api.github.com/users/JWally/followers","following_url":"https://api.github.com/users/JWally/following{/other_user}","gists_url":"https://api.github.com/users/JWally/gists{/gist_id}","starred_url":"https://api.github.com/users/JWally/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/JWally/subscriptions","organizations_url":"https://api.github.com/users/JWally/orgs","repos_url":"https://api.github.com/users/JWally/repos","events_url":"https://api.github.com/users/JWally/events{/privacy}","received_events_url":"https://api.github.com/users/JWally/received_events","type":"User","site_admin":false},"created_at":"2015-10-23T16:52:37Z","updated_at":"2015-10-23T16:52:37Z","body":"Sweet!\r\nI'll hold off until your next pr.\r\n\r\nAlso, I think I'm going to try and update the readme.md to reflect some of the functionality adds since I first wrote it. (Maybe not here), but could you explain your PR from earlier today, and what a use case might be for it. "}}