[UniTime-cvs] UniTime/JavaSource/org/unitime/timetable/solver/interactive Suggestions.java, 1.3, 1.4

[Tomas M. <to...@us...>]

Update of /cvsroot/unitime/UniTime/JavaSource/org/unitime/timetable/solver/interactive
In directory ddv4jf1.ch3.sourceforge.com:/tmp/cvs-serv12640/JavaSource/org/unitime/timetable/solver/interactive

Modified Files:
	Suggestions.java 
Log Message:
Suggestions (Interactive Solver)
- following improvements have been implemented:
  - order values (placements) by their impact on the objective function
  - bound improved (estimate the solution value by taking the best possible value for unresolved variables)

Index: Suggestions.java
===================================================================
RCS file: /cvsroot/unitime/UniTime/JavaSource/org/unitime/timetable/solver/interactive/Suggestions.java,v
retrieving revision 1.3
retrieving revision 1.4
diff -C2 -d -r1.3 -r1.4
*** Suggestions.java	17 Jun 2008 21:24:56 -0000	1.3
--- Suggestions.java	23 Dec 2008 16:37:52 -0000	1.4
***************
*** 27,30 ****
--- 27,31 ----
  import org.unitime.timetable.solver.interactive.Suggestion;
  
+ import net.sf.cpsolver.coursett.heuristics.TimetableComparator;
  import net.sf.cpsolver.coursett.model.*;
  import net.sf.cpsolver.ifs.solver.*;
***************
*** 261,276 ****
      }
      
!     private Vector values(Lecture lecture) {
      	if (lecture.equals(iLecture)) {
-     		Vector vals = new Vector();
      		for (Enumeration e=(lecture.allowBreakHard() || !iAllowBreakHard?lecture.values():lecture.computeValues(true)).elements();e.hasMoreElements();) {
      			Placement p = (Placement)e.nextElement();
!     			if (match(p)) vals.add(p);
      		}
-     		return vals;
      	} else {
!     		if (lecture.allowBreakHard() || !iAllowBreakHard) return lecture.values();
!     		return lecture.computeValues(true);
      	}
      }
      
--- 262,284 ----
      }
      
!     private TreeSet<PlacementValue> values(Lecture lecture) {
!     	TreeSet<PlacementValue> vals = new TreeSet();
      	if (lecture.equals(iLecture)) {
      		for (Enumeration e=(lecture.allowBreakHard() || !iAllowBreakHard?lecture.values():lecture.computeValues(true)).elements();e.hasMoreElements();) {
      			Placement p = (Placement)e.nextElement();
!     			if (match(p)) vals.add(new PlacementValue(p));
      		}
      	} else {
!     		if (lecture.allowBreakHard() || !iAllowBreakHard) {
!     			for (Enumeration e=lecture.values().elements();e.hasMoreElements();) {
!     				vals.add(new PlacementValue((Placement)e.nextElement()));
!     			}
!     		} else {
!     			for (Enumeration e=lecture.computeValues(true).elements();e.hasMoreElements();) {
!     				vals.add(new PlacementValue((Placement)e.nextElement()));
!     			}
!     		}
      	}
+     	return vals;
      }
      
***************
*** 287,290 ****
--- 295,299 ----
  
      private void backtrack(long startTime, Vector initialLectures, Vector resolvedLectures, Hashtable conflictsToResolve, Hashtable initialAssignments, int depth) {
+         iNrCombinationsConsidered++;
          int nrUnassigned = conflictsToResolve.size();
          if ((initialLectures==null || initialLectures.isEmpty()) && nrUnassigned==0) {
***************
*** 302,311 ****
              return;
          }
          for (Enumeration e1=(initialLectures!=null && !initialLectures.isEmpty()?initialLectures.elements():conflictsToResolve.keys());e1.hasMoreElements();) {
              Lecture lecture = (Lecture)e1.nextElement();
              if (resolvedLectures.contains(lecture.getClassId())) continue;
              resolvedLectures.add(lecture.getClassId());
!             for (Enumeration e2=values(lecture).elements();e2.hasMoreElements();) {
!                 Placement placement = (Placement)e2.nextElement();
                  if (placement.equals(lecture.getAssignment())) continue;
                  if (!iAllowBreakHard && placement.isHard()) continue;
--- 311,324 ----
              return;
          }
+         if (iSuggestions.size()==iLimit && ((Suggestion)iSuggestions.last()).getValue()<getBound(conflictsToResolve)) {
+         	return; //BOUND
+         }
          for (Enumeration e1=(initialLectures!=null && !initialLectures.isEmpty()?initialLectures.elements():conflictsToResolve.keys());e1.hasMoreElements();) {
              Lecture lecture = (Lecture)e1.nextElement();
              if (resolvedLectures.contains(lecture.getClassId())) continue;
              resolvedLectures.add(lecture.getClassId());
!             for (Iterator e2=values(lecture).iterator();e2.hasNext();) {
!                 PlacementValue placementValue = (PlacementValue)e2.next();
!                 Placement placement = placementValue.getPlacement();
                  if (placement.equals(lecture.getAssignment())) continue;
                  if (!iAllowBreakHard && placement.isHard()) continue;
***************
*** 320,324 ****
                      if (ini!=null && !placement.sameRooms(ini)) continue;
                  }
-                 iNrCombinationsConsidered++;
                  Set conflicts = iModel.conflictValues(placement);
                  if (conflicts!=null && (nrUnassigned+conflicts.size()>depth)) continue;
--- 333,336 ----
***************
*** 434,436 ****
--- 446,475 ----
              "}";
      }
+     
+     public double getBound(Hashtable conflictsToResolve) {
+     	TimetableComparator cmp = (TimetableComparator)iSolver.getSolutionComparator();
+     	double value = cmp.currentValue(iSolver.currentSolution());
+     	for (Enumeration e=conflictsToResolve.keys();e.hasMoreElements();) {
+     		Lecture lect = (Lecture)e.nextElement();
+     		PlacementValue val = values(lect).first();
+     		value += val.getValue();
+     	}
+     	return value;
+     }
+     
+     public class PlacementValue implements Comparable<PlacementValue> {
+     	private Placement iPlacement;
+     	private double iValue;
+     	public PlacementValue(Placement placement) {
+     		iPlacement = placement;
+     		iValue = ((TimetableComparator)iSolver.getSolutionComparator()).value(placement, iSolver.getPerturbationsCounter());
+     	}
+     	public Placement getPlacement() { return iPlacement; }
+     	public double getValue() { return iValue; }
+     	public int compareTo(PlacementValue p) {
+     		int cmp = Double.compare(getValue(), p.getValue());
+     		if (cmp!=0) return cmp;
+     		return Double.compare(getPlacement().getId(), p.getPlacement().getId());
+     	}
+     }
  }