@article{manne_job-shop_1960,

title = {On the {Job}-{Shop} {Scheduling} {Problem}},

volume = {8},

issn = {0030-364X, 1526-5463},

url = {http://pubsonline.informs.org/doi/10.1287/opre.8.2.219},

doi = {10.1287/opre.8.2.219},

abstract = {This is a proposal for the application of discrete linear programming to the typical job-shop scheduling problem—one that involves both sequencing restrictions and also noninterference constraints for individual pieces of equipment. Thus far, no attempt has been made to establish the computational feasibility of the approach in the case of large-scale realistic problems. This formulation seems, however, to involve considerably fewer variables than two other recent proposals [Bowman, E. H. 1959. The schedule-sequencing problem. Opns Res. 7 621–624; Wagner, H. 1959. An integer linear-programming model for machine scheduling. Naval Res. Log. Quart. (June).], and on these grounds may be worth some computer experimentation.},

language = {en},

number = {2},

urldate = {2023-03-15},

journal = {Operations Research},

author = {Manne, Alan S.},

month = apr,

year = {1960},

pages = {219--223},

file = {Manne - 1960 - On the Job-Shop Scheduling Problem.pdf:/Users/klian/Zotero/storage/7TZJE3G9/Manne - 1960 - On the Job-Shop Scheduling Problem.pdf:application/pdf},

}

@article{ku_mixed_2016,

title = {Mixed {Integer} {Programming} models for job shop scheduling: {A} computational analysis},

volume = {73},

issn = {03050548},

shorttitle = {Mixed {Integer} {Programming} models for job shop scheduling},

url = {https://linkinghub.elsevier.com/retrieve/pii/S0305054816300764},

doi = {10.1016/j.cor.2016.04.006},

language = {en},

urldate = {2023-03-16},

journal = {Computers \& Operations Research},

author = {Ku, Wen-Yang and Beck, J. Christopher},

month = sep,

year = {2016},

pages = {165--173},

file = {Ku and Beck - 2016 - Mixed Integer Programming models for job shop sche.pdf:/Users/klian/Zotero/storage/9XIRH64S/Ku and Beck - 2016 - Mixed Integer Programming models for job shop sche.pdf:application/pdf},

}

@inproceedings{kondili_general_1988,

address = {Barton, ACT},

title = {A {General} {Algorithm} for {Scheduling} {Batch} {Operations}},

isbn = {0-85825-410-7},

url = {https://search.informit.org/doi/10.3316/informit.394925233030714},

abstract = {A general framework for handling a wide variety of scheduling problems arising in multiproduct/multipurpose batch chemical plants is presented. This new approach has the flexibility to accommodate various process characteristics. Furthermore, it is able to deal in a natural manner with a number of objectives and constraints imposed on the plant. Batch plant involving a variety of complexities is represented using a State Task Network. The novel feature of this representation is that both the individual batch operations (“tasks”) and the feedstocks, intermediate and final products (“states”) are included explicitly as network nodes. The mathematical formulation of the problem has resulted in a mixed integer linear programming model. A special schedule generating algorithm has been developed, using the branch and bound technique to obtain the optimal solution. The amount of search required by the algorithm has been substantially reduced by introducing branch cutting rules devised from physical considerations of the process, without compromising the optimality of the solution obtained.},

language = {English},

urldate = {2023-03-23},

author = {Kondili, E and Pantelides, CC and Sargent, R WH},

month = jan,

year = {1988},

keywords = {Branch and bound algorithms, Chemical process control--Computer simulation, Chemical process control--Data processing, Chemical process control--Mathematical models, Computer integrated manufacturing systems, Programming (Mathematics)},

}

@article{wagner_integer_1959,

title = {An integer linear-programming model for machine scheduling},

volume = {6},

issn = {00281441, 19319193},

url = {https://onlinelibrary.wiley.com/doi/10.1002/nav.3800060205},

doi = {10.1002/nav.3800060205},

language = {en},

number = {2},

urldate = {2023-03-23},

journal = {Naval Research Logistics Quarterly},

author = {Wagner, Harvey M.},

month = jun,

year = {1959},

pages = {131--140},

}

@book{toth_vehicle_2014,

title = {Vehicle routing: problems, methods, and applications},

shorttitle = {Vehicle routing},

publisher = {SIAM},

author = {Toth, Paolo and Vigo, Daniele},

year = {2014},

file = {Full Text:/Users/klian/Zotero/storage/N3NDUAN2/Toth and Vigo - 2014 - Vehicle routing problems, methods, and applicatio.pdf:application/pdf},

}

@article{miller_integer_1960,

title = {Integer {Programming} {Formulation} of {Traveling} {Salesman} {Problems}},

volume = {7},

issn = {0004-5411},

url = {https://dl.acm.org/doi/10.1145/321043.321046},

doi = {10.1145/321043.321046},

abstract = {It has been observed by many people that a striking number of quite diverse mathematical problems can be formulated as problems in integer programming, that is, linear programming problems in which some or all of the variables are required to assume integral values. This fact is rendered quite interesting by recent research on such problems, notably by R. E. Gomory [2, 3], which gives promise of yielding efficient computational techniques for their solution. The present paper provides yet another example of the versatility of integer programming as a mathematical modeling device by representing a generalization of the well-known “Travelling Salesman Problem” in integer programming terms. The authors have developed several such models, of which the one presented here is the most efficient in terms of generality, number of variables, and number of constraints. This model is due to the second author [4] and was presented briefly at the Symposium on Combinatorial Problems held at Princeton University, April 1960, sponsored by SIAM and IBM. The problem treated is: (1) A salesman is required to visit each of n cities, indexed by 1, … , n. He leaves from a “base city” indexed by 0, visits each of the n other cities exactly once, and returns to city 0. During his travels he must return to 0 exactly t times, including his final return (here t may be allowed to vary), and he must visit no more than p cities in one tour. (By a tour we mean a succession of visits to cities without stopping at city 0.) It is required to find such an itinerary which minimizes the total distance traveled by the salesman. Note that if t is fixed, then for the problem to have a solution we must have tp ≧ n. For t = 1, p ≧ n, we have the standard traveling salesman problem. Let dij (i ≠ j = 0, 1, … , n) be the distance covered in traveling from city i to city j. The following integer programming problem will be shown to be equivalent to (1): (2) Minimize the linear form ∑0≦i≠j≦n∑ dijxij over the set determined by the relations ∑ni=0i≠j xij = 1 (j = 1, … , n) ∑nj=0j≠i xij = 1 (i = 1, … , n) ui - uj + pxij ≦ p - 1 (1 ≦ i ≠ j ≦ n) where the xij are non-negative integers and the ui (i = 1, …, n) are arbitrary real numbers. (We shall see that it is permissible to restrict the ui to be non-negative integers as well.) If t is fixed it is necessary to add the additional relation: ∑nu=1 xi0 = t Note that the constraints require that xij = 0 or 1, so that a natural correspondence between these two problems exists if the xij are interpreted as follows: The salesman proceeds from city i to city j if and only if xij = 1. Under this correspondence the form to be minimized in (2) is the total distance to be traveled by the salesman in (1), so the burden of proof is to show that the two feasible sets correspond; i.e., a feasible solution to (2) has xij which do define a legitimate itinerary in (1), and, conversely a legitimate itinerary in (1) defines xij, which, together with appropriate ui, satisfy the constraints of (2). Consider a feasible solution to (2). The number of returns to city 0 is given by ∑ni=1 xi0. The constraints of the form ∑ xij = 1, all xij non-negative integers, represent the conditions that each city (other than zero) is visited exactly once. The ui play a role similar to node potentials in a network and the inequalities involving them serve to eliminate tours that do not begin and end at city 0 and tours that visit more than p cities. Consider any xr0r1 = 1 (r1 ≠ 0). There exists a unique r2 such that xr1r2 = 1. Unless r2 = 0, there is a unique r3 with xr2r3 = 1. We proceed in this fashion until some rj = 0. This must happen since the alternative is that at some point we reach an rk = rj, j + 1 {\textless} k. Since none of the r's are zero we have uri - uri + 1 + pxriri + 1 ≦ p - 1 or uri - uri + 1 ≦ - 1. Summing from i = j to k - 1, we have urj - urk = 0 ≦ j + 1 - k, which is a contradiction. Thus all tours include city 0. It remains to observe that no tours is of length greater than p. Suppose such a tour exists, x0r1 , xr1r2 , … , xrprp+1 = 1 with all ri ≠ 0. Then, as before, ur1 - urp+1 ≦ - p or urp+1 - ur1 ≧ p. But we have urp+1 - ur1 + pxrp+1r1 ≦ p - 1 or urp+1 - ur1 ≦ p (1 - xrp+1r1) - 1 ≦ p - 1, which is a contradiction. Conversely, if the xij correspond to a legitimate itinerary, it is clear that the ui can be adjusted so that ui = j if city i is the jth city visited in the tour which includes city i, for we then have ui - uj = - 1 if xij = 1, and always ui - uj ≦ p - 1. The above integer program involves n2 + n constraints (if t is not fixed) in n2 + 2n variables. Since the inequality form of constraint is fundamental for integer programming calculations, one may eliminate 2n variables, say the xi0 and x0j, by means of the equation constraints and produce an equivalent problem with n2 + n inequalities and n2 variables. The currently known integer programming procedures are sufficiently regular in their behavior to cast doubt on the heuristic value of machine experiments with our model. However, it seems appropriate to report the results of the five machine experiments we have conducted so far. The solution procedure used was the all-integer algorithm of R. E. Gomory [3] without the ranking procedure he describes. The first three experiments were simple model verification tests on a four-city standard traveling salesman problem with distance matrix [ 20 23 4 30 7 27 25 5 25 3 21 26 ] The first experiment was with a model, now obsolete, using roughly twice as many constraints and variables as the current model (for this problem, 28 constraints in 21 variables). The machine was halted after 4000 pivot steps had failed to produce a solution. The second experiment used the earlier model with the xi0 and x0j eliminated, resulting in a 28-constraint, 15-variable problem. Here the machine produced the optimal solution in 41 pivot steps. The third experiment used the current formulation with the xi0 and x0j eliminated, yielding 13 constraints and 9 variables. The optimal solution was reached in 7 pivot steps. The fourth and fifth experiments were used on a standard ten-city problem, due to Barachet, solved by Dantzig, Johnson and Fulkerson [1]. The current formulation was used, yielding 91 constraints in 81 variables. The fifth problem differed from the fourth only in that the ordering of the rows was altered to attempt to introduce more favorable pivot choices. In each case the machine was stopped after over 250 pivot steps had failed to produce the solution. In each case the last 100 pivot steps had failed to change the value of the objective function. It seems hopeful that more efficient integer programming procedures now under development will yield a satisfactory algorithmic solution to the traveling salesman problem, when applied to this model. In any case, the model serves to illustrate how problems of this sort may be succinctly formulated in integer programming terms.},

number = {4},

urldate = {2023-04-01},

journal = {Journal of the ACM},

author = {Miller, C. E. and Tucker, A. W. and Zemlin, R. A.},

month = oct,

year = {1960},

pages = {326--329},

file = {Full Text PDF:/Users/klian/Zotero/storage/RCGDJI9G/Miller et al. - 1960 - Integer Programming Formulation of Traveling Sales.pdf:application/pdf},

}

@article{dantzig_solution_1954,

title = {Solution of a {Large}-{Scale} {Traveling}-{Salesman} {Problem}},

volume = {2},

issn = {0096-3984},

url = {https://pubsonline.informs.org/doi/10.1287/opre.2.4.393},

doi = {10.1287/opre.2.4.393},

abstract = {It is shown that a certain tour of 49 cities, one in each of the 48 states and Washington, D.C., has the shortest road distance.

Operations Research, ISSN 0030-364X, was published as Journal of the Operations Research Society of America from 1952 to 1955 under ISSN 0096-3984.},

number = {4},

urldate = {2023-04-05},

journal = {Journal of the Operations Research Society of America},

author = {Dantzig, G. and Fulkerson, R. and Johnson, S.},

month = nov,

year = {1954},

note = {Publisher: INFORMS},

pages = {393--410},

}

@article{dudzinski_exact_1987,

title = {Exact methods for the knapsack problem and its generalizations},

volume = {28},

issn = {0377-2217},

url = {https://www.sciencedirect.com/science/article/pii/0377221787901652},

doi = {10.1016/0377-2217(87)90165-2},

abstract = {A unified approach and a summary of the most important results concerned with exact methods for solving the (binary) knapsack problem and its generalizations are given. We stress the importance of dual methods for solving linear programming relaxations of the considered problems. Two ways of generalization of the knapsack problem are described. If the special ordered sets are added, then the multiple-choice knapsack problem is obtained. If the constraints have the nested structure, then we get the nested knapsack problem. Also the multiple-choice nested knapsack problem is discussed.},

language = {en},

number = {1},

urldate = {2023-04-13},

journal = {European Journal of Operational Research},

author = {Dudziński, Krzysztof and Walukiewicz, Stanisław},

month = jan,

year = {1987},

keywords = {branch-and-bound, Integer programming, Lagrangean relaxation, linear programming relaxation, reduction},

pages = {3--21},

file = {Dudziński and Walukiewicz - 1987 - Exact methods for the knapsack problem and its gen.pdf:/Users/klian/Zotero/storage/PMGAKCGZ/Dudziński and Walukiewicz - 1987 - Exact methods for the knapsack problem and its gen.pdf:application/pdf;ScienceDirect Snapshot:/Users/klian/Zotero/storage/4YCGFBFZ/0377221787901652.html:text/html},

}

@article{petersen_computational_1967,

title = {Computational {Experience} with {Variants} of the {Balas} {Algorithm} {Applied} to the {Selection} of {R}\&{D} {Projects}},

volume = {13},

issn = {0025-1909},

url = {https://pubsonline.informs.org/doi/abs/10.1287/mnsc.13.9.736},

doi = {10.1287/mnsc.13.9.736},

abstract = {Allocating funds to independent R\&D projects is a problem of practical importance for many firms. We formulate the problem as a 0-1 integer programming problem with the objective of selecting projects that will maximize the anticipated dollar contract volume, yet not exceed cost budgets. Our form-mulation accommodates R\&D projects extending over several budget periods and permits carryover of unspent funds from one budget period to later periods. Experience in solving such problems by using the Balas [Balas, Egon. 1965. An additive algorithm for solving linear programs with zero-one variables. Oper. Res.13 (4, July–August) 517–549.] algorithm in its literal form and in reformulated form is summarized. Several other modifications to the algorithm are described and; their effect on efficiency is shown through presentation of computational experience on problems with as many as 50 variables.},

number = {9},

urldate = {2023-04-15},

journal = {Management Science},

author = {Petersen, Clifford C.},

month = may,

year = {1967},

note = {Publisher: INFORMS},

pages = {736--750},

}

@article{sinha_multiple-choice_1979,

title = {The {Multiple}-{Choice} {Knapsack} {Problem}},

volume = {27},

issn = {0030-364X},

url = {https://www.jstor.org/stable/170213},

abstract = {The multiple-choice knapsack problem is defined as a binary knapsack problem with the addition of disjoint multiple-choice constraints. The strength of the branch-and-bound algorithm we present for this problem resides with the quick solution of the linear programming relaxation and its efficient, subsequent reoptimization as a result of branching. An implemented version of this algorithm has performed well on a large set of test problems. We cite computational results as well as a comparison with a previously reported algorithm. Several useful applications of the multiple-choice knapsack problem are also suggested.},

number = {3},

urldate = {2023-04-15},

journal = {Operations Research},

author = {Sinha, Prabhakant and Zoltners, Andris A.},

year = {1979},

note = {Publisher: INFORMS},

pages = {503--515},

file = {JSTOR Full Text PDF:/Users/klian/Zotero/storage/AM4UE6PI/Sinha and Zoltners - 1979 - The Multiple-Choice Knapsack Problem.pdf:application/pdf},

}

@article{chen_reduce_2014,

title = {A “reduce and solve” approach for the multiple-choice multidimensional knapsack problem},

volume = {239},

issn = {0377-2217},

url = {https://www.sciencedirect.com/science/article/pii/S0377221714004482},

doi = {10.1016/j.ejor.2014.05.025},

abstract = {The multiple-choice multidimensional knapsack problem (MMKP) is a well-known NP-hard combinatorial optimization problem with a number of important applications. In this paper, we present a “reduce and solve” heuristic approach which combines problem reduction techniques with an Integer Linear Programming (ILP) solver (CPLEX). The key ingredient of the proposed approach is a set of group fixing and variable fixing rules. These fixing rules rely mainly on information from the linear relaxation of the given problem and aim to generate reduced critical subproblem to be solved by the ILP solver. Additional strategies are used to explore the space of the reduced problems. Extensive experimental studies over two sets of 37 MMKP benchmark instances in the literature show that our approach competes favorably with the most recent state-of-the-art algorithms. In particular, for the set of 27 conventional benchmarks, the proposed approach finds an improved best lower bound for 11 instances and as a by-product improves all the previous best upper bounds. For the 10 additional instances with irregular structures, the method improves 7 best known results.},

language = {en},

number = {2},

urldate = {2023-04-15},

journal = {European Journal of Operational Research},

author = {Chen, Yuning and Hao, Jin-Kao},

month = dec,

year = {2014},

keywords = {Fixing heuristics, Hybridization, Knapsack, Linear relaxation},

pages = {313--322},

file = {ScienceDirect Snapshot:/Users/klian/Zotero/storage/4CHTEABF/S0377221714004482.html:text/html},

}

@article{letavec_n_2002,

title = {The \textit{n} -{Queens} {Problem}},

volume = {2},

issn = {1532-0545, 1532-0545},

url = {https://pubsonline.informs.org/doi/10.1287/ited.2.3.101},

doi = {10.1287/ited.2.3.101},

language = {en},

number = {3},

urldate = {2023-04-15},

journal = {INFORMS Transactions on Education},

author = {Letavec, Craig and Ruggiero, John},

month = may,

year = {2002},

pages = {101--103},

file = {Submitted Version:/Users/klian/Zotero/storage/3IUP2I3D/Letavec and Ruggiero - 2002 - The n -Queens Problem.pdf:application/pdf},

}

@article{falkenauer_hybrid_1996,

title = {A hybrid grouping genetic algorithm for bin packing},

volume = {2},

issn = {1381-1231, 1572-9397},

url = {http://link.springer.com/10.1007/BF00226291},

doi = {10.1007/BF00226291},

language = {en},

number = {1},

urldate = {2023-04-20},

journal = {Journal of Heuristics},

author = {Falkenauer, Emanuel},

year = {1996},

pages = {5--30},

file = {Falkenauer - 1996 - A hybrid grouping genetic algorithm for bin packin.pdf:/Users/klian/Zotero/storage/UFKJN4RB/Falkenauer - 1996 - A hybrid grouping genetic algorithm for bin packin.pdf:application/pdf},

}

@misc{noauthor_bin_nodate,

title = {Bin packing - one-dimensional},

url = {http://people.brunel.ac.uk/~mastjjb/jeb/orlib/binpackinfo.html},

urldate = {2023-04-20},

file = {Bin packing - one-dimensional:/Users/klian/Zotero/storage/HIKJNK9Z/binpackinfo.html:text/html},

}

@article{beasley_or-library_1990,

title = {{OR}-{Library}: {Distributing} {Test} {Problems} by {Electronic} {Mail}},

volume = {41},

issn = {0160-5682},

shorttitle = {{OR}-{Library}},

url = {https://www.jstor.org/stable/2582903},

doi = {10.2307/2582903},

number = {11},

urldate = {2023-04-20},

journal = {The Journal of the Operational Research Society},

author = {Beasley, J. E.},

year = {1990},

note = {Publisher: Palgrave Macmillan Journals},

pages = {1069--1072},

file = {JSTOR Full Text PDF:/Users/klian/Zotero/storage/IKA23ZDD/Beasley - 1990 - OR-Library Distributing Test Problems by Electron.pdf:application/pdf},

}