Finding smallest triplets given a set of options

Question

I am working on this problem to find the smallest triplet given a set of triplets which is smallest in all three dimensions. However, if there exists a triplet which is smallest is any one or two dimensions than the smallest across all three dimensions, that too needs to be considered.

Example

Let me give an example. Say, my triplets are as follows

(25, 30, 34), (15, 31, 21), (10, 40, 21), (50, 30, 34), (25, 30, 10), (9, 20, 15)

Now, (9,20,15) looks to be the smallest across all three dimensions. However, there also exists an option (25,30,10) which is smallest in the third dimension since it's score in the third diemnsion(10) is smallest than any of the other options, so that too needs to be included in the output too. so the final output would be {(9,20,15) and (25,30,10)}

So, basically a solution should be considered if it is either Dominant or Optimal. I can define these as follows

1. Dominant : If an outcome o is at least as good for another agent as another outcome o' and there is some
agent who strictly prefers o to o'. Then o pareto-dominates o'

2. Optimal : o* is pareto-optimal if it isn't pareto-dominated by anything else

My algorithm

This is my algorithm. Please see the attached code. Let the three dimensions be called Course1Score, Course2Score and Course3Score.

So I traverse across the inputs, and find the smallest for each of the following

1.{Course1Score}
2.{Course2Score}
3.{Course3Score}
4.{Course1Score, Course2Score}
5.{Course1Score, Course3Score}
6.{Course2Score, Course3Score}
7.{Course1Score, Course2Score, Course3Score}

I then find the distinct solution among the solutions which minimize the above objectives.

False case

Now this would work for most cases except in a case like below. Let the input be (1,100,100), (100,1,100), (100,100,1), (1,1,1) As per the above algorithm, the scores which minimize the above objectives would be as follows

 1.Minimize {Course1Score} - (1,100,100) 
(remember this won't be over-written by say,(1,1,1) since Course1Score of (1,1,1) IS NOT LESS than Course1Score of (1,100,100) which comes first in the order of inputs) )
    2.Minimize {Course2Score} - (100,1,100)
    3.Minimize {Course3Score} - (100,100,1)
    4.Minimize {Course1Score, Course2Score} - (1,100,100)
    5.Minimize {Course1Score, Course3Score} - (1,100,100)
    6.Minimize {Course2Score, Course3Score} - (100,1,100)
    7.Minimize {Course1Score, Course2Score, Course3Score} - (1,1,1)

Continuing with the algorithm, we find the distinct solution and report them as (1,100,100), (100,1,100), (100,100,1), (1,1,1) However, this solution is incorrect. Since (1,1,1) beats all of the other solutions in all three dimensions, and none of (1,100,100), (100,1,100), (100,100,1) are better than (1,1,1) in any of the dimensions. So, I add an extra condition to check this at the end which can be found in the function

Online java fiddle

This is an online java fiddle of my implementation

My implementation

Please find my code

import java.util.ArrayList;

/* Glossary
 * 1. Dominant : If an outcome o is at least as good for another agent as another outcome o' and there is some
 * agent who strictly prefers o to o'. Then o Triplet-dominates o'
 * 
 * 2. Optimal : o* is Triplet-optimal if it isn't Triplet-dominated by anything else
 * 
 *   */
public class HelloWorld
{
    public static void main(String[] args)
    {
        Triplet myTriplet = new Triplet();

        /* Populating input and printing them */
        System.out.println("Printing input");
        myTriplet.PopulateSampleInput();
        myTriplet.Print(myTriplet.options);

        /* Printing the Triplet-Optimal solutions */
        ArrayList



Can you please suggest an algorithm for the above, and/or review my algo and implementation?

EDIT : I think this solution works

Pseudocode

ParetoSolutionPool[1] = input[1]

for(i in 2:input)
    boolean ParetoDominant = false;
    boolean ParetoOptimal = true;

    for(j in 1:ParetoSolutionPool)
        if(input[i] ParetoDominates ParetoSolutionPool[j])
            remove ParetoSolutionPool[j]
            ParetoDominant = true;

        if(input[i] IsParetoDominatedBy ParetoSolutionPool[j])//extra if(ParetoDominant == false && ParetoOptimal == true && above)
            ParetoOptimal = false;
    end of for loop over j

    if(ParetoDominant || ParetoOptimal == true)
        add input[i] to ParetoSolutionPool

end of for loop over i


Pseudocode in words

Basically, two checks.
1.If an input/option domoinates(lower in all three dimensions), one of the existing solutions, that "existing solution" is popped, and replaced by this input, since it's better unanimously. (Eg 25,30,10 better than 25,30,34)

2.If an input is NOT WORSE (in all three dimensions )than any of the existing solutions, then it too has to be considered to the solution pool.

So basically in either of the two cases, above, an input is added to the solution pool. Only difference between the two being that in the first case, the weaker existing solution is popped as well.

Code

package TripletOptimizationAlgorithms;

import java.io.BufferedReader;
import java.io.DataInputStream;
import java.io.FileInputStream;
import java.io.InputStreamReader;
import java.nio.file.Paths;
import java.util.ArrayList;
import java.util.Collections;

public class algo4
{
    public static void main(String[] args)
    {
        Triplet myTriplet = new Triplet();

        /* Populating input and printing them */
        System.out.println("Printing input");
        //myTriplet.PopulateSampleInput();
        myTriplet.PopulateSampleInputFromFile();
        myTriplet.Print(myTriplet.options);
        System.out.println("Number of inputs read=="+myTriplet.options.size());

        /* Printing the Triplet-Optimal solutions */
        final long startTime = System.currentTimeMillis();
        ArrayList

Finding smallest triplets given a set of options

Answers (1)

Related Questions