assignment problem extensions

Information

• Author Services

Initiatives

You are accessing a machine-readable page. In order to be human-readable, please install an RSS reader.

All articles published by MDPI are made immediately available worldwide under an open access license. No special permission is required to reuse all or part of the article published by MDPI, including figures and tables. For articles published under an open access Creative Common CC BY license, any part of the article may be reused without permission provided that the original article is clearly cited. For more information, please refer to https://www.mdpi.com/openaccess .

Feature papers represent the most advanced research with significant potential for high impact in the field. A Feature Paper should be a substantial original Article that involves several techniques or approaches, provides an outlook for future research directions and describes possible research applications.

Feature papers are submitted upon individual invitation or recommendation by the scientific editors and must receive positive feedback from the reviewers.

Editor’s Choice articles are based on recommendations by the scientific editors of MDPI journals from around the world. Editors select a small number of articles recently published in the journal that they believe will be particularly interesting to readers, or important in the respective research area. The aim is to provide a snapshot of some of the most exciting work published in the various research areas of the journal.

Original Submission Date Received: .

• Active Journals
• Find a Journal
• Proceedings Series
• For Authors
• For Reviewers
• For Editors
• For Librarians
• For Publishers
• For Societies
• For Conference Organizers
• Open Access Policy
• Institutional Open Access Program
• Special Issues Guidelines
• Editorial Process
• Research and Publication Ethics
• Article Processing Charges
• Testimonials
• Preprints.org
• SciProfiles
• Encyclopedia

Article Menu

• Subscribe SciFeed
• Recommended Articles
• Google Scholar
• on Google Scholar
• Table of Contents

Find support for a specific problem in the support section of our website.

Please let us know what you think of our products and services.

Visit our dedicated information section to learn more about MDPI.

JSmol Viewer

A four-label-based algorithm for solving stable extension enumeration in abstract argumentation frameworks, 1. introduction, 2. related work on reduction-based methods and direct solving for af, 3. background, 3.1. abstract argumentation framework and stable extensions, 3.2. the relationship between arguments and labelings, 4. comparison of two-label and three-label enumeration algorithms for stable extensions, 4.1. labeling model for stable extensions, 4.2. comparison of two-label and three-label algorithms.

• Step 1: Argument a 1 is labeled as i n and propagates the o u t label to argument a 2 , with all propagated labels being legal.
• Step 2: Argument a 3 is labeled as i n and propagates the o u t label to arguments a 4 and a 5 . The arguments a 2 , a 4 , and a 5 , labeled as o u t , are all legal.
• Step 3: Argument a 6 is labeled as i n without propagating any other argument labels, so no labeling legality check is needed. At this point, all arguments have been legally labeled, so the set of arguments labeled as i n   { a 1 , a 3 , a 6 } forms a stable extension.
• Step 1: Argument a 1 is labeled as i n and propagates the label o u t to argument a 2 . No labeling legality check is needed in this round.
• Step 2: Argument a 3 is labeled as i n and propagates the labels m u s t _ o u t and o u t to arguments a 4 and a 5 , respectively. A legality check is performed for argument a 4 , which is labeled as m u s t _ o u t .
• Step 3: Argument a 6 does not propagate any other argument labels, so no legality check is needed.

5. The Labeling Algorithm for Four-Label Enumeration Stable Extension

5.1. the concept of the four-label enumeration stable extension algorithm.

• Step 1: During preprocessing, the initial argument a 1 is labeled as m u s t _ i n , and other ordinary arguments are labeled as b l a n k . The arguments in the m u s t _ i n label set are then prioritized for the i n transition. Consequently, argument a 1 is labeled as i n and propagates the label o u t to argument a 2 .
• Step 2: The argument a 3 is selected from the ordinary argument set. Then argument a 3 is labeled as i n and propagates labels m u s t _ o u t and o u t to arguments a 4 and a 5 , respectively. The labeling legality of argument a 4 , which is labeled as m u s t _ o u t , is then checked and found to be legal. Next, the algorithm attempts to further propagate labels based on the propagated arguments a 4 and a 5 . Argument a 4 propagates the label m u s t _ i n to argument a 6 , which is then labeled as i n . At this point, a stable extension { a 1 , a 3 , a 6 } is obtained.

5.2. Four-Label Algorithm Description

6. Experiment Analysis

6.1. experiment setup, 6.2. experiment results and analysis.

• ArgTools_3lab: The basic Argtools solver which uses three labels.
• ArgTools_3lab+: Argtools solver with the preprocessing strategy applied.
• ArgTools_3lab++(ArgTools_4lab): Argtools solver with the proposed four-label method applied.
• ArgSemSAT: Stable extension solving algorithm based on the reduction model.
• DREDD: The basic DREDD solver using three labels.
• DREDD_4lab: DREDD solver with the proposed four-label method applied.

7. Conclusions and Future Work

Author contributions, institutional review board statement, informed consent statement, data availability statement, conflicts of interest.

• Bench-Capon, T.J.; Dunne, P.E. Argumentation in artificial intelligence. Artif. Intell. 2007 , 171 , 619–641. [ Google Scholar ] [ CrossRef ]
• Rahwan, I.; Simari, G.R. Argumentation in Artificial Intelligence ; Springer: Cham, Switzerland, 2009; Volume 47. [ Google Scholar ]
• Atkinson, K.; Baroni, P.; Giacomin, M.; Hunter, A.; Prakken, H.; Reed, C.; Simari, G.; Thimm, M.; Villata, S. Towards artificial argumentation. AI Mag. 2017 , 38 , 25–36. [ Google Scholar ] [ CrossRef ]
• Dung, P.M. On the acceptability of arguments and its fundamental role in nonmonotonic reasoning, logic programming and n-person games. Artif. Intell. 1995 , 77 , 321–357. [ Google Scholar ] [ CrossRef ]
• Amgoud, L.; Prade, H. Using arguments for making and explaining decisions. Artif. Intell. 2009 , 173 , 413–436. [ Google Scholar ] [ CrossRef ]
• Caminada, M. Rationality postulates: Applying argumentation theory for non-monotonic reasoning. J. Appl. Logics 2017 , 4 , 2707–2734. [ Google Scholar ]
• Možina, M.; Žabkar, J.; Bratko, I. Argument based machine learning. Artif. Intell. 2007 , 171 , 922–937. [ Google Scholar ] [ CrossRef ]
• Kökciyan, N.; Sassoon, I.; Sklar, E.; Modgil, S.; Parsons, S. Applying metalevel argumentation frameworks to support medical decision making. IEEE Intell. Syst. 2021 , 36 , 64–71. [ Google Scholar ] [ CrossRef ]
• Walton, D.; Oliveira, T.; Satoh, K.; Mebane, W. Argumentation analytics for treatment deliberations in multimorbidity cases: An introduction to two artificial intelligence approaches. Topoi 2021 , 40 , 373–386. [ Google Scholar ] [ CrossRef ]
• Caminada, M.W.; Gabbay, D.M. A logical account of formal argumentation. Stud. Log. 2009 , 93 , 109–145. [ Google Scholar ] [ CrossRef ]
• Dvořák, W.; Morak, M.; Nopp, C.; Woltran, S. dynPARTIX-A dynamic programming reasoner for abstract argumentation. In Proceedings of the International Conference on Applications of Declarative Programming and Knowledge Management, Vienna, Austria, 28–30 September 2011; pp. 259–268. [ Google Scholar ]
• Charwat, G.; Dvořák, W.; Gaggl, S.A.; Wallner, J.P.; Woltran, S. Methods for solving reasoning problems in abstract argumentation—A survey. Artif. Intell. 2015 , 220 , 28–63. [ Google Scholar ] [ CrossRef ] [ PubMed ]
• Cerutti, F.; Gaggl, S.A.; Thimm, M.; Wallner, J. Foundations of implementations for formal argumentation. IfCoLog J. Logics Their Appl. 2017 , 4 , 2623–2705. [ Google Scholar ]
• Nofal, S.; Atkinson, K.; Dunne, P.E. Algorithms for decision problems in argument systems under preferred semantics. Artif. Intell. 2014 , 207 , 23–51. [ Google Scholar ] [ CrossRef ]
• Baroni, P.; Caminada, M.; Giacomin, M. An introduction to argumentation semantics. Knowl. Eng. Rev. 2011 , 26 , 365–410. [ Google Scholar ] [ CrossRef ]
• Caminada, M. An algorithm for computing semi-stable semantics. In Proceedings of the European Conference on Symbolic and Quantitative Approaches to Reasoning and Uncertainty, Hammamet, Tunisia, 31 October–2 November 2007; pp. 222–234. [ Google Scholar ]
• Prakken, H.; Vreeswijk, G. Logics for defeasible argumentation. In Handbook of Philosophical Logic ; Springer: Cham, Switzerland, 2002; pp. 219–318. [ Google Scholar ]
• Dvořák, W.; König, M.; Rapberger, A.; Wallner, J.P.; Woltran, S. ASPARTIX-V-A Solver for Argumentation Tasks Using ASP. In Proceedings of the 14th Workshop on Answer Set Programming and Other Computing Paradigms, Virtual, 20–27 September 2021; pp. 1–12. [ Google Scholar ]
• Dvorák, W.; König, M.; Wallner, J.P.; Woltran, S. ASPARTIX-v21. arXiv 2021 , arXiv:2109.03166. [ Google Scholar ]
• Niskanen, A.; Järvisalo, M. μ -TOKSIA in ICCMA 2023. In Proceedings of the ICCMA 2023, Helsinki, Finland, 1–3 November 2023; p. 31. [ Google Scholar ]
• Kamal, A.A.; Youssef, A.M. Applications of SAT solvers to AES key recovery from decayed key schedule images. In Proceedings of the 2010 Fourth International Conference on Emerging Security Information, Systems and Technologies, Venice, Italy, 18–25 July 2010; pp. 216–220. [ Google Scholar ]
• Audemard, G.; Simon, L. Predicting learnt clauses quality in modern SAT solvers. In Proceedings of the Twenty-First International Joint Conference on Artificial Intelligence, Pasadena, CA, USA, 11–17 July 2009. [ Google Scholar ]
• Fleury, A.; Heisinger, M. Cadical, kissat, paracooba, plingeling and treengeling entering the sat competition 2020. SAT Compet. 2020 , 2020 , 50. [ Google Scholar ]
• Queue, S.D. CaDiCaL at the SAT Race 2019. SAT Race 2019 , 2019 , 8. [ Google Scholar ]
• Gebser, M.; Kaminski, R.; Kaufmann, B.; Schaub, T. Answer Set Solving in Practice ; Springer: Cham, Switzerland, 2022. [ Google Scholar ]
• Biere, A.; Heule, M.; van Maaren, H. Handbook of Satisfiability ; IOS Press: Amsterdam, The Netherlands, 2009; Volume 185. [ Google Scholar ]
• Niu, D.; Liu, L.; Lü, S. New stochastic local search approaches for computing preferred extensions of abstract argumentation. AI Commun. 2018 , 31 , 369–382. [ Google Scholar ] [ CrossRef ]
• Thimm, M. Stochastic Local Search Algorithms for Abstract Argumentation Under Stable Semantics. In Proceedings of the COMMA, Warsaw, Poland, 12–14 September 2018; pp. 169–180. [ Google Scholar ]
• Nofal, S.; Atkinson, K.; Dunne, P.E. Looking-ahead in backtracking algorithms for abstract argumentation. Int. J. Approx. Reason. 2016 , 78 , 265–282. [ Google Scholar ] [ CrossRef ]
• Geilen, N.; Thimm, M. Heureka: A General Heuristic Backtracking Solver for Abstract Argumentation. In Proceedings of the Theory and Applications of Formal Argumentation, Melbourne, VIC, Australia, 19–20 August 2018; pp. 143–149. [ Google Scholar ]

Click here to enlarge figure

Share and Cite

Luo, M.; He, N.; Wu, X.; Xiong, C.; Xu, W. A Four-Label-Based Algorithm for Solving Stable Extension Enumeration in Abstract Argumentation Frameworks. Appl. Sci. 2024 , 14 , 7656. https://doi.org/10.3390/app14177656

Luo M, He N, Wu X, Xiong C, Xu W. A Four-Label-Based Algorithm for Solving Stable Extension Enumeration in Abstract Argumentation Frameworks. Applied Sciences . 2024; 14(17):7656. https://doi.org/10.3390/app14177656

Luo, Mao, Ningning He, Xinyun Wu, Caiquan Xiong, and Wanghao Xu. 2024. "A Four-Label-Based Algorithm for Solving Stable Extension Enumeration in Abstract Argumentation Frameworks" Applied Sciences 14, no. 17: 7656. https://doi.org/10.3390/app14177656

Article Metrics

Article access statistics, further information, mdpi initiatives, follow mdpi.

Subscribe to receive issue release notifications and newsletters from MDPI journals

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.)

• DOI: 10.48550/arXiv.2310.03159
• Corpus ID: 263672141

New Auction Algorithms for the Assignment Problem and Extensions

• Dimitri Bertsekas
• Published in Results in Control and… 4 October 2023
• Computer Science, Mathematics

Figures from this paper

One Citation

Modeling of the process of multicriteria distribution and execution of work packages in the design of technological systems, 125 references, auction algorithms for network flow problems: a tutorial introduction, a distributed auction algorithm for the assignment problem, the auction algorithm for assignment and other network flow problems, towards auction algorithms for large dense assignment problems, the auction algorithm: a distributed relaxation method for the assignment problem, iterative combinatorial auctions: theory and practice, reverse auction and the solution of inequality constrained assignment problems, auction algorithms for path planning, network transport, and reinforcement learning, the auction algorithm for the transportation problem, auctions for multi-robot task allocation in communication limited environments, related papers.

Showing 1 through 3 of 0 Related Papers

Learn all about getting started with the Tailwind extension for Chrome, Firefox, and Safari to schedule content from around the web.

Tailwind's Browser Extension makes it easy to schedule and publish content from across the web!

Post Often : Find and schedule multiple images from any website via the toolbar button.

Post Quickly : Easily schedule any image by clicking the "Schedule" button when hovering over large images.

Ready to start scheduling across the web? We've included step-by-step instructions below on how to install the extension in your browser, as well as how to remove it.

Helpful Tip: Tailwind does not support Internet Explorer or Opera.

How to Install the Extension

How to remove the extension.

Ghostwriter Extension

Chrome or Microsoft Edge

Find our Chrome Extension in Google Chrome's Web Store. Select the Add to Chrome button, and then select Add Extension in the authorization pop-up:

Helpful tip: If you’re using Microsoft Edge, it will also support the Google Chrome version of the extension, which you can download from the Chrome store.

Safari (macOS)

Visit the Mac App Store and search for Tailwind Publisher. You can also use this link.

Click Get, then Install :

Select Open once the extension has been installed in your browser. You will be asked to open Safari Extension Preferences to complete installation:

Check the box next to Tailwind Publisher and select the website permissions:

Helpful Tip: The extension works best if you select Always Allow on Every Website. Our Safari extension also requires macOS 10.13 or later.

Find our Firefox Add-on in Mozilla's official site for add-ons to Mozilla software. Select the Add to Firefox button, then select Add on the authorization pop-up that appears:

Having trouble using the extension? If so, removing it and installing a new version is always the best first step!

Visit your Extension Manager page in your Chrome browser.

Find the Tailwind extension and select Remove , then confirm by clicking the second Remove button:

You can also remove the extension by right-clicking the extension shortcut in the toolbar, then selecting Remove from Chrome:

Go to your Firefox Add-Ons Menu (located in Firefox's Preferences and Settings).

Find Tailwind Publisher, click the drop-down menu and click the Remove button to remove the extension from your browser.

You can also right-click the extension icon in your toolbar and click Remove Extension:

Go to your Safari Extensions Menu (located in Safari's Preferences and Settings).

Find Tailwind Publisher and click the Uninstall button to remove the extension from your browser.

Ghostwriter Extension vs. Scheduling Images

Sorry for the confusion regarding our browser extension! We have recently introduced our new Ghostwriter Labs feature, so you now have two options when using the browser extension!

You can choose to have the browser extension button open the publisher or the Ghostwriter tool.

If you are looking to schedule images from the Tailwind extension, you will first want to make sure you are updated to the newest extension version 4.4.3. Then, when opening the extension, you should see the screen shown below. From here, you will click 'Reenable the classic experience'

Once clicking this, you will make sure that the settings default to 'Schedule Images'

You can also view these settings by visiting: https://www.tailwindapp.com/dashboard/v2/popup/settings/extension/

From here, you will need to close out of the window pop-up. Once you re-open the extension, you should see the option to schedule images. Please note: you may need to wait up to 10 seconds for it to load.

New auction algorithms for the assignment problem and extensions

• Engineering, Ira A. Fulton Schools of (IAFSE)

Research output : Contribution to journal › Article › peer-review

We consider the classical linear assignment problem, and we introduce new auction algorithms for its optimal and suboptimal solution. The algorithms are founded on duality theory, and are related to ideas of competitive bidding by persons for objects and the attendant market equilibrium, which underlie real-life auction processes. We distinguish between two fundamentally different types of bidding mechanisms: aggressive and cooperative. Mathematically, aggressive bidding relies on a notion of approximate coordinate descent in dual space, an ϵ-complementary slackness condition to regulate the amount of descent approximation, and the idea of ϵ-scaling to resolve efficiently the price wars that occur naturally as multiple bidders compete for a smaller number of valuable objects. Cooperative bidding avoids price wars through detection and cooperative resolution of any competitive impasse that involves a group of persons. We discuss the relations between the aggressive and the cooperative bidding approaches, we derive new algorithms and variations that combine ideas from both of them, and we also make connections with other primal–dual methods, including the Hungarian method. Furthermore, our discussion points the way to algorithmic extensions that apply more broadly to network optimization, including shortest path, max-flow, transportation, and minimum cost flow problems with both linear and convex cost functions.

• Auction algorithm
• Duality theory
• Linear assignment problem
• Optimal solution

ASJC Scopus subject areas

• Control and Systems Engineering
• Modeling and Simulation
• Control and Optimization
• Applied Mathematics
• Artificial Intelligence

Access to Document

• 10.1016/j.rico.2024.100383

Other files and links

• Link to publication in Scopus
• Link to the citations in Scopus

Fingerprint

• Approximates Mathematics 100%
• Real Life Mathematics 100%
• Cost Function Mathematics 100%
• Duality Theory Mathematics 100%
• Network Optimization Mathematics 100%
• Dual Space Mathematics 100%
• Hungarian Method Mathematics 100%
• Health Care Cost Medicine and Dentistry 100%

T1 - New auction algorithms for the assignment problem and extensions

AU - Bertsekas, Dimitri

N1 - Publisher Copyright: © 2024 The Author

PY - 2024/3

Y1 - 2024/3

N2 - We consider the classical linear assignment problem, and we introduce new auction algorithms for its optimal and suboptimal solution. The algorithms are founded on duality theory, and are related to ideas of competitive bidding by persons for objects and the attendant market equilibrium, which underlie real-life auction processes. We distinguish between two fundamentally different types of bidding mechanisms: aggressive and cooperative. Mathematically, aggressive bidding relies on a notion of approximate coordinate descent in dual space, an ϵ-complementary slackness condition to regulate the amount of descent approximation, and the idea of ϵ-scaling to resolve efficiently the price wars that occur naturally as multiple bidders compete for a smaller number of valuable objects. Cooperative bidding avoids price wars through detection and cooperative resolution of any competitive impasse that involves a group of persons. We discuss the relations between the aggressive and the cooperative bidding approaches, we derive new algorithms and variations that combine ideas from both of them, and we also make connections with other primal–dual methods, including the Hungarian method. Furthermore, our discussion points the way to algorithmic extensions that apply more broadly to network optimization, including shortest path, max-flow, transportation, and minimum cost flow problems with both linear and convex cost functions.

AB - We consider the classical linear assignment problem, and we introduce new auction algorithms for its optimal and suboptimal solution. The algorithms are founded on duality theory, and are related to ideas of competitive bidding by persons for objects and the attendant market equilibrium, which underlie real-life auction processes. We distinguish between two fundamentally different types of bidding mechanisms: aggressive and cooperative. Mathematically, aggressive bidding relies on a notion of approximate coordinate descent in dual space, an ϵ-complementary slackness condition to regulate the amount of descent approximation, and the idea of ϵ-scaling to resolve efficiently the price wars that occur naturally as multiple bidders compete for a smaller number of valuable objects. Cooperative bidding avoids price wars through detection and cooperative resolution of any competitive impasse that involves a group of persons. We discuss the relations between the aggressive and the cooperative bidding approaches, we derive new algorithms and variations that combine ideas from both of them, and we also make connections with other primal–dual methods, including the Hungarian method. Furthermore, our discussion points the way to algorithmic extensions that apply more broadly to network optimization, including shortest path, max-flow, transportation, and minimum cost flow problems with both linear and convex cost functions.

KW - Auction algorithm

KW - Duality theory

KW - Linear assignment problem

KW - Optimal solution

UR - http://www.scopus.com/inward/record.url?scp=85184511366&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85184511366&partnerID=8YFLogxK

U2 - 10.1016/j.rico.2024.100383

DO - 10.1016/j.rico.2024.100383

M3 - Article

AN - SCOPUS:85184511366

SN - 2666-7207

JO - Results in Control and Optimization

JF - Results in Control and Optimization

M1 - 100383

Vegetable and Fruit News-2024 (Volume 15, Issue 8)

2024  |  Volume 15, Issue 8

Inside this issue:.

• Corky Root Disease in Tomatoes
• Club Root Found in Brassica Crops
• Rain Check May Become a Problem in Tomato Fields
• Rain Cracking in Gala Apples
• Maryland Pesticide News
• Insect Scouting Tips
• UME and UMES Events

Vegetable Production Guide Mid-Atlantic Commercial Vegetable Production Recommendations (EB-236)

Spray program for multi-small fruit plantings, common fruit herbicides*, join our team.

The University of Maryland Extension is seeking dedicated individuals to join our team as Nutrient Management Advisors. Our mission is to provide educational programs and resources to Maryland farmers, helping them implement environmentally responsible nutrient management practices. As a Nutrient Management Advisor, you will play a crucial role in helping Maryland farmers develop and implement nutrient management plans. We are looking for individuals who are passionate about agriculture, have strong communication and organizational skills, and an understanding of farming operations and computer systems. University of Maryland Extension has three job openings located in Anne Arundel, Carroll, and Charles Counties. To apply or learn more, please visit https://ejobs.umd.edu/postings/121775

Upcoming Events

Additional upcoming events can be found on the UME events website . This institution is an equal opportunity provider. If you need a reasonable accommodation to participate in any UME event or activity, please contact your local University of Maryland Extension Office 2 weeks prior to the event.

Event: Summer Vegetable Twilight Tour Date: August 20, 2024  |  Tuesday Time: 5:30 p.m. to 7:30 p.m.  |  Cost: Free, but registration is appreciated. Location: Wye Research and Education Center, 211 Farm Lane, Queenstown, MD Description: featuring watermelons, sweet corn, and tomatoes. For more information please call Megan Messix Stibbe at (443) 446-4248 and [email protected] or Chris Cochran at (443) 988-8595 or [email protected]. Register: https://docs.google.com/forms/d/e/1FAIpQLScFgRMmsEKosDQ-Bc67yR9WCjCRKTxtEaTF738en_m2OGW1ZA/viewform?usp=sf_link

************************************************************************************

Science of Food Safety Short Course Dates: Aug 20-22, 2024  (Tuesday, Wednesday, & Thursday) Time: 9:00 a.m. to 5:30 p.m.  |  Cost: $400 Location: Room 2309 Edward St. John (ESJ) Learning and Teaching Center, 4131 Campus Drive, College Park, MD 20742 Syllabus :  https://drive.google.com/file/d/1aCN3sSYDmuUvdH25LFYnnap2KrqFHsya/view Register :  https://umd-nfs.catalog.instructure.com/courses/science-of-food-safety For more information : Contact Dr. Rohan Tikekar at  [email protected]  or 301-405-4509

Event: Sustainable Pest Management Workshops Time: 9:00 a.m. to 3:00 p.m.with lunch included. Description: This workshop will present information on common Ag insect pest identification and biology, monitoring and thresholds, preventive and nonchemical pest control methods, and chemical controls. Workshops will be repeated in two locations:

•  September 24, 2024 in Queenstown, MD.
•  October 1, 2024 in Derwood, MD.

More information at https://go.umd.edu/IPMFall2024 . If you have questions about the pro-gram, please contact Emily Zobel at [email protected] or 410-228-8800.

Event: Women in Agriculture Fall Farm Tour Date: Oct 3, 2024  | Time: 8 a.m. to 4:00 p.m. Cost: $25.00 per person for the tour, including lunch at the Robin Hill Farm and Vineyards Club. Description: Women in Ag and Annie's Project enthusiasts come together to tour the Southern MD area. More information here: https://agnr.umd.edu/events/women-in-agriculture-fall-farm-tour/

Event: How to Interpret a Soil Test Report Date: October 8, 2024  | Tuesday Time: 12:00 noon | Cost: Free Location: Online webinar (Zoom) Description: pH, organic matter, CEC, ppm, FIV, base saturation, oh my! This presentation will cover the basics of a soil test report and how to make management decisions based on your test results. Register: https://www.eventbrite.com/e/2024-women-in-ag-webinars-tickets-770439012827

Extensión en Español Check out Extensión en Español , a Spanish language blog by two UMD professors, Anahí Espíndola (Entomology) and Macarena Farcuh (Plant Sciences & Landscape Architecture). https://extensionesp.umd.edu/

They cover a range of topics, including fruit, pollinators, pests, soils, and pesticides.

Download Vegetable & Fruit News, Volume 15, Issue 8  (PDF)

Vegetable & Fruit News  is a research-based publication for the commercial vegetable and fruit industry available electronically from April through October.  Published by the University of Maryland Extension Agriculture and Food Systems team.

Subscribe to Fruit and Vegetable News

Emily Zobel University of Maryland Extension Agent - Dorchester County 501 Court Lane, Room 208 Cambridge, MD 21613 Phone:  (410) 410-228-8800 Email: [email protected]

Note: Registered Trade Mark® Products, Manufacturers, or Companies mentioned within this newsletter are not to be considered as sole endorsements. The information has been provided for educational purposes only

The Generalized Assignment Problem

• First Online: 10 February 2021

Cite this chapter

• Vittorio Maniezzo 6 ,
• Marco Antonio Boschetti 6 &
• Thomas Stützle 7  

Part of the book series: EURO Advanced Tutorials on Operational Research ((EUROATOR))

1345 Accesses

5 Citations

The generalized assignment problem (GAP) asks to assign n clients to m servers in such a way that the assignment cost is minimized, provided that all clients are assigned to a server and that the capacity of each server is not exceeded. It is a problem that appears, by itself or as a subproblem, in a very high number of practical applications and has therefore been intensively studied. We use this problem as a test case example of all algorithms presented in the text. This section reviews the state of the art of research on GAP and shows the application of several mathematical programming techniques on GAP instances.

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
• Available as EPUB and PDF
• Compact, lightweight edition
• Dispatched in 3 to 5 business days
• Free shipping worldwide - see info
• Durable hardcover edition

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Vectors and matrices are denoted by small bold letters throughout the text, and these definitions depart from the standard for compliance with much of the literature on the GAP. Furthermore, as stated in Sect. 1.1 , remind that all variables in this chapter are indexed from 1, but in the computational traces they will appear as indexed from 0.

In this, and in all algorithms in the text, the input of all GAP instance data is implicit.

Avella P, Boccia M, Vasilyev I (2010) A computational study of exact knapsack separation for the generalized assignment problem. Comput Optim Appl 45(3):543–555

Article   Google Scholar  

Beasley JE (1993) Lagrangian relaxation. In: Reeves CR (ed) Modern heuristic techniques for combinatorial problems. Wiley, New York, pp 243–303

Google Scholar  

Benders JF (1962) Partitioning procedures for solving mixed-variables programming problems. Numer Math 4:280–322

Benders JF, van Nunen JA (1983) A property of assignment type mixed linear programming problems. Oper Res Lett 32:47–52

Boschetti M, Maniezzo V (2009) Benders decomposition, Lagrangean relaxation and metaheuristic design. J Heurist 15:283–312

Bressoud TC, Rastogi R, Smith MA (2003) Optimal configuration for BGP route selection. In: IEEE INFOCOM 2003, twenty-second annual joint conference of the IEEE computer and communications societies, San Francisco, CA, vol 2, pp 916–926

Campbell GM (1999) Cross-utilization of workers whose capabilities differ. Manage Sci 45(5):722–732

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

Cattrysse DG, Degraeve Z, Tistaert J (1998) Solving the generalised assignment problem using polyhedral results. Eur J Oper Res 108(3):618–628

Chalmet LG, Gelders LF (1976) Lagrangian relaxations for a generalized assignment-type problem. In: Proceedings of the second european congress operations research. North-Holland, Amsterdam, pp 103–109

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

Cordeau JF, Gaudioso M, Laporte G, Moccia L (2006) A memetic heuristic for the generalized quadratic assignment problem. INFORMS J Comput 18(4):433–443

Dantzig GB, Wolfe P (1960) Decomposition principle for linear programs. Oper Res 8:101–111

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

Dobson G, Nambimadom RS (2001) The batch loading and scheduling problem. Oper Res 49(1):52–65

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

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

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

Foulds L, Wilson J (1997) A variation of the generalized assignment problem arising in the New Zealand dairy industry. Ann Oper Research 69:105–114

Garey MR, Johnson DS (1979) Computers and intractability: a guide to the theory of NP-completeness. W. H. Freeman & Co, New York, NY

Gavish B, Pirkul H (1985) Efficient algorithms for solving multiconstraint zero-one knapsack problems to optimality. Math Program 33(1):31–78

Geoffrion AM (1974) Lagrangean relaxation for integer programming. Math Program Stud 2:82–114

Glover F (1965) A multiphase-dual algorithm for the zero-one integer programming problem. Oper Res 13:879–919

Glover F (1968) Surrogate constraints. Oper Res 16:741–749

Glover F (1975) Surrogate constraint duality in mathematical programming. Oper Res 23:434–451

Glover F, Hultz H, Klingman D (1979) Improved computer based planning techniques, part 2. Interfaces 9(4):12–20

Gottlieb ES, Rao MR (1990) Generalized assignment problem. Valid inequalities and facets. Math Program Ser A 46(1):31–52

Greenberg HJ, Pierskalla WP (1970) Surrogate mathematical programming. Oper Res 18:924–939

Guignard M, Kim S (1987) Lagrangean decomposition: a model yielding stronger Lagrangean bounds. Math Program 39:215–228

Harvey NJA, Ladner RE, Lovász L, Tamir T (2006) Semi-matchings for bipartite graphs and load balancing. J Algorith 59(1):53–78

Higgins AJ (1999) Optimizing cane supply decisions within a sugar mill region. J Sched 2:229–244

Jeet V, Kutanoglu E (2007) Lagrangean relaxation guided problem space search heuristic for generalized assignment problems. Eur J Oper Res 182(3):1039–1056

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

Lee CG, Ma Z (2004) The generalized quadratic assignment problem. Tech. Rep. 5, Department of Mechanical and Industrial Engineering, University of Toronto, Toronto

Maniezzo V (2019) Bridging the GAP. Some generalized assignment problem instances. http://astarte.csr.unibo.it/gapdata/gapinstances.html

Martello S, Toth P (1981) An algorithm for the generalized assignment problem. In: Brans J (ed) Operations research ’81. North-Holland, Amsterdam, pp 589–603

Martello S, Toth P (1990) Knapsack problems: algorithms and computer implementations. Wiley, New York, NY

Mazzola JB, Neebe AW (1993) An algorithm for the bottleneck generalized assignment problem. Comput Oper Res 20(4):355–362

Mazzola JB, Neebe AW, Dunn CVR (1989) Production planning of a flexible manufacturing system in a requirements planning environment. Int J Flex Manuf Syst 1:115–142

Mitrović-Minić S, Punnen AP (2008) Very large-scale variable neighborhood search for the generalized assignment problem. J Interdiscipl Math 11(5):653–670

Morales DR, Romeijn HE (2004) The generalized assignment problem and extensions. In: Du D, Pardalos PM (eds) Handbook of combinatorial optimization. Springer, Boston, pp 259–311

Narciso MG, Lorena L (2007) Lagrangean/surrogate relaxation for generalized assignment problems. Eur J Oper Res 182:1039–1056

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

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

Öncan T (2007) A survey of the generalized assignment problem and its applications. Inf Syst Oper Res 45(3):123–141

Pigatti A, Poggi de Aragao M, Uchoa E (2005) Stabilized branch-and-cut-and-price for the generalized assignment problem. Electron Notes Discr Math 19:389–395

Pirkul H, Gavish B (1986) Computer and database location in distributed computer systems. IEEE Trans Comput 35:583–590

Posta M, Ferland JA, Michelon P (2012) An exact method with variable fixing for solving the generalized assignment problem. Comput Optim Appl 52(3):629–644

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

Ruland KS (1999) A model for aeromedical routing and scheduling. Int Trans Oper Res 6:57–73

Sahni S, Gonzalez T (1976) P-complete approximation problems. J ACM 23(3):555–565

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

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

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

Download references

Author information

Authors and affiliations.

University of Bologna, Cesena, Italy

Vittorio Maniezzo & Marco Antonio Boschetti

Université Libre de Bruxelles, Brussels, Belgium

Thomas Stützle

You can also search for this author in PubMed   Google Scholar

Rights and permissions

Reprints and permissions

Copyright information

© 2021 The Author(s), under exclusive license to Springer Nature Switzerland AG

About this chapter

Maniezzo, V., Boschetti, M.A., Stützle, T. (2021). The Generalized Assignment Problem. In: Matheuristics. EURO Advanced Tutorials on Operational Research. Springer, Cham. https://doi.org/10.1007/978-3-030-70277-9_1

Download citation

DOI : https://doi.org/10.1007/978-3-030-70277-9_1

Published : 10 February 2021

Publisher Name : Springer, Cham

Print ISBN : 978-3-030-70276-2

Online ISBN : 978-3-030-70277-9

eBook Packages : Business and Management Business and Management (R0)

Share this chapter

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