best combination algorithm of complex data with multiple contraints

Question

I guess we can say that this is very similar to an already asked question here (Optimisation/knapsack algorithm with multiple contraints in JavaScript), which hasn't yet an answer.

Let say we like javascript, C, C++, java. Any of this languages work for me. Anyone know algorithms to solve the problem?

PROBLEM: find the best subset of items which grants minimum cost and maximum number of objects, knowing that there's a limitation of resource:

var items = [
    {name: "Rome", cost: 1000, hours: 5, peoples: 5},
    {name: "Venice", cost: 200, hours:  1, peoples: 10},
    {name: "Torin", cost: 500, hours: 3, peoples: 2},
    {name: "Genova", cost: 700, hours: 7, peoples: 8},
    {name: "Rome2", cost: 1020, hours: 5, peoples: 6},
    {name: "Venice2", cost: 220, hours:  1, peoples: 10},
    {name: "Torin2", cost: 520, hours: 3, peoples: 2},
    {name: "Genova2", cost: 720, hours: 7, peoples: 4},
    {name: "Rome3", cost: 1050, hours: 5, peoples: 5},
    {name: "Venice3", cost: 250, hours:  1, peoples: 8},
    {name: "Torin3", cost: 550, hours: 3, peoples: 8},
    {name: "Genova3", cost: 750, hours: 7, peoples: 8}
];
var maxCost = 10000, maxHours = 100, maxPeoples = 50;
// find subset of items that minimize cost, hours and peoples
// and maximize number of items
// do not exceed max values!!!

IDEAS I HAD: I imagined I could do a solution to knapsack problem for each couple of cost (let call them "KPcost-hours", "KPhours-cost", "KPcost-peoples" etc.), which grants me the solution to optimize single costs. Then, if I'm lucky, take the common parts of this subsets and work from there... but i don't think it's a good path...

If you can give a script sample, or a pseudo-script sample, you're welcome! Thank you!

Answer 1

Assuming one can only select 0 or 1 of each item, there are 2^12=4096 combinations possible. The number of feasible solutions is 3473. The number of non-dominated (or Pareto optimal) solutions is 83.

I used two different approaches:

1. Enumerate all feasible solutions. Then filter out all dominated solutions (each solution must be better in at least one objective than all other solutions).

2. Write a Mixed Integer Programming. It finds a solution, and adds a constraint that says: it should be better in at least one of the objectives than previous solutions. (Along the lines of this model).

Both methods find these 83 solutions. For this problem complete enumeration is faster.

Note that the number of Pareto optimal solutions can grow quickly. Here are some pictures of such a Pareto optimal set of a real-world design problem.

Note that there is no "single" best solution. All Pareto optimal solutions are optimal. Only when you make assumptions on the trade-offs between objectives, you can reduce the number of optimal solutions further.

Answer 2

I elaborate a working solution, but it's really bruteforce, however a bit optimized. I didn't went thru the Pareto solution which I believe is probably a better solution. Unfortunately the script from Nina Sholz didn't work (at least for me), so I came up with this one.

Just to leave here a working sample (read: don't use for BIG data).

PS - if anyone can write any phrase in a better english, comment below, I'll correct my bad writing.

/**
 * Brute Force approach
 * Problem: find combination of data objects to minimize sum of object properties and maximize number of objects
 * Costraint: sum of object properties has upper limit (for each property)
 * Solution used: do every combination, starting with the max number of objects, then lower by 1 each time, until a (or more) combination satisfy every criteria.
 */


// combination
// e.g. combination of 3 numbers with value from 0 to 4 -> combination(3,5)
// see https://rosettacode.org/wiki/Combinations#JavaScript
function combination(n, length) {
 
  // n -> [a] -> [[a]]
  function comb(n, lst) {
if (!n) return [[]];
if (!lst.length) return [];
 
var x = lst[0],
  xs = lst.slice(1);
 
return comb(n - 1, xs).map(function (t) {
  return [x].concat(t);
}).concat(comb(n, xs));
  }
 
  // f -> f
  function memoized(fn) {
m = {};
return function (x) {
  var args = [].slice.call(arguments),
    strKey = args.join('-');
 
  v = m[strKey];
  if ('u' === (typeof v)[0])
    m[strKey] = v = fn.apply(null, args);
  return v;
}
  }
 
  // [m..n]
  function range(m, n) {
return Array.apply(null, Array(n - m + 1)).map(function (x, i) {
  return m + i;
});
  }
 
  var fnMemoized = memoized(comb),
lstRange = range(0, length-1);
 
  return fnMemoized(n, lstRange)
}




// just some math calculation ------
// obviously n & r in N; r < n
function _factor(n){
var f = 1;
while (n > 1){ f *= n--; }
return f;
}
function _factor2(n,to){
var f = 1;
while (n > 1 && n >= to){ f *= n--; }
return f;
}
function _factorFraction(sup,inf){
return (sup > inf) ? _factor2(sup,inf+1) : 1/_factor2(inf,sup+1)
}
function _combination(n,r){
return (r > n/2) ? _factorFraction(n,r)/_factor(n-r) : _factorFraction(n,n-r)/_factor(r); // namely _factor(n)/_factor(n-r)/_factor(r)
}
// just some math calculation ------



var minr = 2,			// set inferior limit (r) of combination search. 2 <= minr < datas.length
datas = [],			// to be set. matrix to be filled with array of data
limits = [0],		// to be set. contains limit for each datas column
comboKeep = [],		// will contain all solutions found
columns,
sums,
timer;
function combineCheck(r){
if (r < minr) return;
console.log("Expected number of combination C(",datas.length,",",r,") = ",_combination(datas.length,r));
var metconditions = 0;
var CNR = combination(r,datas.length);
CNR.forEach(combo => {
	sums = new Array(columns).fill(0);
	// calculate sum for each column
	for (var j=0; j<combo.length; j++){
		for (var i=0; i<columns; i++){
			sums[i] += datas[combo[j]][i];
		};
	}
	// check if conditions are met
	for (var i=0; i<columns; i++){
		if (sums[i] > limits[i]){
			//console.log("sum of column",i,"exceeds limit (",sums[i]," > ",limits[i],")");
			return;
		}
	};
	comboKeep.push(combo);
	metconditions++;
});
console.log("Condition met in ",metconditions,"combos.");
if (metconditions == CNR.length){
	console.log("No need to go further, all combo have been checked.");
	return;
}
//------------
// OPTIONAL...
//------------
if (metconditions) return; // remove this line if you want all possible combination, even with less objects

combineCheck(r-1); // for delayed call: setTimeout( () => combineCheck(r-1), 250 );
}

function combineCheckStarter(){
comboKeep = [];
columns = datas[0].length;
timer = Date.now();
combineCheck(datas.length-1);
timer = Date.now() - timer;
}


//-----------------------------------------
var items = [
{name: "Rome", cost: 1000, hours: 5, peoples: 5},
{name: "Venice", cost: 200, hours:  1, peoples: 10},
{name: "Torin", cost: 500, hours: 3, peoples: 2},
{name: "Genova", cost: 700, hours: 7, peoples: 8},
{name: "Rome2", cost: 1020, hours: 5, peoples: 6},
{name: "Venice2", cost: 220, hours:  1, peoples: 10},
{name: "Torin2", cost: 520, hours: 3, peoples: 2},
{name: "Genova2", cost: 720, hours: 7, peoples: 4},
{name: "Rome3", cost: 1050, hours: 5, peoples: 5},
{name: "Venice3", cost: 250, hours:  1, peoples: 8},
{name: "Torin3", cost: 550, hours: 3, peoples: 8},
{name: "Genova3", cost: 750, hours: 7, peoples: 8}
];
var datas = Array.from(items, e => [e.cost, e.hours, e.peoples]);
var limits = [2500, 8, 20];
//-----------------------------------------

// test ;)
combineCheckStarter();
console.log("Combination found in ",timer,"ms:",comboKeep);


// pretty print results
var prettier = new Array(comboKeep.length),
unifier = new Array(columns).fill(0);
comboKeep.forEach( (combo, k) => {
var answer = new Array(combo.length);
sums = new Array(columns).fill(0);
combo.forEach((itm,i) => {
	answer[i] = items[itm].name;
	for (var j=0; j<columns; j++){
		sums[j] += datas[itm][j];
	};
});
prettier[k] = {items: answer.join(","), cost: sums[0], hours: sums[1], peoples: sums[2]};
for (var j=0; j<columns; j++){
	if (unifier[j]<sums[j]) unifier[j] = sums[j];
};
});
// normalize 
prettier.forEach( e => {
e.total = e.cost/unifier[0] + e.hours/unifier[1] + e.peoples/unifier[2];
});

//find the best (sum of all resource is lower)
prettier.sort( (b,a) => b.total-a.total);
console.log("sorted solutions:",prettier);
console.log("Best solution should be ",prettier[0].items,prettier[0]);

Answer 3

General solution

PROBLEM: find the best subset of items which grants minimum cost and maximum number of objects, knowing that there's a limitation of resource.

I see two optimization criteria here (I'll talk about the case where you want to minimize people, hours and cost below as well).
A possible approach is to build a program that will return a maximum Pareto-optimal set of solutions.

A Pareto set is a set of non-dominating solutions, meaning that for any two solutions S1 and S2, S1 does not dominate S2, and vice versa. A solution S1 dominates a solution S2 if it is better or equal than S2 regarding all criterias, and strictly better regarding at least one criteria.

For example, in your case, we can consider the following solutions:

S1: cost = 10, nb_objects = 4
S2: cost = 10, nb_objects = 7
S3: cost = 0, nb_objects = 0
S4: cost = 14, nb_objects = 6

Then our Pareto-optimal set of solutions is {S1, S3, S4}. That is because they do not dominate each other (for example, S1 does not dominate S4 because S4 is better regarding the number of objects). S2 is not part of the Pareto-optimal solution because it is dominated by both S1 and S4.

In the general case, Pareto-set are very hard to calculate, and can be extremely big. In your particular case, 4 criteria seem somehow reasonable, but it always can be surprising.
Here is a pseudocode on how to compute such a set of solutions:

Result = array of size nb_objects, initialized with empty sets
for i from 0 to total_nb_of_objects:
    for each feasible solution 'new_solution' to the problem with fixed number of objects:
        for each solution of Result[i]:
            if hours(new_solution) >= hours(solution) and  \
               cost(new_solution) >= cost(solution) and    \
               people(new_solution) >= people(solution):
                dominated = true
                break
        if not dominated:
            add new_solution to Result[i]
return Result

This little pseudocode here has more a value to try and understand the concept of Pareto Efficiency, I would not advice looping on all the feasible solutions of a variation to a knapsack problem (too costy).

Answer 4

A brute force approach by checking all combinations.

function getItems(array, constraints, [optimum, equal]) {
    function iter(index = 0, right = [], add) {

        function update() {
            if (!result.length || optimum(right, result[0])) return result = [right];
            if (equal(right, result[0])) result.push(right);
        }

        if (index >= array.length || !constraints.every(fn => fn(right))) return;
        if (add && right.length) update();

        var temp = right.find(({ ref }) => ref === array[index]),
            old = JSON.parse(JSON.stringify(right));

        if (temp) {
            temp.count++;
        } else {
            right.push({ count: 1, ref: array[index] });
        }

        iter(index, right, true);
        iter(index + 1, old);
    }

    var result = [];
    iter();
    return result;
}

const
    addBy = k => (s, { count, ref: { [k]: value } }) => s + count * value,
    addCount = (s, { count }) => s + count;

// find subset of items that minimize cost, hours and peoples
// and maximize number of items
// do not exceed max values!!!
var items = [{ name: "Rome", cost: 1000, hours: 5, peoples: 5 }, { name: "Venice", cost: 200, hours: 1, peoples: 10 }, { name: "Torin", cost: 500, hours: 3, peoples: 2 }, { name: "Genova", cost: 700, hours: 7, peoples: 8 }],
    maxCost = 10000,
    maxHours = 100,
    maxPeoples = 50,
    result = getItems(
        items,
        [
            array => array.reduce(addBy('cost'), 0) <= maxCost,
            array => array.reduce(addBy('hours'), 0) <= maxHours,
            array => array.reduce(addBy('peoples'), 0) <= maxPeoples
        ],
        [
            (a, b) => a.reduce(addCount, 0) > b.reduce(addCount, 0),
            (a, b) => a.reduce(addCount, 0) === b.reduce(addCount, 0)
        ]
    );

console.log(result);

.as-console-wrapper { max-height: 100% !important; top: 0; }