Trying to find the no-dominated solutions of two arrays

Question

I'm trying to find the no-dominated values of two arrays in an optimization problem.

I've two arrays, lost_bars_array and prices_array. What I want to do is MINIMIZE the lost bars, and MAXIMIZE the price. I want to get a final array named no_dominated with the index of the non-dominates values of both arrays. It's easy to understand. Let me explain this with an example.

We have the inital two arrays:

The theorical process is something like:

1. Get the first value

2. Get the second one (index #1) and see if its a better solution than the first one. This means we've to see if the second one has LESS lost bars and a BIGGER price. This is not the case, it has LESS bars, but also LESS price, so we can't say it's a better solution. We save it as a posible solution

3. Now comes the next one, index #2, this one improves the solution of index #1 because it has LESS lost brs and a BIGGER price. But it doesnt improve index #0 because it has LESS lost bars but also LESS price. So we save index #0 and index #2 as possible solutions.

4. Index #3, and #4, has MORE lost bars and LESS price, so just reject them as possible solutions.

5. Finally, index #5, has LESS lost bars and MORE price than index #0, so, solution of index #0 is rejected, and the final no-dominated values will be the ones of index #2 and index #5.

This is what I've tried so far.

#include <stdio.h>

int main(int argc, char** argv)
{
    int lost_bars_array[] = {15, 10,  8, 15, 17,  9};
    int prices_array[]    = {35, 25, 30, 10, 15, 36};
    int no_dominated[6];
    int cont              = 6;

    for (int actual_pos = 0; actual_pos < cont; actual_pos++)
    { 
        if (actual_pos == 0)
        {
            no_dominated[actual_pos] = actual_pos; 
        } 
        else
        {
            // Here's where I've the problems, I dont know how to handle the arrays
            for (int p = 0; p < actual_pos; p++)
            {
                if (lost_bars_array[p] > lost_bars_array[p + 1] && 
                    prices_array[p] < prices_array[p + 1])
                {
                    no_dominated[p] = p;
                }

            }
        }
    }

    printf("\nThe non-dominated solutions index are: %d");
    for (int i = 0; i < 6; i++)
    {
        printf(" %d ", no_dominated[i]);
    }

    printf("\n");

    return 0;
}

The code should output the index 2 5 as solution. I hope I explained the problem correctly.
Any help is appreciated. Thanks in advance.

Answer 1

The program below gets what you want, but I've only tested it for your specific case; it may very well fail in case there is only one dominated solution, or in a few other special cases. But you may be able to work from this.

Two notes:

• you forgot to include the potential solutions; the boolean && will only save solutions that are guaranteed to be better

• the last double loop is a bit of a hack; hashes would be easier (the solution index would be the hash), but I think that requires c++ or an extra library.

Code:

#include <stdio.h>

int main() 
{
    int lost_bars_array[] = {15,10,8,15,17,9};
    int prices_array[] = {35,25,30,10,15,36};
    int no_dominated[6];
    int cont = 6;
    int ndom = 0;

    no_dominated[ndom] = 0;
    ndom++;
    for (int actual_pos = 1; actual_pos < cont; actual_pos++) { 
        int ntmp = ndom;
        for(int p = 0; p < ntmp; p++) {
            if (lost_bars_array[no_dominated[p]] > lost_bars_array[actual_pos] && 
                prices_array[no_dominated[p]] < prices_array[actual_pos]) {
                // Replace with a better solution
                no_dominated[p] = actual_pos;
        } else if (lost_bars_array[no_dominated[p]] > lost_bars_array[actual_pos] ||
               prices_array[no_dominated[p]] < prices_array[actual_pos]) {
                // Save as potential solution
                no_dominated[ndom] = actual_pos;
                ndom++;
            }
        }
    }
    // Remove double solutions
    for (int i = 0; i < ndom; i++) {
        for (int j = i; j < ndom; j++) {
            if (no_dominated[i] == no_dominated[j]) {
                ndom--;
            }
        }
    }
    printf("\nThe non-dominated solutions index are:");
    for(int i = 0; i < ndom; i++)
        printf(" %d ", no_dominated[i]);
    printf("\n");
    return 0;
}