Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

Solve an assignment problem #1

Open
gocklkatz opened this issue Jul 5, 2024 · 7 comments
Open

Solve an assignment problem #1

gocklkatz opened this issue Jul 5, 2024 · 7 comments
Assignees
@gocklkatz

Comments

@gocklkatz
Copy link
Owner

gocklkatz commented Jul 5, 2024 •
edited
Loading

Implement and solve a balanced assignment problem in Java
@gocklkatz gocklkatz changed the title Solve a simple quadratic assignment problem Solve a simple assignment problem Jul 6, 2024
@gocklkatz gocklkatz changed the title Solve a simple assignment problem Solve an assignment problem Jul 6, 2024
@gocklkatz
Copy link
Owner Author

gocklkatz commented Jul 7, 2024 •
edited
Loading

Approach 1: Brute force. n! permutations
https://www.geeksforgeeks.org/job-assignment-problem-using-branch-and-bound

gocklkatz pushed a commit that referenced this issue Jul 7, 2024
#1 Intitial creation of AssignmentProblem class
5332c2e
@gocklkatz
Copy link
Owner Author

Approach 2: Greedy algorithm (heuristic)
https://en.wikipedia.org/wiki/Assignment_problem

@gocklkatz
Copy link
Owner Author

Generate sample instances of size n

@gocklkatz gocklkatz self-assigned this Jul 7, 2024
@gocklkatz
Copy link
Owner Author

Implement permutation generation and balanced assignment problem solver with arrays

@gocklkatz
Copy link
Owner Author

n > 10: generateApSample(n) -> OutOfMemoryError: Java heap space :)

@gocklkatz
Copy link
Owner Author

Find existing problem sets with optimal solution on the internet

@gocklkatz
Copy link
Owner Author

StopWatch for optimization runs

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees

@gocklkatz gocklkatz

Labels
None yet
Projects
None yet
Milestone
No milestone
Development

No branches or pull requests
1 participant
@gocklkatz