Back to Discrete Optimization
Summary: The objective of the bar crawl optimization problem is to select a set of bars and determine an ordering to visit them so as to optimize the objective function subject to any constraints on the bar crawl. The objective function may include a single criterion or multiple criteria, and the constraints may include requirements to include one or more specific locations, limits on the cost of drinks, restrictions on operating hours, etc.
Summary: Given a \(n \times n\) grid of panes, the objective of the Abbott's Window puzzle is to maximize the number of lighted panes subject to the constraint that the number of lighted panes in every row, column, and diagonal is even.
Summary: The origin of the cutting stock problem is in the paper industry. Given paper rolls of fixed width and a set of orders for rolls of smaller widths, the objective of the Cutting Stock Problem is to determine how to cut the rolls into smaller widths to fulfill the orders in such a way as to minimize the amount of scrap.
Summary: The objective of sudoku is to fill a 9 x 9 grid so that each column, each row, and each of the nine 3 x 3 boxes contains all of the digits from 1 to 9 exactly once.