Pseudo-Boolean optimization

Adams, 1990, Unconstrained 0–1 optimization and Lagrangean relaxation, First International Colloquium on Pseudo-Boolean Optimization and Related Topics (Chexbres, 1987), Discrete Appl. Math., 29, 131, 10.1016/0166-218X(90)90139-4 Adams, 1994, On the equivalence between roof duality and Lagrangian duality for unconstrained 0–1 quadratic programming problems, Discrete Appl. Math., 48, 1, 10.1016/0166-218X(92)00119-7 Adams, 1986, A tight linearization and an algorithm for zero-one quadratic programming problems, Management Sci., 32, 1274, 10.1287/mnsc.32.10.1274 G. Alexe, P.L. Hammer, Boolean simplifications of the stability problem in graphs. RUTCOR Research Report, RUTCOR, August, 2001. Alon, 1992 Amit, 1989 S. Arora, C. Lund, R. Motwani, M. Sudan, M. Szegedy, Proof verification and hardness of approximation problems, Proceedings of the 33rd Annual IEEE Symposium on Foundations of Computer Science, Pittsburgh, PA, 1992, pp. 14–23. S. Arora, M. Safra, Probabilistic checking of proofs: a new characterization of NP, Proceedings of the 33rd Annual IEEE Symposium on Foundations of Computer Science, Pittsburgh, PA, 1992, pp. 2–13. T. Badics, Approximation of some Nonlinear Binary Optimization Problems, Ph.D. Thesis, RUTCOR, Rutgers University, 1996. Badics, 1998, Minimization of Half-Products, Math. Oper. Res., 23, 649, 10.1287/moor.23.3.649 Balas, 1967, Extension de l'algorithme additif a la programmation en nombres at a la programmation non lineare, C. R. Acad. Sci. Paris, 258, 5136 Balas, 1984, Nonlinear 0–1 programming: I. Linearization techniques and II. Dominance relations and algorithms, Math. Programming, 30, 1, 10.1007/BF02591796 Balas, 1972, On the set covering problem, Oper. Res., 20, 1152, 10.1287/opre.20.6.1152 Balas, 1976, Set partitioning: a survey, SIAM Rev., 18, 710, 10.1137/1018115 Banzhaf III, 1965, Weighted voting does not work: a mathematical analysis, Rutgers Law Rev., 19, 317 Barahona, 1986, A solvable case of quadratic 0–1 programming, Discrete Appl. Math., 13, 23, 10.1016/0166-218X(86)90065-X Barahona, 1988, An application of combinatorial optimization to statistical physics and circuit layout design, Oper. Res., 36, 493, 10.1287/opre.36.3.493 Barahona, 1985, Facets of the bipartite subgraph polytope, Math. Oper. Res., 10, 340, 10.1287/moor.10.2.340 Barahona, 1986, On the cut polytope, Math. Programming, 36, 157, 10.1007/BF02592023 M. Bellare, O. Goldreaich, M. Sudan, Free bits, PCPsw and non-approximability—towards tight results, Proceedings of the 36th Annual IEEE Symposium on Foundations of Computer Science, Milwaukee, WI, 1995, pp. 422–431. C. Benzaken, Y. Crama, P.L. Hammer, F. Maffray, More characterizations of triangulated graphs, RUTCOR Research Report 46-87, Rutgers University, 1987. Benzaken, 1983, Adjoints of pure bidirected graphs, Congr. Numer., 39, 123 Benzaken, 1980, Some remarks on conflict graphs of quadratic pseudo-Boolean functions, Internat. Ser. Numer. Math., 55, 9, 10.1007/978-3-0348-6322-3_1 Billionnet, 1985, Maximizing a supermodular pseudo-boolean function: a polynomial algorithm for supermodular cubic functions, Discrete Appl. Math., 12, 1, 10.1016/0166-218X(85)90035-6 Billionnet, 1992, Persistency in quadratic 0–1 optimization, Math. Programming Ser. A, 54, 115, 10.1007/BF01586044 Boros, 1999, Maximum renamable Horn sub-CNFs, Discrete Appl. Math., 96–97, 29, 10.1016/S0166-218X(99)00031-1 Boros, 2001, Covering non-uniform hypergraphs, J. Combin. Theory (B), 82, 270, 10.1006/jctb.2001.2037 Boros, 1990, Upper bounds for quadratic 0–1 maximization, Oper. Res. Lett., 9, 73, 10.1016/0167-6377(90)90044-6 Boros, 1992, Chvátal cuts and odd cycle inequalities in quadratic 0–1 optimization, SIAM J. Discrete Math., 5, 163, 10.1137/0405014 E. Boros, P.L. Hammer, A max-flow approach to improved roof-duality in quadratic 0–1 minimization, RUTCOR Research Report RRR 15-1989, RUTCOR, March 1989. Boros, 1991, The max-cut problem and quadratic 0–1 optimization, polyhedral aspects, relaxations and bounds, Ann. Oper. Res., 33, 151, 10.1007/BF02115753 E. Boros, P.L. Hammer, A generalization of the pure literal rule for satisfiability problems, RUTCOR Research Report RRR 20-92, RUTCOR, April 1992; DIMACS Technical Report 92-19. Boros, 1993, Cut-polytopes, Boolean quadric polytopes and nonnegative quadratic pseudo-Boolean functions, Math. Oper. Res., 18, 245, 10.1287/moor.18.1.245 Boros, 1999, Optimal cell flipping to minimize channel density in VLSI design and pseudo-Boolean optimization, Discrete Appl. Math., 90, 69, 10.1016/S0166-218X(98)00114-0 E. Boros, P.L. Hammer, X. Sun, The DDT method for quadratic 0–1 optimization, RUTCOR Research Report RRR 39-1989, RUTCOR, October 1989. E. Boros, P.L. Hammer, X. Sun, Network flows and minimization of quadratic pseudo-Boolean functions, RUTCOR Research Report RRR 17-1991, RUTCOR, May 1991. Boros, 1989, Probabilistic bounds and algorithms for the maximum satisfiability problem, Ann. Oper. Res., 21, 109, 10.1007/BF02022095 J-M. Bourjolly, P.L. Hammer, W.R. Pulleyblank, B. Simeone, Boolean-combinatorial bounding of maximum 2-satisfiability, Computer Science and Operations Research, Williamsburg, VA, Pergamon Press, Oxford, 1992, pp. 23–42. M.L. Bushnell, I.P. Shaik, U.S. Patent # 5,422,891, Robust delay-fault built-in testing method and its apparatus. June 6, 1995. (Patents pending in EEC, Canada, Japan and South Korea.) J. Cheng, W. Kubiak, A faster fully polynomial approximation scheme for agreeable weighted completion time variance, Working Paper, Faculty of Business Administration, Memorial University of New-Foundland, 2000. Crama, 1989, Recognition problems for special classes of polynomials in 0–1 variables, Math. Programming, 44, 139, 10.1007/BF01587085 Crama, 1993, Concave extensions for nonlinear 0–1 maximization problems, Math. Programming, 61, 53, 10.1007/BF01582138 Crama, 1989, Recognition of quadratic graphs and adjoints of bidirected graphs, Vol. 555, 140 Crama, 1989, Bimatroidal independence systems, Z. Oper. Res., 33, 149 Crama, 1989, A characterization of a cone of pseudo-Boolean functions via supermodularity-type inequalities, 53 Crama, 1986, Strong unimodularity for matrices and hypergraphs, Discrete Appl. Math., 15, 221, 10.1016/0166-218X(86)90044-2 Crama, 1990, The basic algorithm for pseudo-Boolean programming revisited, Discrete Appl. Math., 29, 171, 10.1016/0166-218X(90)90142-Y Crama, 1995, Valid inequalities and facets for a hypergraph model of the nonlinear knapsack and FMS part-selection problems, Ann. Oper. Res., 58, 99, 10.1007/BF02032163 De Simone, 1989, The cut polytope and the Boolean quadric polytope, Discrete Math., 79, 71, 10.1016/0012-365X(90)90056-N De Simone, 1995, Exact ground states of Ising spin glasses: New experimental results with a branch and cut algorithm, J. Statist. Physics, 80, 487, 10.1007/BF02178370 de Werra, 1984, On some properties of the struction of a graph, SIAM J. Algebraic Discrete Methods, 5, 239, 10.1137/0605025 Deza, 1992, Facets for the cut cone I, Math. Programming Ser. A, 56, 121, 10.1007/BF01580897 Deza, 1992, Facets for the cut cone II: clique-web inequalities, Math. Programming Ser. A, 56, 161, 10.1007/BF01580898 Ebenegger, 1984, Pseudo-Boolean functions and stability of graphs, Ann. Discrete Math., 19, 83 C.S. Fabian, S. Rudeanu, GH. Weisz, Rezolvarea problemelor de programare pseudobooleana liniara cu ajutorul unui calculator electronic, Studii Si Cercetari 10 (tomul 20) (1968). U. Feige, M.X. Goemans, Approximating the value of two prover proof systems, with applications to MAX 2SAT and MAX DICUT, Proceedings of the Third Israel Symposium on Theory of Computing and Systems, Tel Aviv, Israel, 1995, pp. 182–189. Feige, 1996, Interactive proofs and the hardness of approximating cliques, J. ACM, 43, 268, 10.1145/226643.226652 Fisher, 1978, An analysis of approximations for maximizing submodular setfunctions—I, Math. Programming, 14, 265, 10.1007/BF01588971 Fortet, 1959, L'algebre de Boole en recherche operationelle, Cahiers Études Centre Rech. Oper., 1, 5 Fortet, 1960, Applications de l'algebre de Boole en recherche operationelle, Rev. Francaise Rech. Oper., 4, 17 Fraenkel, 1984, Pseudo-Boolean functions and their graphs, Ann. Discrete Math., 20, 137 Gallo, 1989, On the supermodular knapsack problem, Math. Programming Study, 45, 295, 10.1007/BF01589108 Garey, 1979 Glover, 1986, Future paths for integer programming and links to artificial intelligence, Comput. Oper. Res., 5, 533, 10.1016/0305-0548(86)90048-1 Glover, 1989, Tabu search—Part I, ORSA J. Comput., 1, 190, 10.1287/ijoc.1.3.190 F. Glover, B. Alidaee, C. Rego, G. Kochenberger. One-pass heuristics for large scale unconstrained binary quadratic problems, Technical Report, HCES-09-00, Hearin Center for Enterprise Science, September 2000. Glover, 1973, Further reduction of zero–one polynomial programs to zero–one linear programming problems, Oper. Res., 21, 156, 10.1287/opre.21.1.156 Glover, 1974, Note on converting the 0–1 polynomial programming problems to zero–one linear programming problems, Oper. Res., 22, 180, 10.1287/opre.22.1.180 Goemans, 1994, New 34-approximation algorithms for the maximum satisfiability problem, SIAM J. Discrete Math., 7, 656, 10.1137/S0895480192243516 Goemans, 1995, Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming, J. ACM, 42, 1115, 10.1145/227683.227684 Grötschel, 1981, The ellipsoid method and its consequences in combinatorial optimization, Combinatorica, 1, 169, 10.1007/BF02579273 Hammer, 1965, Some network flow problems solved with pseudo-Boolean programming, Oper. Res., 13, 388, 10.1287/opre.13.3.388 Hammer, 1968, Plant location—a pseudo-Boolean approach, Israel J. Technol., 6, 330 Hammer, 1977, Pseudo-Boolean remarks on balanced graphs, Internat. Ser. Numer. Math., 36, 69 P.L. Hammer, The conflict graph of a pseudo-Boolean function, Technical Report, Bell Laboratories, August 1978. P.L. Hammer, P. Hansen, P.M. Pardalos, D.J. Rader Jr., Maximizing the product of two linear functions in 0–1 variables, RUTCOR Research Report RRR 2-97, RUTCOR, February 1997. Hammer, 1981, Upper planes of quadratic 0–1 functions and stability in graphs, 395 Hammer, 1982, On vertices belonging to all or to no maximum stable sets of a graph, SIAM J. Algebraic Discrete Methods, 3, 511, 10.1137/0603052 Hammer, 1984, Roof duality, complementation and persistency in quadratic 0–1 optimization, Math. Programming, 28, 121, 10.1007/BF02612354 Hammer, 1992, Approximations of pseudo-Boolean functions; applications to game theory, ZOR—Methods and Models of Operations Research, 36, 3, 10.1007/BF01541028 P.L. Hammer, B. Kalantari, A bound on the roof duality gap, Combinatorial Optimization, Lecture Notes in Mathematics, Vol. 1403, 1989, pp. 254–257. Hammer, 1988, From linear separability to unimodality: a hierarchy of pseudo-Boolean functions, ORWP 84-3, Ecole Polytechnique Federale de Lausanne. SIAM J. Discrete Math., 1, 177 Hammer, 1985, Stability in CAN-free graphs, J. Combin. Theory (B), 38, 23, 10.1016/0095-8956(85)90089-9 Hammer, 1985, The struction of a graph: application to CN-free graphs, Combinatorica, 5, 141, 10.1007/BF02579377 Hammer, 1972, On the maximization of a pseudo-Boolean function, J. ACM, 19, 265, 10.1145/321694.321700 Hammer, 1977, Pseudo-Boolean functions and game theory. I. Core elements and Shapley value, Cahiers Centre Etudes Rech. Oper., 19, 159 P.L. Hammer, I. Rosenberg, S. Rudeanu, On the determination of the minima of pseudo-Boolean functions, Stud. Cerc. Mat. 14 (1963) 359–364 (in Romanian). Hammer, 1963, Application of discrete linear programming to the minimization of Boolean functions, Rev. Math. Pures Appl., 8, 459 Hammer, 1974, Linear decomposition of a positive group-Boolean function, 51 Hammer, 1970, Some remarks on quadratic programming with 0–1 variables, Rev. Frances d'Informatique Rech. Oper., 4, 67 P.L. Hammer, S. Rudeanu, Boolean Methods in Operations Research and Related Areas, Springer, Berlin, Heidelberg, New York, 1968. Hammer, 1971, Applications of pseudo-Boolean methods to economic problems, Theory and Decision, 1, 296, 10.1007/BF00139572 Hammer, 1980, Quasimonotone boolean functions and bistellar graphs, Ann. Discrete Math., 9, 107, 10.1016/S0167-5060(08)70043-8 P.L. Hammer, B. Simeone, Quadratic functions of binary variables. Combinatorial Optimization, Lecture Notes in Mathematics, Vol. 1403, Springer, Berlin, 1989, pp. 1–56. Hansen, 1979, Methods of nonlinear 0–1 programming, Ann. Discrete Math., 5, 53, 10.1016/S0167-5060(08)70343-1 P. Hansen, The steepest ascent mildest descent heuristic for combinatorial programming, Presented at the Congress on Numerical Methods in Combinatorial Optimization, Capri, March 1986. Hansen, 1990, Boolean query optimization and the 0–1 hyperbolic sum problem, Ann. Math. Artif. Intell., 1, 97, 10.1007/BF01531072 Hansen, 1990, On the equivalence of paved-duality and standard linearization in nonlinear optimization, Discrete Appl. Math., 29, 187, 10.1016/0166-218X(90)90143-Z P. Hansen, B. Simeone, A class of quadratic pseudoboolean functions whose maximization is reducible to a network flow problem, CORR 79-39, Department of Comb. Optim., University of Waterloo. Hansen, 1986, Unimodular functions, Discrete Appl. Math., 14, 269, 10.1016/0166-218X(86)90031-4 J. Håstad, Some optimal inapproximability results, Proceedings of the 28th Annual ACM Symposium on Theory of Computing, El Paso, TX, 1997, pp. 1–10. Hertz, 1986, Quelques utilisations de la struction, Discrete Math., 59, 79, 10.1016/0012-365X(86)90071-3 Hertz, 1995, Polynomially solvable cases for the maximum stable set problem, ARIDAM VI and VII, New Brunswick, NJ, 1991/1992. Discrete Appl. Math., 60, 195 Hertz, 1997, On the use of Boolean methods for the computation of the stability number, Discrete Appl. Math., 76, 183, 10.1016/S0166-218X(96)00124-2 Hillier, 1969 Hoke, 1994, The struction algorithm for the maximum stable set problem revisited, Discrete Math., 131, 105, 10.1016/0012-365X(94)90377-8 J.J. Hopfield, Neural networks and physical systems with emergent collective computational abilities, Proc. Nat. Acad. Sci. U.S.A. (Biophysics) 79 (1982) 2554–2558. S. Iwata, L. Fleischer, S. Fujishige, A strongly polynomial-time algorithm for minimizing submodular functions, Proceedings of the 32nd ACM Symposium on Theory of Computing, May, 2000. Johnson, 1974, Approximation algorithms for combinatorial problems, J. Comput. System Sci., 9, 256, 10.1016/S0022-0000(74)80044-9 D.S. Johnson, C.H. Papadimitriou, M. Yannakakis, How easy is local search, Proceedings of the 26th Annual Symposium on the Foundations of Computer Science, 1985, pp. 39–42. Jurisch, 1997, Algorithms for minclique scheduling problems, Discrete Appl. Math., 72, 115, 10.1016/S0166-218X(96)00040-6 Kalantari, 1986, Quadratic functions with exponential number of local maxima, Oper. Res. Lett., 5, 47, 10.1016/0167-6377(86)90100-8 H. Karloff, U. Zwick, A 7/8-approximation algorithm for MAX 3SAT? Proceedings of the 38th Annual IEEE Symposium on Foundations of Computer Science, Miami Beach, FL, 1997, pp. 406–415. Karp, 1972, Reducibility among combinatorial problems, 85 Kirkpatrick, 1983, Optimization by simulated annealing, Science, 220, 671, 10.1126/science.220.4598.671 Kohli, 1989, Average performance of heuristics for satisfiability, SIAM J. Discrete Math., 2, 508, 10.1137/0402046 Korner, 1985, An effective branch-and-bound algorithm for Boolean quadratic optimization problems, Z. Angew. Math. Mech., 65, 392, 10.1002/zamm.19850650820 Kubiak, 1995, New results on the completion time variance minimization, Discrete Appl. Math., 58, 157, 10.1016/0166-218X(93)E0125-I W. Kubiak, Minimization of ordered, symmetric half-products, Research Report, Faculty of Business Administration, Memorial University of Newfoundland, 2000. Laughhunn, 1970, Quadratic binary programming with applications to capital budgeting problems, Oper. Res., 18, 454, 10.1287/opre.18.3.454 Laughhunn, 1971, Computational experience with capital expenditure programming models under risk, J. Business Finance, 3, 43 Lawler, 1963, The quadratic assignment problem, Manage. Sci., 9, 586, 10.1287/mnsc.9.4.586 Lieberherr, 1981, Complexity of partial satisfaction, J. ACM, 28, 411, 10.1145/322248.322260 Lovász, 1983, Submodular functions and convexity, 235 Lu, 1987, Roof duality for 0–1 nonlinear optimization, Math. Prog., 37, 357, 10.1007/BF02591742 Mattis, 1976, Solvable spin systems with random interaction, Phys. Lett., 56, 412, 10.1016/0375-9601(76)90396-0 Monien, 1985, Solving satisfiability in less than 2n steps, Discrete Applied Math., 10, 287, 10.1016/0166-218X(85)90050-2 A. Nagih, Sur la résolution des programmes fractionnaires en variables 0–1, Ph.D. Thesis, Université Paris 13, 1996. Nemhauser, 1978, Vertex packing: structural properties and algorithms, Math. Programming, 8, 232, 10.1007/BF01580444 Nemhauser, 1981, Maximizing submodular set functions: formulations and analysis of algorithms, Ann. Discr. Math., 11, 279 Nesterov, 1994 von Neumann, 1944 Nieminen, 1974, A linear pseudo-Boolean viewpoint on matching and other central concepts in graph theory, Zastos. Mat., 14, 365 Owen, 1982 Padberg, 1989, The Boolean quadric polytope: some characteristics, facets and relatives, Math. Programming, 45, 139, 10.1007/BF01589101 Papadimitriou, 1991, Optimization, approximation, and complexity classes, J. Comput. System Sci., 43, 425, 10.1016/0022-0000(91)90023-X Papaioannou, 1977, Optimal test generation in combinational networks by pseudo-Boolean programming, IEEE Trans. Comput., 26, 553, 10.1109/TC.1977.1674880 Personnaz, 1986, Collective computational properties of neural networks: new learning mechanisms, Phys. Rev. A, 34, 4217, 10.1103/PhysRevA.34.4217 Picard, 1977, On the integer-valued variables in the linear vertex packing problem, Math. Programming, 12, 97, 10.1007/BF01593772 Picard, 1975, Minimum cuts and related problems, Networks, 5, 357, 10.1002/net.3230050405 Picard, 1978, A cut approach to the rectilinear facility location problem, Oper. Res., 26, 422, 10.1287/opre.26.3.422 Raghavan, 1988, Probabilistic construction of deterministic algorithms: approximating packing integer programs, J. Comput. System. Sci., 37, 130, 10.1016/0022-0000(88)90003-7 Raghavan, 1987, Randomized rounding: A technique for provably good algorithms and algorithmic proofs, Combinatorica, 7, 365, 10.1007/BF02579324 Ranyard, 1976, An algorithm for maximum likelihood ranking and Slater's i from paired comparisions, British J. Math. Statist. Psychol., 29, 242, 10.1111/j.2044-8317.1976.tb00715.x Rao, 1971, Cluster analysis and mathematical programming, J. Amer. Statist. Assoc., 66, 622, 10.1080/01621459.1971.10482319 Rhys, 1970, A selection problem of shared fixed costs and network flows, Manage. Sci., 17, 200, 10.1287/mnsc.17.3.200 Robillard, 1971, (0,1) hyperbolic programming problems, Naval Res. Logist. Quart., 18, 47, 10.1002/nav.3800180104 Rosenberg, 1972, 0–1 optimization and non-linear programming, Rev. Française Automatique, Informatique Rech. Opér. (Série Bleue), 2, 95 Rosenberg, 1975, Reduction of bivalent maximization to the quadratic case, Cahiers Centre Etudes Rech. Oper., 17, 71 Rosenberg, 1980, Linear decompositions of positive real function of binary arguments, Utilitas Math., 17, 17 Rödl, 1987, Multiple optima in local search, J. Algorithms, 8, 250, 10.1016/0196-6774(87)90041-1 Schrijver, 2000, A combinatorial algorithm minimizing submodular functions in strongly polynomial time, J. Combin. Theory (B), 80, 346, 10.1006/jctb.2000.1989 I.P. Shaik, An optimization approach to robust delay-fault built-in testing, Ph.D. in Electrical Engineering, Rutgers University, 1996. Shapley, 1953, A value for n-person games I. Shepanik, Use of pseudo-boolean preference functions in metagame analysis, Ph.D. Thesis, Department of System Design, 1973. B. Simeone, Quadratic 0–1 programming, Boolean functions and graphs, Ph.D. Thesis in Combinatorics and Optimization, Waterloo, 1979. Tovey, 1985, Hill climbing with multiple local optima, SIAM J. Algebraic Discrete Methods, 6, 384, 10.1137/0606040 Tovey, 1986, Low order polynomial bounds on the expected performance of local improvement algorithms, Math. Programming, 35, 193, 10.1007/BF01580647 L. Trevisan, G.B. Sorkin, M. Sudan, D.P. Williamson, Gadgets, approximation, and linear programming (extended abstract). Proceedings of the 37th Annual IEEE Symposium on Foundations of Computer Science, Burlington, VT, 1996, pp. 617–626. Trubin, 1969, On a method of solution of integer linear programming problems of special kind, Soviet Math. Dokl., 10, 1544 Tuza, 1999, Maximum cuts: improvements and local algorithmic analogues of the Edwards–Erdös inequality, Discrete Math., 194, 39, 10.1016/S0012-365X(98)00115-0 Warszawski, 1974, Pseudo-Boolean solutions to multidimensional location problems, Oper. Res., 22, 1081, 10.1287/opre.22.5.1081 Watters, 1967, Reduction of integer polynomial problems to zero-one linear programming problems, Oper. Res., 15, 1171, 10.1287/opre.15.6.1171 Welsh, 1976 Weingartner, 1966, Capital budgeting of interrelated projects: survey and synthesis, Manage. Sci., 12, 485, 10.1287/mnsc.12.7.485 Yannakakis, 1994, On the approximation of maximum satisfiability, J. Algorithms, 17, 475, 10.1006/jagm.1994.1045 Young, 1984, Spin glasses, J. Statist. Phys., 34, 871, 10.1007/BF01009446 U. Zwick, Approximation algorithms for constraint satisfaction problems involving at most three variables per constraint, Proceedings of the Ninth SODA, 1998, pp. 201–210.