private PlanString buildPlanString(final IncompatiblePlansIdentifier incompatiblePlans,final ForbidenPlanStrings forbidenCombinations,final List<PersonRecord> personsStillToAllocate,final Set<Id> allocatedIncompatibilityGroups,final PlanString str,final double minimalWeightToObtain){
  final FeasibilityChanger feasibilityChanger=new FeasibilityChanger();
  final List<PersonRecord> remainingPersons=new ArrayList<PersonRecord>(personsStillToAllocate);
  final PersonRecord currentPerson=remainingPersons.remove(0);
  tagLinkedPlansOfPersonAsInfeasible(currentPerson,feasibilityChanger);
  assert str == null || !str.containsPerson(currentPerson.person.getId());
  final List<PlanRecord> records=new ArrayList<PlanRecord>(currentPerson.plans);
  PlanString constructedString=null;
  final KnownBranches knownBranches=new KnownBranches(true);
  final FeasibilityChanger localFeasibilityChanger=new FeasibilityChanger();
  double lastWeight=Double.POSITIVE_INFINITY;
  for (  PlanRecord r : records) {
    assert lastWeight >= r.avgJointPlanWeight;
    lastWeight=r.avgJointPlanWeight;
    if (!r.isStillFeasible) {
      assert intersect(r.jointPlan.getIndividualPlans().keySet(),str);
      continue;
    }
    final Set<Id> incomp=incompatiblePlans.identifyIncompatibilityGroups(r.plan);
    if (!Collections.disjoint(allocatedIncompatibilityGroups,incomp)) {
      continue;
    }
    final Set<Id<Person>> cotravelers=r.jointPlan == null ? Collections.<Id<Person>>emptySet() : r.jointPlan.getIndividualPlans().keySet();
    if (knownBranches.isExplored(cotravelers,incomp))     continue;
    knownBranches.tagAsExplored(cotravelers,incomp);
    PlanString tail=str;
    List<PersonRecord> actuallyRemainingPersons=remainingPersons;
    if (r.jointPlan != null) {
      assert !intersect(r.jointPlan.getIndividualPlans().keySet(),str);
      tail=getOtherPlansAsString(r,tail);
      actuallyRemainingPersons=filter(remainingPersons,r.jointPlan);
      tagLinkedPlansOfPartnersAsInfeasible(r,localFeasibilityChanger);
    }
    PlanString newString;
    if (!actuallyRemainingPersons.isEmpty()) {
      final Set<Id> newIncomp=new HashSet<Id>(allocatedIncompatibilityGroups);
      newIncomp.addAll(incomp);
      newString=buildPlanString(incompatiblePlans,forbidenCombinations,actuallyRemainingPersons,newIncomp,new PlanString(r,tail),Math.max(minimalWeightToObtain,constructedString != null ? constructedString.getWeight() - EPSILON : Double.NEGATIVE_INFINITY));
    }
 else {
      newString=new PlanString(r,tail);
      if (forbidBlockingCombinations && forbidenCombinations.isForbidden(newString)) {
        newString=null;
      }
    }
    localFeasibilityChanger.resetFeasibilities();
    if (newString == null)     continue;
    if (constructedString == null || newString.getWeight() > constructedString.getWeight()) {
      constructedString=newString;
    }
  }
  feasibilityChanger.resetFeasibilities();
  return constructedString;
}

private PlanString buildPlanString ( final IncompatiblePlansIdentifier incompatiblePlans , final ForbidenPlanStrings forbidenCombinations , final List < PersonRecord > personsStillToAllocate , final Set < Id > allocatedIncompatibilityGroups , final PlanString str , final double minimalWeightToObtain ) { final FeasibilityChanger feasibilityChanger = new FeasibilityChanger ( ) ; final List < PersonRecord > remainingPersons = new ArrayList < PersonRecord > ( personsStillToAllocate ) ; final PersonRecord currentPerson = remainingPersons . remove ( 0 ) ; tagLinkedPlansOfPersonAsInfeasible ( currentPerson , feasibilityChanger ) ; assert str == null || ! str . containsPerson ( currentPerson . person . getId ( ) ) ; final List < PlanRecord > records = new ArrayList < PlanRecord > ( currentPerson . plans ) ; PlanString constructedString = null ; final KnownBranches knownBranches = new KnownBranches ( true ) ; final FeasibilityChanger localFeasibilityChanger = new FeasibilityChanger ( ) ; double lastWeight = Double . POSITIVE_INFINITY ; for ( PlanRecord r : records ) { assert lastWeight >= r . avgJointPlanWeight ; lastWeight = r . avgJointPlanWeight ; if ( ! r . isStillFeasible ) { assert intersect ( r . jointPlan . getIndividualPlans ( ) . keySet ( ) , str ) ; continue ; } final Set < Id > incomp = incompatiblePlans . identifyIncompatibilityGroups ( r . plan ) ; if ( ! Collections . disjoint ( allocatedIncompatibilityGroups , incomp ) ) { continue ; } final Set < Id < Person > > cotravelers = r . jointPlan == null ? Collections . < Id < Person > > emptySet ( ) : r . jointPlan . getIndividualPlans ( ) . keySet ( ) ; if ( knownBranches . isExplored ( cotravelers , incomp ) ) continue ; knownBranches . tagAsExplored ( cotravelers , incomp ) ; PlanString tail = str ; List < PersonRecord > actuallyRemainingPersons = remainingPersons ; if ( r . jointPlan != null ) { assert ! intersect ( r . jointPlan . getIndividualPlans ( ) . keySet ( ) , str ) ; tail = getOtherPlansAsString ( r , tail ) ; actuallyRemainingPersons = filter ( remainingPersons , r . jointPlan ) ; tagLinkedPlansOfPartnersAsInfeasible ( r , localFeasibilityChanger ) ; } PlanString newString ; if ( ! actuallyRemainingPersons . isEmpty ( ) ) { final Set < Id > newIncomp = new HashSet < Id > ( allocatedIncompatibilityGroups ) ; newIncomp . addAll ( incomp ) ; newString = buildPlanString ( incompatiblePlans , forbidenCombinations , actuallyRemainingPersons , newIncomp , new PlanString ( r , tail ) , Math . max ( minimalWeightToObtain , constructedString != null ? constructedString . getWeight ( ) - EPSILON : Double . NEGATIVE_INFINITY ) ) ; } else { newString = new PlanString ( r , tail ) ; if ( forbidBlockingCombinations && forbidenCombinations . isForbidden ( newString ) ) { newString = null ; } } localFeasibilityChanger . resetFeasibilities ( ) ; if ( newString == null ) continue ; if ( constructedString == null || newString . getWeight ( ) > constructedString . getWeight ( ) ) { constructedString = newString ; } } feasibilityChanger . resetFeasibilities ( ) ; return constructedString ; }
recursively decends in the tree of possible joint plans .
