assignment problem constrained

CS 2110: Object-Oriented Programming and Data Structures

Assignment 1.

A1 consists of a series of exercises to help you transition to procedural programming in the Java language. The problem-solving elements are at the level of lab exercises from CS 1110/1112. The assignment comes bundled with a thorough test suite, so you will know when you have implemented each method’s specifications correctly.

You must work on this assignment independently (no partners)—we want to ensure that every student can write, test, and submit Java code on their own. For this reason, we are also grading this assignment for mastery ; if a grader identifies mistakes that you didn’t catch yourself, you may resubmit once to correct them without penalty.

Learning objectives

• Author Java code in the IntelliJ IDEA IDE.
• Employ operations on Java’s primitive types ( boolean , int , double ) and strings to solve high-level problems.
• Employ Java control structures ( if , for , while ) to implement algorithms for solving high-level problems.
• Select relevant mathematical functions from Java’s standard library by referencing JavaDoc pages.
• Verify the correctness of implementations by running JUnit test cases.
• Adopt good programming style to facilitate readability and maintenance.
• Witness examples of precise method specifications that separate “what” from “how”.

If you are worried that these exercises seem a bit dry and mathematical, that is a consequence of restricting ourselves to Java’s primitive types (which are mostly numbers). Once we get to object-oriented programming in A2, the problem domains will become richer.

Collaboration policy

This assignment is to be completed as an individual. You may talk with others to discuss Java syntax, debugging tips, or navigating the IntelliJ IDE, but you should refrain from discussing algorithms that might be used to solve the problems, and you must never show your in-progress or completed code to another student. Consulting hours are the best way to get individualized assistance at the source code level.

Frequently asked questions

There is a pinned post on Ed where we will post any clarifications for this assignment. Please review it before asking a new question in case your concern has already been addressed. You should also review the FAQ before submitting to see whether there are any new ideas that might help you to improve your solution.

I. Getting started

You already know at least one procedural language (e.g. Python) with which you should be able to solve the problems on this assignment. If that language is not Java, then the goal is for you to become comfortable with procedural Java syntax, as it compares with what you already know, by practicing it in targeted problems. Start by reading transition to Java on the course website, which provides a focused translation guide between Python, MATLAB, and Java.

Download the release code from the CMSX assignment page; it is a ZIP file named “a1-release.zip”. Decide where on your computer’s disk you want your project to be stored (we recommend a “CS2110” directory under your home or documents folder), then extract the contents of the ZIP file to that directory. Find the folder simply named “a1” (depending on your operating system, this may be under another folder named “a1-release”); its contents should look like this:

We assume you have already followed the setup instructions for IntelliJ, possibly in your first discussion section. It is important that JDK 21 has been downloaded.

In IntelliJ, select File | Open , then browse to the location of this “a1” directory, highlight “a1”, and click OK . IntelliJ may ask whether you want to open the project in the same window or a new one; this is up to you, noting that if you choose the same window, whatever project you previously had open (e.g. a discussion activity or old assignment) will be closed.

Please keep track of how much time you spend on this assignment. There is a place in “reflection.txt” for reporting this time, along with asserting authorship.

II. Working with the provided code

Specifications and preconditions.

A recurring theme in this course is distinguishing between the roles of client and implementer . For methods, a client is someone who calls a method, and the implementer is someone who writes the method’s body. Although you might act both as client and implementer in a small project, ideally the two roles have no knowledge of one another, so you should keep track of which role you are currently in and “split your brain” accordingly. For most of this assignment you will be in the implementer role relative to the assignment’s methods.

Each method is accompanied by a specification in a JavaDoc comment. As the implementer, your job is to write a method body that fulfills that specification. Specifications may include a precondition phrased as a “requires” clause. As the implementer, you can assume that the precondition is already satisfied. You do not have to attempt to check the precondition or to handle invalid arguments in any special way. It would be the responsibility of clients to ensure that they do not violate such conditions.

For example, if a specification contains the precondition “ nTerms is non-negative”, then the client is never permitted to pass negative arguments to the function. If the client nonetheless does so, the specification promises nothing about the result. Specifically, the specification does not promise that the function will check for non-negativity, and the specification does not promise that any kind of error will be produced. That means the implementer has an easy job: they can simply ignore the possibility of negative arguments.

You might have been taught in previous programming classes that implementers must always check preconditions, or must always produce an error when a precondition is violated. Those are useful and important defensive programming techniques! (And we will see how to employ them in Java soon.) But the point we are making here is that they are not mandated by a “requires” clause. So in this assignment, you do not have to use such techniques, and it’s likely to be easier for you to omit them entirely.

Replacing method “stubs”

The body of each method initially looks like this:

This is a placeholder —it allows the method to compile even though it doesn’t return a value yet, but it will cause any tests of the method to fail. You should delete these lines as the first step when implementing each method. (We’ll discuss the meaning of these lines later in the course when we cover exceptions, objects, and so forth.)

Use the TODO comments to guide you to work that still needs to be done. As you complete each task, remove the comment line with the TODO since it doesn’t need doing anymore! Temporary comment prefixes like TODO and FIXME are a convenient way to keep track of your progress when writing and debugging code; IntelliJ will even track them for you in its TODO window .

Finally, some method bodies contain comments with “implementation constraints.” These are not part of the specification, as they do not affect potential clients. Instead, they are requirements of the assignment to ensure that you get practice with the necessary skills. Violating these constraints will not cause unit tests to fail, but points will be deducted by your grader, so make sure you obey them.

Test cases for each method are in “tests/cs2110/A1Test.java”. You are encouraged to read the test suites to see what corner cases are considered, but you do not need to add any tests of your own for this assignment.

To run a test case, click the green arrow to the left of the method name, then select “Run”; the results will be shown at the bottom of the screen. To run all test cases, use the arrow to the left of the class name ( A1Test ). If a test fails with a yellow “X”, that means it returned the wrong result. By reading the messages in the output window, you should be able to determine which case failed and what your implementation computed instead. If it fails with a red “!”, that means it encountered an error (or you forgot to delete the placeholder throw line).

Take note of the style of these tests. While you may not understand all of the Java syntax yet, you should see that related tests are grouped together and given descriptive names. This makes it easier to debug your code, since your IDE will clearly show which scenarios are behaving as expected and which are not. You are expected to adopt this style for your own tests on future assignments.

III. Assignment walkthrough

Implement the methods one at a time. As soon as you implement one, run the corresponding test case to verify your work. Do not modify any method signatures (or return types or throws clauses)—not only would that change the class type we provided, but it would make it impossible for our autograder to interoperate with your code. And do not leave print statements in your final submission unless the method specification mentions printing output as a side effect.

Each of the numbered exercises below references a section of the Supplement 1 chapter of the primary course textbook, Data Structures and Abstraction with Java , 5th edition, to which you should have access in Canvas through the “Course Materials” link. That supplement is designed to help students who know how to program, but are new to Java. It is a great resource for making the transition to Java.

1. Regular polygons

[Textbook: S1.29: The Class Math ]

The area of a regular polygon with n sides of length s is given by the formula:

$$A = \frac{1}{4} s^2 \frac{n}{\tan(\pi/n)}$$

Implement this formula. You will need one or more math functions and/or constants from Java’s standard library. Skim the JavaDoc page for the static methods in the Math class to learn which functions are available. Remember that a Math. prefix is required when calling them (so to compute the absolute value of -5, you would write Math.abs(-5) ).

Take some time to explore these functions and get a feel for how Java’s standard library is documented. The functions you are most likely to use later in the course include: abs() , min() , max() , sqrt() , pow() , and the trigonometric functions.

Note: methods dealing with dimensionful quantities (like length and area) should always say something about what units (e.g. meters, acres) those quantities are measured in. In this case, the formula makes no assumptions about units, so the specification simply tells the client that the units of the output are compatible with the units of the input.

2. Collatz sequence

[Textbook: S1.59: The while Statement]

The Collatz conjecture is a fun piece of mathematical trivia: by repeatedly performing one of two simple operations on a positive integer (depending on whether it is even or odd), you always seem to get back to 1. The rules for determining the next number in the sequence are:

• If the last number was even, divide it by 2.
• If the last number was odd, multiply it by 3 and add 1.

Our objective is to sum all of the terms in the sequence starting from a given “seed” number until we get to 1. This involves indefinite iteration , and you should use a while loop for this.

This is also a chance to practice problem decomposition and defining new methods. Declare and implement a method named nextCollatz() that takes one int argument and returns an int value according to the given specification. When you have done this, remove the TODO and uncomment the relevant test case in A1Test (it was commented out because the test case will not compile unless that method is at least declared, preventing you from running tests for other methods in the suite). Tip: there is an IntelliJ keyboard shortcut for commenting and uncommenting whole selections of code; can you find it?

3. Median of three

[Textbook: S1.38: The if-else Statement]

The median value of a collection of numbers is the value that would be in the middle if the collection were sorted. A special case is median-of-three voting , which is used in fault-tolerant systems to decide how to proceed when not all components agree. This small function is actually one of the most commonly-run procedures in SpaceX’s flight software, helping it determine which sensors and commands to trust dozens of times per second.

You need to develop an algorithm for determining which of three numbers is the middle value. The numbers could be in any order, and there could be duplicates. Use a chain of conditional statements ( if / else ), possibly nested, to find the middle value.

4. Interval overlaps

[Textbook: S1.41: Boolean Expressions]

Intervals are a useful abstraction when working with schedules. For example, if class meeting times are represented as intervals over the seconds of a day, then an overlap would imply that two classes conflict.

This exercise is designed to help you avoid a common “anti-pattern” among new programmers:

(here, expr is a Boolean expression, like x > 0 ). Remember that the conditions used in if statements are expressions that yield a boolean value and can be used anywhere a boolean value like true or false could be used. Therefore, the above code can (and should) be rewritten as:

Keeping this in mind, implement intervalsOverlap() using a single return statement.

5. Estimating pi

[Textbook: S1.61: The for Statement]

The Madhava-Leibniz series is an infinite sum of numbers that is related to π:

$$\frac{\pi}{4} = 1 - \frac{1}{3} + \frac{1}{5} - \frac{1}{7} + \frac{1}{9} - \ldots$$

Observe that the denominators of the terms are the sequence of odd integers and that the sign alternates between plus and minus.

By truncating this series after a finite number of terms, we get an approximation for π (though this particular formula requires many terms for even modest accuracy). Use a for -loop to evaluate this approximation for a specified number of terms (this is an example of definite iteration ). Recall that integer division in Java rounds down to another integer, so you may need to cast some numbers to a floating-point type when evaluating the fractions.

As a corner case, note that the sum of zero terms is 0.

6. Palindromes

[Textbook: S1.67: The Class String ]

With control structures and primitive types out of the way, it’s time to get some experience with our first aggregate type : String (an aggregate type is one that groups together multiple values, like how a String contains multiple char s). Strings get some special treatment in Java; while they are objects , they are immutable (their contents can’t be changed), which means they behave much like primitive values. And unlike other objects, they have their own literals and even an operator ( + for concatenation). But as a sequence of characters they are like arrays, giving you some early practice with algorithms that iterate over data.

A palindrome has the same sequence of characters when written backwards as when written normally. To examine the i th character in string s , use s.charAt(i) . The total number of characters in s is given by s.length() . In Java, the index of the first character is 0 , and the index of the last character is s.length() - 1 . The specifications for these methods are in the API documentation for String ; by calling them, you are now in the client role with respect to the String class.

7. Formatting messages

[Textbook: S1.70: Concatenation of Strings]

A common task in computing systems is to format information to be read by humans. The system may need to support translations in multiple languages, and sometimes words will change depending on the data being explained (e.g. singular vs. plural nouns, “a” vs. “an” depending on the following word, etc.). To manage this potential complexity, it is a good idea to move formatting logic into its own function (Java actually provides a sophisticated infrastructure for managing this in large applications, but that is beyond the scope of this course).

This exercise requires you to concatenate strings and to format numerical data as a string. There are several approaches you can take; the + operator is probably most convenient, but if you have used a format or printf feature in another language, you might be interested in String ’s format() method. This is also a good opportunity to get practice with Java’s ternary operator ?: , an awkward-to-read but extremely useful bit of syntax; use this to decide between the singular and plural forms of “item” without using an if -statement.

8. Making a program

Now it’s time to step into the client role. Add a main() method so that the A1 class can be run as a program. Find a way to use at least four of the methods in A1 in combination, then print the final result. Is is okay to be silly here! Ideas include:

• Compute the sums of three Collatz sequences of your choice, then take their median; use this as the number of sides of a polygon. For the length of the polygon’s sides, use an estimate of π. Print the polygon’s area.
• Compute the median of three numbers of your choice, then find the next number in the Collatz sequence after it. Use this as the number of items in an order, then determine whether that order’s confirmation message is a palindrome.

You can be creative here and provide arbitrary inputs as necessary, but all four methods must contribute somehow to the final result. For this assignment, you should hard-code your inputs, rather than expecting program arguments (in other words, ignore args ).

Your program’s printed output should be a complete sentence written in English. It should describe what final operation was performed, what its inputs were, and what the result was (the inputs and outputs should not be baked into the printed text; instead, you should print the values of program variables or expressions). For example, “The area of a polygon with 4 sides of length 0.5 m is 0.25 m^2.” When you run your program, make sure this is the only output (i.e., that there are no “debugging prints” in the other methods you are calling).

9. Reflecting on your work

Stepping back and thinking about how you approached an assignment (a habit called metacognition ) will help you make new mental connections and better retain the skills you just practiced. Therefore, each assignment will ask you to write a brief reflection in a file called “reflection.txt”. This file is typically divided into three sections:

• Submitter metadata: Assert authorship over your work, and let us know how long the assignment took you to complete.
• Verification questions: These will ask for a result that is easily obtained by running your assignment. (Do not attempt to answer these using analysis; the intent is always for you to run your program, possibly provide it with some particular input, and copy its output.)
• Reflection questions: These will ask you write about your experience completing the assignment. We’re not looking for an essay, but we do generally expect a few complete sentences.

Respond to the four TODOs in “reflection.txt” (you can edit this file in IntelliJ).

IV. Scoring

This assignment is evaluated in the following categories (note: weights are approximate and may be adjusted slightly in final grading):

• Submitted and compiles (25%)
• Fulfills specifications (41%)
• Complies with implementation constraints (25%)
• Exhibits good code style (5%)
• Responds to reflection questions (4%)

You can maximize the “fulfilling specifications” portion of your score by passing all of the included unit tests (don’t forget to uncomment the ones for nextCollatz() ). The smoketester will also run these tests for you when you submit so you can be sure that your code works as well for us as it does for you.

Formatting is a subset of style. To be on the safe side, ensure that our style scheme is installed and that you activate “Reformat Code” before submitting. Graders will deduct for obvious violations that detract from readability, including improper indentation and misaligned braces.

But beyond formatting, choose meaningful local variable names, follow Java’s capitalization conventions (camelCase), and look for ways to simplify your logic. If the logic is subtle or the intent of a statement is not obvious, clarify with an implementation comment.

V. Submission

Upload your “A1.java” and “reflection.txt” files to CMSX before the deadline. If you forgot where your project is saved on your computer, you can right-click on “A1.java” in IntelliJ’s project browser and select “Open In”, then your file explorer (e.g. “Explorer” for Windows, “Finder” for Mac). Be careful to only submit “.java” files, not files with other extensions (e.g. “.class”).

After you submit, CMSX will automatically send your submission to a smoketester , which is a separate system that runs your solution against the same tests that we provided to you in the release code. The purpose of the smoketester is to give you confidence that you submitted correctly. You should receive an email from the smoketester shortly after submitting. Read it carefully, and if it doesn’t match your expectations, confirm that you uploaded the intended version of your file (it will be attached to the smoketester feedback). Be aware that these emails occasionally get misclassified as spam, so check your spam folder. It is also possible that the smoketester may fall behind when lots of students are submitting at once. Remember that the smoketester is just running the same tests that you are running in IntelliJ yourself, so don’t panic if its report gets lost—we will grade all work that is submitted to CMSX, whether or not you receive the email.

(Note: it may take us a day after the assignment is released before the smoketester is up and running.)

Stack Exchange Network

Stack Exchange network consists of 183 Q&A communities including Stack Overflow , the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Q&A for work

Connect and share knowledge within a single location that is structured and easy to search.

How can I solve this constrained assignment problem?

The assignment problem is defined as follows:

There are a number of agents and a number of tasks. Any agent can be assigned to perform any task, incurring some cost that may vary depending on the agent-task assignment. It is required to perform all tasks by assigning exactly one task to each agent in such a way that the total cost of the assignment is minimized.

The number of tasks is larger than the number of agents.

My problem statement though imposes an additional constraint on the above.

Each task belongs to exactly one 'category'. Each 'category' has an associated maximum number of tasks that can be assigned. Enforce this constraint on the earlier definition.

For a layman's example, consider this -

A restaurant serves n customers (agents), and has on it's menu m possible dishes (tasks), with m > n. Each customer gives his preference for each of the m dishes, which is the cost for this particular assignment problem. Find a solution which minimizes cost i.e. which gives each customer a dish that is as high on their preference as possible. Additionally, each dish belong to a certain cuisine (category). The restaurant can only make a certain number of dishes per cuisine. Enforce this constraint on the problem above.

I understand that this is a very specific problem, but any help would be appreciated.

I am currently solving the first part of the problem using the Hungarian Algorithm for assignment.

• optimization
• combinatorics
• assignment-problem

• 2 $\begingroup$ You should be able to reformulate this as a Maximum-Flow Problem $\endgroup$ –  Francesco Gramano Commented Jan 15, 2015 at 18:45

3 Answers 3

Introduce dummy variables with zero cost so that it becomes a balanced assignment, which can be solved with Hungarian Algorithm .

• $\begingroup$ Does not work for the additional constraint. $\endgroup$ –  Rohan Sood Commented Jul 5, 2015 at 11:51

This can be formulated as an instance of minimum-cost flow problem . Have a graph with one vertex per agent, one vertex per task, and one vertex per category. Now add edges:

Add an edge from the source to each agent, with capacity 1 and cost 0.

Add an edge from each agent to each task, with capacity 1 and cost according to the cost of that assignment.

Add an edge from each task to the category it is part of, with capacity 1 and cost 0.

Add an edge from each category to the sink, with capacity given by the maximum number of tasks assignable in that category and cost 0.

Now find the minimum-cost flow of size $t$, where $t$ is the number of tasks. There are polynomial-time algorithms for that.

I know it is a bit late for an answer to that post. Maybe you should have closed it within a year of no relevant answer. The problem is not that easy, just with one additional constraint, there is a lot of work dealing with the problem. You can use branch and bound algorithm. In the branch and bound, there are different ways to proceed.

• 1 $\begingroup$ Could you please describe the branch and bound algorithm in detail? $\endgroup$ –  xskxzr Commented Sep 1, 2020 at 1:12
• $\begingroup$ it is tree like method, based on : 1) solving a relaxation of your problem,, a good relaxation (without some complicating constraints). 2) setting up a branching criteria (a way how you construct the subproblems). You have to manage with bounds, upper and lowers bounds. There are ways to fathom (cut it out) a vertex or branch of the tree according to the bounds. if it is a min problem, then a lower bound is determined by the value obtained by solving the relaxed problem, and an upper bound is the value of any feasible solution (that satisfies all the constraints of the initial problem). $\endgroup$ –  Rima Awhid Commented Sep 2, 2020 at 23:15

Your Answer

Sign up or log in, post as a guest.

Required, but never shown

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy .

Not the answer you're looking for? Browse other questions tagged algorithms optimization combinatorics assignment-problem or ask your own question .

• Featured on Meta
• Bringing clarity to status tag usage on meta sites
• Announcing a change to the data-dump process

Hot Network Questions

• Why is simpler prose more popular these days?
• Has a tire ever exploded inside the Wheel Well?
• Coding exercise to represent an integer as words using python
• The Fourth Daughter
• Gomoku game 5 in a row. Javascript simple game Canvas
• Does the order of ingredients while cooking matter to an extent that it changes the overall taste of the food?
• 70s-80s animation with an island of robots
• Where to donate foreign-language academic books?
• What are the 270 mitzvot relevant today?
• How can one be honest with oneself if one IS oneself?
• Compact symmetric spaces and sub-root systems
• Why does average of Monte Carlo simulations not hold for simple problem?
• How is message waiting conveyed to home POTS phone
• How can moral disagreements be resolved when the conflicting parties are guided by fundamentally different value systems?
• Who is the referent of "him" in Genesis 18:2?
• Overstayed Schengen but can I switch to US passport?
• magnetic boots inverted
• What unique phenomena would be observed in a system around a hypervelocity star?
• Held Action Sneak attack after action surge
• How is it possible to know a proposed perpetual motion machine won't work without even looking at it?
• Is 3 ohm resistance value of a PCB fuse reasonable?
• My supervisor wants me to switch to another software/programming language that I am not proficient in. What to do?
• Has the US said why electing judges is bad in Mexico but good in the US?
• How did Oswald Mosley escape treason charges?

• Google OR-Tools
• Español – América Latina
• Português – Brasil
• Tiếng Việt

Solving an Assignment Problem

This section presents an example that shows how to solve an assignment problem using both the MIP solver and the CP-SAT solver.

In the example there are five workers (numbered 0-4) and four tasks (numbered 0-3). Note that there is one more worker than in the example in the Overview .

The costs of assigning workers to tasks are shown in the following table.

The problem is to assign each worker to at most one task, with no two workers performing the same task, while minimizing the total cost. Since there are more workers than tasks, one worker will not be assigned a task.

MIP solution

The following sections describe how to solve the problem using the MPSolver wrapper .

Import the libraries

The following code imports the required libraries.

Create the data

The following code creates the data for the problem.

The costs array corresponds to the table of costs for assigning workers to tasks, shown above.

Declare the MIP solver

The following code declares the MIP solver.

Create the variables

The following code creates binary integer variables for the problem.

Create the constraints

Create the objective function.

The following code creates the objective function for the problem.

The value of the objective function is the total cost over all variables that are assigned the value 1 by the solver.

Invoke the solver

The following code invokes the solver.

Print the solution

The following code prints the solution to the problem.

Here is the output of the program.

Complete programs

Here are the complete programs for the MIP solution.

CP SAT solution

The following sections describe how to solve the problem using the CP-SAT solver.

Declare the model

The following code declares the CP-SAT model.

The following code sets up the data for the problem.

The following code creates the constraints for the problem.

Here are the complete programs for the CP-SAT solution.

Except as otherwise noted, the content of this page is licensed under the Creative Commons Attribution 4.0 License , and code samples are licensed under the Apache 2.0 License . For details, see the Google Developers Site Policies . Java is a registered trademark of Oracle and/or its affiliates.

Last updated 2024-08-28 UTC.

Stack Exchange Network

Stack Exchange network consists of 183 Q&A communities including Stack Overflow , the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Q&A for work

Connect and share knowledge within a single location that is structured and easy to search.

Constrained assignment problem (Linear Programming, Genetic Algorithm, etc...)

I'm looking for advice on how I should approach a specific problem. I have about 1000 shops that I have to assign to about 20 different supply centers out of a possible 28, and I'm trying to pick the best 20 (or less) centers that minimizes the overall distance between shops and supply centers.

I looked into the 'assignment problem' and how linear programming could help, but it seems this can only work if I have an equal number of shops and centers. I also looked into Genetic Algorithms and tried to code the algorithm to 1) ensure each shop is assigned to only one center and the center count must be no greater than 20, but results aren't that great (I can provide my R code if requested)

Should I continue trying to work with a Genetic Algorithm or can you folks suggest some other tool I should use or resource to look over? Thank you.

EDIT: Some nice user who's comment is now deleted suggested researching the Facility Location Problem . This seems more in line with what I'm looking for but most of the examples online cover single-facility problems, not multi-facility problems. Can anyone recommend a good resource for R or Python?

• optimization
• genetic-algorithms
• operations-research

EDIT: Apparently, I should have posted my original recommendation about the facility location problem as a reply to your question, not as an answer. I am new to the forum, but I get it now.

Any way, I believe your problem can be formulated as follows.

Let $y_i$ = 1 if supply center i is opened and 0 otherwise

$x_i,_j$ = 1 if supply center i feeds shop j and 0 otherwise

$c_i,_j$ = distance from supply center i to shop j

Then you want to solve the following linear programming problem.

    minimize  $\sum_i\sum_jc_i,_jx_i,_j$

    subject to $\sum_ix_i,_j = 1$                j = 1,...,1000 (or the number of shops you have)

                    $\sum_jx_i,_j \le 1000y_i$      i = 1,...,28 (If you have a max capacity for each supply center, use that number instead of 1000; 1000 assumes there is no max capacity so one center could feasibly supply all shops)

                    $\sum_iy_i \le 20$                 (max of 20 supply centers chosen)

                    $x_i,_j$ = 0 or 1                  i=1,...,28; j =1,...,1000

                    $y_i$ = 0 or 1                     i=1,...,14

The Rsymphony package in R can solve this problem for you. You will need a vector of the distances $c_i,_j$ and 0's for each $y_i$ as well as a matrix to take care of the constraints (the three summations starting after "subject to"). If you aren't familiar with the constraint matrix, each column contains the coefficients for that variable. The help file for the Rsymphony package has a couple examples that should help with that. Don't forget to include columns for the $y_i$ in the matrix as well. You will also need to set the $x_i,_j$ and $y_i$ to be binary by using

     types = "B"

As an example, suppose we have 3 shops and 2 supply centers with distances between them as $x_1,_1$ = 2.8, $x_1,_2$ = 5.4, $x_1,_3$ = 1.4, $x_2,_1$ = 4.2, $x_2,_2$ = 3.0, $x_2,_3$ = 6.3. Then

tells us that we should open both supply centers and supply center 1 will supply shops 1 and 3 and supply center 2 will supply shop 2, for a total distance of 7.2.

I hope this helps.

• 1 $\begingroup$ Actually, this is a very direct answer to the question that suggests the use of the RSymphony package for integer linear programming to solve the problem. These types of integer programming problems are actually quite easy to solve exactly, so there's no need to use an heuristic approach such as genetic algorithms. $\endgroup$ –  Brian Borchers Commented Feb 7, 2015 at 21:30
• $\begingroup$ @TAS thanks! Sorry for the late reply but I think this is exactly what I'm looking for! I'm going to test it out on my own data set and let you guys know soon. $\endgroup$ –  gtnbz2nyt Commented Feb 11, 2015 at 15:12
• $\begingroup$ Glad to hear. I think the most difficult part will be coming up with your constraint matrix. $\endgroup$ –  TAS Commented Feb 11, 2015 at 18:24
• $\begingroup$ @TAS Thanks a freaking million dude! It worked, and building the constraint matrix wasn't that hard once I took your example constraint matrix and broke it into different 'blocks' then binded them all together! $\endgroup$ –  gtnbz2nyt Commented Feb 12, 2015 at 18:21

Your Answer

Sign up or log in, post as a guest.

Required, but never shown

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy .

Not the answer you're looking for? Browse other questions tagged r optimization linear genetic-algorithms operations-research or ask your own question .

• Featured on Meta
• Announcing a change to the data-dump process
• Bringing clarity to status tag usage on meta sites

Hot Network Questions

• Which hash algorithms support binary input of arbitrary bit length?
• How much easier/harder would it be to colonize space if humans found a method of giving ourselves bodies that could survive in almost anything?
• Overstayed Schengen but can I switch to US passport?
• How can I get around 16 electrical receptacles in a small area with the least amount of wiring?
• Writing an i with a line over it instead of an i with a dot and a line over it
• Where to donate foreign-language academic books?
• Cannot open and HTML file stored on RAM-disk with a browser
• What is the purpose of these 33-ohm series resistors on the RMII side of the LAN8742A?
• Should you refactor when there are no tests?
• What is happening when a TV satellite stops broadcasting during an "eclipse"?
• I have some questions about theravada buddhism
• Has the US said why electing judges is bad in Mexico but good in the US?
• Why is simpler prose more popular these days?
• What unique phenomena would be observed in a system around a hypervelocity star?
• Can you use 'sollen' the same way as 'should' in sentences about possibility that something happens?
• How can I draw intersection of a sphere and a plane?
• magnetic boots inverted
• What are the 270 mitzvot relevant today?
• Rings demanding identity in the categorical context
• How is message waiting conveyed to home POTS phone
• Encode a VarInt
• Does it pay to put effort in fixing this problem or better reinstall Ubuntu 24.04 from scratch?
• 1960s Stylesheet/Format for working Physics problems
• My supervisor wants me to switch to another software/programming language that I am not proficient in. What to do?

Stack Exchange Network

Stack Exchange network consists of 183 Q&A communities including Stack Overflow , the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Q&A for work

Connect and share knowledge within a single location that is structured and easy to search.

Adding sequence constraints to the assignment problem- Python

This is an online assignment problem and yet can be considered as an assignment problem with a sequence. Assume that workers are coming into the system sequentially and I want to assign a task to them based on their cost for each task. I have set up the python model without the sequence constraint, I just couldn't figure out how to mandate the order: This example from the OR-Tools: In the example there are four workers (numbered 0-3) and four tasks (numbered 0-3).

The costs of assigning workers to tasks are shown in the following table.

The problem is to assign each worker to at most one task, with no two workers performing the same task while minimizing the total cost. Since there are more workers than tasks, one worker will not be assigned a task.

Assume that I want to force an order/ sequence. Say worker 0 has to be assigned first worker 2, then worker 3... So in practice:

• worker 0 assigned to task 3 (lowest cost)
• worker 1 assigned to task 0 (lowest cost)
• worker 2 assigned to task 2 (task 3 has the lowest cost but since it is already assigned to worker 0 it is not available)
• worker 3 assigned to task 1

MIP solution The following sections describe how to solve the problem using the MIP solver as an assignment problem without enforcing the order.

Import the libraries The following code imports the required libraries.

The following code declares the MIP solver.

The following code creates the data for the problem.

The following code creates binary integer variables for the problem.

The following code creates the constraints for the problem.

HERE I want to add another constraint(s) that forces the order

The following code creates the objective function for the problem.

The value of the objective function is the total cost over all variables that are assigned the value 1 by the solver.

Invoke the solver The following code invokes the solver and prints the solution.

• assignment-problem

• $\begingroup$ You posted data for 4 tasks and 4 resources whereas you mentioned workers are more than tasks, could you please explain and also what constraint you want to include ? Is it just that 1Task per worker or other constraints are there too ? And is objective that you want to minimize total cost of Tasks wrt workers they are assigned to (That's what I made out from explanation). And also what are problems you facing as you've included almost all the program so aren't you getting desired OP ? $\endgroup$ –  user3237357 Commented Sep 1, 2021 at 7:36

Know someone who can answer? Share a link to this question via email , Twitter , or Facebook .

Your answer, sign up or log in, post as a guest.

Required, but never shown

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy .

Browse other questions tagged python constraint scheduling or-tools assignment-problem or ask your own question .

• Featured on Meta
• Bringing clarity to status tag usage on meta sites
• Announcing a change to the data-dump process

Hot Network Questions

• What does "CD military" mean on this sign at this crossing point between East Berlin and West Berlin? (June/July 1989)
• Is there a way to isolate 2 operating systems on 2 different hard drives?
• How can one be honest with oneself if one IS oneself?
• Held Action Sneak attack after action surge
• My supervisor wants me to switch to another software/programming language that I am not proficient in. What to do?
• Overstayed Schengen but can I switch to US passport?
• Motion of the COM of 2-body system
• What is happening when a TV satellite stops broadcasting during an "eclipse"?
• OpenCLLink does print build errors (MacOS M1 / Wolfram Engine 14.1)
• How can moral disagreements be resolved when the conflicting parties are guided by fundamentally different value systems?
• Is 3 ohm resistance value of a PCB fuse reasonable?
• 70s-80s animation with an island of robots
• What does this translated phrase convey "The heart refuses to obey."?
• How to define a function for Schmitt trigger?
• Can you give me an example of an implicit use of Godel's Completeness Theorem, say for example in group theory?
• Which version of Netscape, on which OS, appears in the movie “Cut” (2000)?
• What happens when touching a piece which cannot make a legal move?
• Rings demanding identity in the categorical context
• Encode a VarInt
• Whatever happened to Chessmaster?
• How is message waiting conveyed to home POTS phone
• Replacing aircon capacitor, using off brand same spec vs lower/higher spec from correct brand?
• Do somebody know when will GPT5 be available for public?
• magnetic boots inverted

Generalized Assignment Problem

• Reference work entry
• pp 1153–1162
• Cite this reference work entry

• O. Erhun Kundakcioglu 3 &
• Saed Alizamir 3  

2895 Accesses

15 Citations

Article Outline

Introduction

  Multiple-Resource Generalized Assignment Problem

  Multilevel Generalized Assignment Problem

  Dynamic Generalized Assignment Problem

  Bottleneck Generalized Assignment Problem

  Generalized Assignment Problem with Special Ordered Set

  Stochastic Generalized Assignment Problem

  Bi-Objective Generalized Assignment Problem

  Generalized Multi-Assignment Problem

  Exact Algorithms

  Heuristics

Conclusions

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Subscribe and save.

• Get 10 units per month
• Download Article/Chapter or eBook
• 1 Unit = 1 Article or 1 Chapter
• Cancel anytime
• Available as PDF
• Read on any device
• Instant download
• Own it forever
• Durable hardcover edition
• Dispatched in 3 to 5 business days
• Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

Some results on an assignment problem variant

Combinatorial clustering: literature review, methods, examples.

Introduction to Optimisation

Albareda-Sambola M, van der Vlerk MH, Fernandez E (2006) Exact solutions to a class of stochastic generalized assignment problems. Eur J Oper Res 173:465–487

Article   MATH   Google Scholar  

Amini MM, Racer M (1994) A rigorous computational comparison of alternative solution methods for the generalized assignment problem. Manag Sci 40(7):868–890

Amini MM, Racer M (1995) A hybrid heuristic for the generalized assignment problem. Eur J Oper Res 87(2):343–348

Asahiro Y, Ishibashi M, Yamashita M (2003) Independent and cooperative parallel search methods for the generalized assignment problem. Optim Method Softw 18:129–141

Article   MathSciNet   MATH   Google Scholar  

Balachandran V (1976) An integer generalized transportation model for optimal job assignment in computer networks. Oper Res 24(4):742–759

Barnhart C, Johnson EL, Nemhauser GL, Savelsbergh MWP, Vance PH (1998) Branch-and-price: column generation for solving huge integer programs. Oper Res 46(3):316–329

Beasley JE (1993) Lagrangean heuristics for location problems. Eur J Oper Res 65:383–399

Cario MC, Clifford JJ, Hill RR, Yang J, Yang K, Reilly CH (2002) An investigation of the relationship between problem characteristics and algorithm performance: a case study of the gap. IIE Trans 34:297–313

Google Scholar  

Cattrysse DG, Salomon M, Van LN Wassenhove (1994) A set partitioning heuristic for the generalized assignment problem. Eur J Oper Res 72:167–174

Cattrysse DG, Van LN Wassenhove (1992) A survey of algorithms for the generalized assignment problem. Eur J Oper Res 60:260–272

Ceselli A, Righini G (2006) A branch-and-price algorithm for the multilevel generalized assignment problem. Oper Res 54:1172–1184

Chalmet L, Gelders L (1976) Lagrangean relaxation for a generalized assignment type problem. In: Advances in OR. EURO, North Holland, Amsterdam, pp 103–109

Chu EC, Beasley JE (1997) A genetic algorithm for the generalized assignment problem. Comput Oper Res 24:17–23

Cohen R, Katzir L, Raz D (2006) An efficient approximation for the generalized assignment problem. Inf Process Lett 100:162–166

de Farias Jr, Johnson EL, Nemhauser GL (2000) A generalized assignment problem with special ordered sets: a polyhedral approach. Math Program, Ser A 89:187–203

de Farias Jr, Nemhauser GL (2001) A family of inequalities for the generalized assignment polytope. Oper Res Lett 29:49–55

DeMaio A, Roveda C (1971) An all zero-one algorithm for a class of transportation problems. Oper Res 19:1406–1418

Diaz JA, Fernandez E (2001) A tabu search heuristic for the generalized assignment problem. Eur J Oper Res 132:22–38

Drexl A (1991) Scheduling of project networks by job assignment. Manag Sci 37:1590–1602

Dyer M, Frieze A (1992) Probabilistic analysis of the generalised assignment problem. Math Program 55:169–181

Article   MathSciNet   Google Scholar  

Feltl H, Raidl GR (2004) An improved hybrid genetic algorithm for the generalized assignment problem. In: SAC '04; Proceedings of the 2004 ACM symposium on Applied computing. ACM Press, New York, pp 990–995

Chapter   Google Scholar  

Fisher ML, Jaikumar R (1981) A generalized assignment heuristic for vehicle routing. Netw 11:109–124

Fisher ML, Jaikumar R, van Wassenhove LN (1986) A multiplier adjustment method for the generalized assignment problem. Manag Sci 32:1095–1103

Fleischer L, Goemans MX, Mirrokni VS, Sviridenko M (2006) Tight approximation algorithms for maximum general assignment problems. In SODA '06: Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm. ACM Press, New York, pp 611–620

Book   Google Scholar  

Freling R, Romeijn HE, Morales DR, Wagelmans APM (2003) A branch-and-price algorithm for the multiperiod single-sourcing problem. Oper Res 51(6):922–939

French AP, Wilson JM (2002) Heuristic solution methods for the multilevel generalized assignment problem. J Heuristics 8:143–153

French AP, Wilson JM (2007) An lp-based heuristic procedure for the generalized assignment problem with special ordered sets. Comput Oper Res 34:2359–2369

Garey MR, Johnson DS (1990) Computers and Intractability; A Guide to the Theory of NP-Completeness. Freeman, New York

Gavish B, Pirkul H (1991) Algorithms for the multi-resource generalized assignment problem. Manag Sci 37:695–713

Geoffrion AM, Graves GW (1974) Multicommodity distribution system design by benders decomposition. Manag Sci 20(5):822–844

Glover F, Hultz J, Klingman D (1979) Improved computer based planning techniques, part ii. Interfaces 4:17–24

Gottlieb ES, Rao MR (1990) \( (1,k) \) -configuration facets for the generalized assignment problem. Math Program 46(1):53–60

Gottlieb ES, Rao MR (1990) The generalized assignment problem: Valid inequalities and facets. Math Stat 46:31–52

MathSciNet   MATH   Google Scholar  

Guignard M, Rosenwein MB (1989) An improved dual based algorithm for the generalized assignment problem. Oper Res 37(4):658–663

Haddadi S (1999) Lagrangian decomposition based heuristic for the generalized assignment problem. Inf Syst Oper Res 37:392–402

Haddadi S, Ouzia H (2004) Effective algorithm and heuristic for the generalized assignment problem. Eur J Oper Res 153:184–190

Hajri-Gabouj S (2003) A fuzzy genetic multiobjective optimization algorithm for a multilevel generalized assignment problem. IEEE Trans Syst 33:214–224

Janak SL, Taylor MS, Floudas CA, Burka M, Mountziaris TJ (2006) Novel and effective integer optimization approach for the nsf panel-assignment problem: a multiresource and preference-constrained generalized assignment problem. Ind Eng Chem Res 45:258–265

Article   Google Scholar  

Jörnsten K, Nasberg M (1986) A new lagrangian relaxation approach to the generalized assignment problem. Eur J Oper Res 27:313–323

Jörnsten KO, Varbrand P (1990) Relaxation techniques and valid inequalities applied to the generalized assignment problem. Asia-P J Oper Res 7(2):172–189

Klastorin TD (1979) An effective subgradient algorithm for the generalized assignment problem. Comp Oper Res 6:155–164

Klastorin TD (1979) On the maximal covering location problem and the generalized assignment problem. Manag Sci 25(1):107–112

Kogan K, Khmelnitsky E, Ibaraki T (2005) Dynamic generalized assignment problems with stochastic demands and multiple agent task relationships. J Glob Optim 31:17–43

Kogan K, Shtub A, Levit VE (1997) Dgap – the dynamic generalized assignment problem. Ann Oper Res 69:227–239

Kuhn H (1995) A heuristic algorithm for the loading problem in flexible manufacturing systems. Int J Flex Manuf Syst 7:229–254

Laguna M, Kelly JP, Gonzfilez-Velarde JL, Glover F (1995) Tabu search for the multilevel generalized assignment problem. Eur J Oper Res 82:176–189

Lawler E (1976) Combinatorial Optimization: Networks and Matroids. Holt, Rinehart, Winston, New York

MATH   Google Scholar  

Lin BMT, Huang YS, Yu HK (2001) On the variable-depth-search heuristic for the linear-cost generalized assignment problem. Int J Comput Math 77:535–544

Lorena LAN, Narciso MG (1996) Relaxation heuristics for a generalized assignment problem. Eur J Oper Res 91:600–610

Lorena LAN, Narciso MG, Beasley JE (2003) A constructive genetic algorithm for the generalized assignment problem. J Evol Optim

Lourenço HR, Serra D (1998) Adaptive approach heuristics for the generalized assignment problem. Technical Report 288, Department of Economics and Business, Universitat Pompeu Fabra, Barcelona

Lourenço HR, Serra D (2002) Adaptive search heuristics for the generalized assignment problem. Mathw Soft Comput 9(2–3):209–234

Martello S, Toth P (1981) An algorithm for the generalized assignment problem. In: Brans JP (ed) Operational Research '81, 9th IFORS Conference, North-Holland, Amsterdam, pp 589–603

Martello S, Toth P (1990) Knapsack Problems: Algorithms and Computer Implementations. Wiley, New York

Martello S, Toth P (1992) Generalized assignment problems. Lect Notes Comput Sci 650:351–369

MathSciNet   Google Scholar  

Martello S, Toth P (1995) The bottleneck generalized assignment problem. Eur J Oper Res 83:621–638

Mazzola JB, Neebe AW (1988) Bottleneck generalized assignment problems. Eng Costs Prod Econ 14(1):61–65

Mazzola JB, Wilcox SP (2001) Heuristics for the multi-resource generalized assignment problem. Nav Res Logist 48(6):468–483

Monfared MAS, Etemadi M (2006) The impact of energy function structure on solving generalized assignment problem using hopfield neural network. Eur J Oper Res 168:645–654

Morales DR, Romeijn HE (2005) Handbook of Combinatorial Optimization, supplement vol B. In: Du D-Z, Pardalos PM (eds) The Generalized Assignment Problem and extensions. Springer, New York, pp 259–311

Narciso MG, Lorena LAN (1999) Lagrangean/surrogate relaxation for generalized assignment problems. Eur J Oper Res 114:165–177

Nauss RM (2003) Solving the generalized assignment problem: an optimizing and heuristic approach. INFORMS J Comput 15(3):249–266

Nauss RM (2005) The elastic generalized assignment problem. J Oper Res Soc 55:1333–1341

Nowakovski J, Schwarzler W, Triesch E (1999) Using the generalized assignment problem in scheduling the rosat space telescope. Eur J Oper Res 112:531–541

Nutov Z, Beniaminy I, Yuster R (2006) A  \( (1-1/e) \) ‐approximation algorithm for the generalized assignment problem. Oper Res Lett 34:283–288

Park JS, Lim BH, Lee Y (1998) A lagrangian dual-based branch-and-bound algorithm for the generalized multi-assignment problem. Manag Sci 44(12S):271–275

Pigatti A, de Aragao MP, Uchoa E (2005) Stabilized branch-and-cut-and-price for the generalized assignment problem. In: Electronic Notes in Discrete Mathematics, vol 19 of 2nd Brazilian Symposium on Graphs, Algorithms and Combinatorics, pp 385–395,

Osman IH (1995) Heuristics for the generalized assignment problem: simulated annealing and tabu search approaches. OR-Spektrum 17:211–225

Racer M, Amini MM (1994) A robust heuristic for the generalized assignment problem. Ann Oper Res 50(1):487–503

Romeijn HE, Morales DR (2000) A class of greedy algorithms for the generalized assignment problem. Discret Appl Math 103:209–235

Romeijn HE, Morales DR (2001) Generating experimental data for the generalized assignment problem. Oper Res 49(6):866–878

Romeijn HE, Piersma N (2000) A probabilistic feasibility and value analysis of the generalized assignment problem. J Comb Optim 4:325–355

Ronen D (1992) Allocation of trips to trucks operating from a single terminal. Comput Oper Res 19(5):445–451

Ross GT, Soland RM (1975) A branch and bound algorithm for the generalized assignment problem. Math Program 8:91–103

Ross GT, Soland RM (1977) Modeling facility location problems as generalized assignment problems. Manag Sci 24:345–357

Ross GT, Zoltners AA (1979) Weighted assignment models and their application. Manag Sci 25(7):683–696

Savelsbergh M (1997) A branch-and-price algorithm for the generalized assignment problem. Oper Res 45:831–841

Shmoys DB, Tardos E (1993) An approximation algorithm for the generalized assignment problem. Math Program 62:461–474

Shtub A (1989) Modelling group technology cell formation as a generalized assignment problem. Int J Prod Res 27:775–782

Srinivasan V, Thompson GL (1973) An algorithm for assigning uses to sources in a special class of transportation problems. Oper Res 21(1):284–295

Stützle T, Hoos H (1999) The Max-Min Ant System and Local Search for Combinatorial Optimization Problems. In: Voss S, Martello S, Osman IH, Roucairol C (eds) Meta-heuristics; Advances and trends in local search paradigms for optimization. Kluwer, Boston, pp 313–329

Toktas B, Yen JW, Zabinsky ZB (2006) Addressing capacity uncertainty in resource-constrained assignment problems. Comput Oper Res 33:724–745

Trick M (1992) A linear relaxation heuristic for the generalized assignment problem. Nav Res Logist 39:137–151

Trick MA (1994) Scheduling multiple variable-speed machines. Oper Res 42(2):234–248

Wilson JM (1997) A genetic algorithm for the generalised assignment problem. J Oper Res Soc 48:804–809

Wilson JM (2005) An algorithm for the generalized assignment problem with special ordered sets. J Heuristics 11:337–350

Yagiura M, Ibaraki T, Glover F (2004) An ejection chain approach for the generalized assignment problem. INFORMS J Comput 16:133–151

Yagiura M, Ibaraki T, Glover F (2006) A path relinking approach with ejection chains for the generalized assignment problem. Eur J Oper Res 169:548–569

Yagiura M, Yamaguchi T, Ibaraki T (1998) A variable depth search algorithm with branching search for the generalized assignment problem. Optim Method Softw 10:419–441

Yagiura M, Yamaguchi T, Ibaraki T (1999) A variable depth search algorithm for the generalized assignment problem. In: Voss S, Martello S, Osman IH, Roucairol C (eds) Meta-heuristics; Advances and Trends in Local Search paradigms for Optimization, Kluwer, Boston, pp 459–471

Zhang CW, Ong HL (2007) An efficient solution to biobjective generalized assignment problem. Adv Eng Softw 38:50–58

Zimokha VA, Rubinshtein MI (1988) R & d planning and the generalized assignment problem. Autom Remote Control 49:484–492

Download references

Author information

Authors and affiliations.

Department of Industrial and Systems Engineering, University of Florida, Gainesville, USA

O. Erhun Kundakcioglu & Saed Alizamir

You can also search for this author in PubMed   Google Scholar

Editor information

Editors and affiliations.

Department of Chemical Engineering, Princeton University, Princeton, NJ, 08544-5263, USA

Christodoulos A. Floudas

Center for Applied Optimization, Department of Industrial and Systems Engineering, University of Florida, Gainesville, FL, 32611-6595, USA

Panos M. Pardalos

Rights and permissions

Reprints and permissions

Copyright information

© 2008 Springer-Verlag

About this entry

Cite this entry.

Kundakcioglu, O.E., Alizamir, S. (2008). Generalized Assignment Problem . In: Floudas, C., Pardalos, P. (eds) Encyclopedia of Optimization. Springer, Boston, MA. https://doi.org/10.1007/978-0-387-74759-0_200

Download citation

DOI : https://doi.org/10.1007/978-0-387-74759-0_200

Publisher Name : Springer, Boston, MA

Print ISBN : 978-0-387-74758-3

Online ISBN : 978-0-387-74759-0

eBook Packages : Mathematics and Statistics Reference Module Computer Science and Engineering

Share this entry

Anyone you share the following link with will be able to read this content:

Sorry, a shareable link is not currently available for this article.

Provided by the Springer Nature SharedIt content-sharing initiative

• Publish with us

Policies and ethics

• Find a journal
• Track your research

• Stack Overflow for Teams Where developers & technologists share private knowledge with coworkers
• Advertising & Talent Reach devs & technologists worldwide about your product, service or employer brand
• OverflowAI GenAI features for Teams
• OverflowAPI Train & fine-tune LLMs
• Labs The future of collective knowledge sharing
• About the company Visit the blog

Collectives™ on Stack Overflow

Find centralized, trusted content and collaborate around the technologies you use most.

Q&A for work

Connect and share knowledge within a single location that is structured and easy to search.

Get early access and see previews of new features.

Efficiently solving assignment problem with constraints

I have a variation of https://en.wikipedia.org/wiki/Assignment_problem#Unbalanced_assignment :

• A bipartite graph with vertex sets A and T,
• Non-negative costs on the edges,
• All vertexes in A and T must occur at most once in a matching.

But with following modifications:

• The edges in a matching must not intersect, i.e. with vertexes a_i in A and t_j in T sorted by some index value on both sides of the graph, a_(i_1) and t_(j_2) must not be connected in the matching when a_(i_2) and t_(j_1) are with i_1 < i_2 and j_1 < j_2.
• Also for the smaller vertex set of the bipartite graph, not all vertexes need to be assigned, i.e. the optimal matching might only contain 1 edge when it has extreme costs.
• We don't provide a constant s for the size of the matching to find.
• Want to MAXIMIZE the sum of edge costs of the assignment.

How can that be solved most efficiently?

Linear program seems to be inefficient.

The problem can also be formulated as shortest-path problem with vertexes v_(i,j) when a_i and t_j are connected in the original bipartite graph, additional source and sink, and edges where above modifications 1 & 2 are satisfied. This still has |A|!*|T|! edges roughly which would also result in high runtime. Costs of edge from v(i_1,j_1) to v(i_2,j_2) should be set to minus the cost of the edge from a_(i_2) to t(j_2) in the original bipartite graph, so we're replicating cost values many times.

Is there some more efficient shortest-path variant with costs on vertexes instead of edges?

Or can the https://en.wikipedia.org/wiki/Hungarian_algorithm be modified to respect above modification 1? For modification 2 and 3 I see a trivial approach by adding rows and columns with values of 0 in order to get a balanced assignment problem, and modification 4 should be just negating the cost function.

• shortest-path
• operations-research
• hungarian-algorithm
• assignment-problem

• For modification (1), are the orderings given or do you have to find the best result among all possible orderings? –  Matt Timmermans Commented Jun 20, 2022 at 17:01
• The orderings are given. The vertexes at each side of the bipartite graph have been sorted before. –  Luma Commented Jun 20, 2022 at 19:06
• Just found that the Dijkstra algorithm seems to solve it within O((|A|*|T|)^2), despite of the high number of edges... Will give an update when I have final results... –  Luma Commented Jun 20, 2022 at 19:10
• 2 If the orderings are given, then there's an O(|A|*|T|) dynamic programming solution similar to longest-common-subsequence –  Matt Timmermans Commented Jun 20, 2022 at 19:49
• Wow thanks for that hint, I can see it. Will post it as the solution together with the concrete algorithm as soon as I'm ready. –  Luma Commented Jun 20, 2022 at 21:25

According to above hint from @MattTimmermans, I ended up in the following dynamic programming approach (which is a modification of bipartite graph and dynamic programming ):

Let w(a, t) be edge weight between nodes a in A and t in T , and let M(i, j) be solution (maximum cost matching graph without intersecting edges) for vertexes {a_0, a_1, ..., a_(i-1)} subset A and {t_0, t_1, ..., t_(j-1)} subset T , where 0 <= i < |A| and 0 <= j < |T| . For i = 0 and j = 0 the vertexes subsets are empty, i.e. prepending the matrix M by 1 row and 1 column.

And then go backwards from M(|A|,|T|) according to step_type in every step, till we reach M(0,0) . This gives a list of the edges in the best matching (in reverse order).

Your Answer

Reminder: Answers generated by artificial intelligence tools are not allowed on Stack Overflow. Learn more

Sign up or log in

Post as a guest.

Required, but never shown

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy .

Not the answer you're looking for? Browse other questions tagged algorithm shortest-path operations-research hungarian-algorithm assignment-problem or ask your own question .

• The Overflow Blog
• Where does Postgres fit in a world of GenAI and vector databases?
• Mobile Observability: monitoring performance through cracked screens, old...
• Featured on Meta
• Announcing a change to the data-dump process
• Bringing clarity to status tag usage on meta sites
• What does a new user need in a homepage experience on Stack Overflow?
• Staging Ground Reviewer Motivation
• Feedback requested: How do you use tag hover descriptions for curating and do...

Hot Network Questions

• How to count mismatches between two rows, column by column R?
• What happens when touching a piece which cannot make a legal move?
• 1960s Stylesheet/Format for working Physics problems
• Explain how π – 1 + 50 + ⅔ × 1000 is PLONK
• Cannot open and HTML file stored on RAM-disk with a browser
• Journal keeps messing with my proof
• If Starliner returns safely on autopilot, can this still prove that it's safe? Could it be launched back up to the ISS again to complete it's mission?
• My supervisor wants me to switch to another software/programming language that I am not proficient in. What to do?
• Is 3 ohm resistance value of a PCB fuse reasonable?
• Is this screw inside a 2-prong receptacle a possible ground?
• How can moral disagreements be resolved when the conflicting parties are guided by fundamentally different value systems?
• Why is there no article after 'by'?
• Can unlimited Duration spells be Dismissed?
• How to remove obligation to run as administrator in Windows?
• How can one be honest with oneself if one IS oneself?
• What story starts off with the character waking up in a battlefield with wolves and vultures and snow?
• Do passengers transiting in YVR (Vancouver) from international to US go through Canadian immigration?
• Held Action Sneak attack after action surge
• Shelves in concrete+drywall
• Can you give me an example of an implicit use of Godel's Completeness Theorem, say for example in group theory?
• Which Mosaic law was in the backdrop of ceremonial hand-washing in Mark 7?
• Compact symmetric spaces and sub-root systems
• Gomoku game 5 in a row. Javascript simple game Canvas
• Whatever happened to Chessmaster?