dimanche 4 novembre 2018

C++ Implementation of Pruning Rules in 2-D Linear Programming Using Prune and Search

I am implementing solving 2-Dim linear programming using prune and search in C++, and here is the reference, page 5 to page 16.

My question is about, how to write pruning rule(page 12) in clean C++ code.

The pruning rule is, given an intersection "a" and the optimal solution OPT, and their x coordinate a(x), OPT(x).

  • For lower boundary constraint cases,
    • If a(x) > OPT(x) then the constraint with larger slop can be removed.
    • If a(x) < OPT(x) then the constraint with smaller slop can be removed.
  • For upper boundary constraint cases,
    • If a(x) < OPT(x) then the constraint with larger slop can be removed.
    • If a(x) > OPT(x) then the constraint with smaller slop can be removed.

I have wrote my C++ implementation, I think there are many redundent and I need some suggestions to have improvement in C++ writing.

void pruneConstraintsLower(
        ConstraintSet &lowerConstraintSet,
        float xMedian,
        vector<IntersectionPoint> lowerBoundaryIntersections,
        CompareToOpt e
        ){
    switch(e){
    case GREATER:
        for(IntersectionPoint point: lowerBoundaryIntersections){
            if(point.X > xMedian){
                float firstSlop = getSlop(lowerConstraintSet.getOneByIndex(point.lineIndicesPair.first));
                float secondSlop = getSlop(lowerConstraintSet.getOneByIndex(point.lineIndicesPair.second));
                if(firstSlop > secondSlop){
                    lowerConstraintSet.setBad(point.lineIndicesPair.first);
                }else if(firstSlop < secondSlop){
                    lowerConstraintSet.setBad(point.lineIndicesPair.second);
                }
            }
        }
        break;
    case LESS:
        for(IntersectionPoint point: lowerBoundaryIntersections){
            if(point.X > xMedian){
                float firstSlop = getSlop(lowerConstraintSet.getOneByIndex(point.lineIndicesPair.first));
                float secondSlop = getSlop(lowerConstraintSet.getOneByIndex(point.lineIndicesPair.second));
                if(firstSlop < secondSlop){
                    lowerConstraintSet.setBad(point.lineIndicesPair.first);
                }else if(firstSlop > secondSlop){
                    lowerConstraintSet.setBad(point.lineIndicesPair.second);
                }
            }
        }
        break;
    }
}


void pruneConstraintsUpper( ConstraintSet &upperConstraintSet, float xMedian, vector<IntersectionPoint> upperBoundaryIntersections, CompareToOpt e ){ switch(e){ case GREATER: for(IntersectionPoint point: upperBoundaryIntersections){ if(point.X > xMedian){ float firstSlop = getSlop(upperConstraintSet.getOneByIndex(point.lineIndicesPair.first)); float secondSlop = getSlop(upperConstraintSet.getOneByIndex(point.lineIndicesPair.second)); if(firstSlop < secondSlop){ upperConstraintSet.setBad(point.lineIndicesPair.first); }else if(firstSlop > secondSlop){ upperConstraintSet.setBad(point.lineIndicesPair.second); } } } break; case LESS: for(IntersectionPoint point: upperBoundaryIntersections){ if(point.X > xMedian){ float firstSlop = getSlop(upperConstraintSet.getOneByIndex(point.lineIndicesPair.first)); float secondSlop = getSlop(upperConstraintSet.getOneByIndex(point.lineIndicesPair.second)); if(firstSlop > secondSlop){ upperConstraintSet.setBad(point.lineIndicesPair.first); }else if(firstSlop < secondSlop){ upperConstraintSet.setBad(point.lineIndicesPair.second); } } } break; } }

Aucun commentaire:

Enregistrer un commentaire