Opened 5 years ago

Closed 5 years ago

#1855 closed enhancement (done)

Implement the linear assignment problem

Reported by: abeham Owned by: gkronber
Priority: medium Milestone: HeuristicLab 3.3.7
Component: Problems.LinearAssignment Version: 3.3.7
Keywords: Cc:

Description

The linear assignment problem finds the minimum assignment of N jobs to N workers given a matrix of costs, e.g.

Workers \ Jobs Wash car Clean house Repair roof
Joe $10 $8 $15
Frank $5 $6 $12
Mark $8 $5 $10

An optimal solution in this case would be to let Joe do the house cleaning, Frank washes the car and Mark repairs the roof.

The LAP can be solved to optimality by the Hungarian algorithm in O(n3). This algorithm is to be implemented as well.

Change History (13)

comment:1 Changed 5 years ago by abeham

  • Owner changed from swagner to abeham
  • Status changed from new to accepted

comment:2 Changed 5 years ago by abeham

r7873:

  • Added linear assignment problem (LAP)
  • Added solver (+unit test)
  • Added dependencies in HeuristicLab-3.3 project

comment:3 Changed 5 years ago by abeham

  • Component changed from ### Undefined ### to Problems.LinearAssignment

comment:4 Changed 5 years ago by abeham

r7874: fixed build

comment:5 Changed 5 years ago by abeham

r8022:

  • Transformed LAP into a SingleObjectiveHeuristicOptimizationProblem
  • Added HungarianAlgorithm as separate algorithm for solving the problem

comment:6 Changed 5 years ago by abeham

r8057: corrected references

Nooooooooo!

comment:7 Changed 5 years ago by abeham

r8093:

  • Added possibility to name row and column in matrix (to have more interpretable results)
  • Added a "standard" assignment problem

comment:8 Changed 5 years ago by abeham

  • Owner changed from abeham to gkronber
  • Status changed from accepted to reviewing

r8094: Added plugin-dependency

comment:9 Changed 5 years ago by gkronber

Andreas, I found a few issues in the review. I put the important issues in bold font. Please review my comments and change the code if necessary.

User Interface

  • Does it have the look and feel of HeuristicLab?
    • yes.
  • Is it understandable, does the user know what to do?
    • yes.
  • Are appropriate controls used?
    • yes.
  • Are controls correctly locked/set readonly?
    • in SetEnabledStateOfControls only the assignmentDataGridView is enabled/disabled. The assignmentViewHost is not disabled/enabled.
  • Is it responsive?
    • yes

Functionality

  • Are important features missing?
    • no
  • Are there additional interesting features (maybe for later)?
    • Sorry, I didn't research this, but considering that this is a straight-forward basic algorithm I believe that there are no additional features.
  • If it is a storable item, can it be correctly saved and loaded?
    • I couldn't save a Hungarian Algorithm and the Linear Assignment Problem through the GUI
    • The solution could be saved and restored successfully.
  • Are/should unit tests be included?
    • A unit test with three different examples is included.
  • Is the impact of the change appropriate?
    • I guess so.
  • Is the feature implemented in the right plugin?
    • yes.
  • Is it fast enough?
    • yes.

Code

  • Does the code follow the DevelopersGuidelines (style, naming conventions, etc.) and the DevelopersBestPractices?
    • In general: yes.
    • the property ReactOnValueToStringChangedAndValueItemImageChanged is set explicitly to false for parameters of the problem
    • A general PropertyChanged event is used for communication between content and view.
  • Are suitable class, property and parameter names used?
    • yes
  • Is the code understandable or is there an appropriate comment?
    • the code is very readable and well documented.
  • Is backwards compatibility maintained?
    • not applicable
  • Is the code written according to already used concepts?
    • yes
  • Are existing components reused and/or is the code written in a way that it can be easily reused by other components?
    • yes
  • Were common pitfalls avoided (missing event handler registration in AfterDeserializationHook, missing members in cloning constructor)?
    • columnNames and rowNames are not cloned in LAPAssignment
    • AfterDeserialization attribute is directly added to the AttachEventHandlers method in HungarianAlgorithm.
  • Do the common unit tests pass?
    • yes
  • Are the classes well designed?
    • yes
  • Are the code files well structured?
    • yes

Documentation

  • Is it correct and up to date?
    • yes
  • Is important information missing?
    • no
  • Is the style consistent with the rest of the documentation?
    • yes
  • Is it short enough?
    • yes

comment:10 Changed 5 years ago by gkronber

  • Owner changed from gkronber to abeham
  • Status changed from reviewing to assigned

The artificial example with the resources human, von-neumann, quantum computer is strange.

comment:11 Changed 5 years ago by abeham

  • Owner changed from abeham to gkronber
  • Status changed from assigned to reviewing

r8183:

  • Added IStorableContent to HungarianAlgorithm, LinearAssignmentProblem, and LAPAssignment (it was only storable, because the result is storable)
  • Added separate AfterDeserialization hook and renamed AttachEventHandlers to RegisterEventHandlers
  • Added cloning of rowNames and columnNames in LAPAssignment
  • Changed the default instance of the LinearAssignmentProblem to a real-world example

Regarding your comment:

  • In SetEnabledStateOfControls only the assignmentDataGridView is enabled/disabled. The assignmentViewHost is not disabled/enabled.
    • The ViewHost is an AsynchronousContentView which is ReadOnly'ed and Locked by the View, and ContentView base classes through PropagateStateChanges.

Thanks for the thorough review. Please set as readytorelease if you think the changes are okay and you have no further comments.

Last edited 5 years ago by abeham (previous) (diff)

comment:12 Changed 5 years ago by gkronber

  • Status changed from reviewing to readytorelease

comment:13 Changed 5 years ago by gkronber

  • Resolution set to done
  • Status changed from readytorelease to closed
  • Version changed from 3.3.6 to 3.3.7
Note: See TracTickets for help on using tickets.