The Pseudo-Boolean Optimization Website

 Bibliography

Back Home Next

 

2/13/2005

The PBO bibliography is in its starting stage. Further additions to it can be expected in the subsequent months. To speed up the processing of this list, please let us know about any unlisted PBO references, or any mistakes/errors you may find in the current list.

Bibliography on PBO

Adams , W., A. Billionnet and A. Sutter, (1990), "Unconstrained 0-1 optimization and Lagrangean relaxation", Discrete Appl. Math. 29, pp 131-142, December.

Alidaee, B., G. A. Kochenberger, K. Lewis and M. Lewis, (2004), "Modeling and solving set packing problems via unconstrained quadratic programming", Working Paper, May.

AlKhamis, T. M., M. Hasan and M. A. Ahmed, (1998), "Simulated annealing for the unconstrained quadratic pseudo-Boolean function", Eur. J. Oper. Res. 108(3), pp 641-652, August.

Al-Khayyal, F. A. and C. Larsen, (1990), "Global optimization of a quadratic function subject to a bounded mixed integer constraint set", Ann. Oper. Res. 25, pp 163-168.

Allemand, K., K. Fukuda, T. M. Liebling and E. Steiner, (2001), "A polynomial case of unconstrained zero-one quadratic optimization", Math. Program. 91(1), pp 49-52.

Amini, M. M., B. Alidaee and G. A. Kochenberger, (1999), "A scatter search approach to unconstrained quadratic binary programs", In (Corne, D., M. Dorigo and F. W. Glover, ed.), New ideas in optimization, McGraw-Hill, pp 317-329.

Balas, E. and R. Jeroslow, (1972), "Canonical cuts on the unit hypercube", SIAM J. Appl. Math. 23(1), pp 61-69, July.

Barahona, F., (1986), "A solvable case of quadratic 0-1 programming", Discrete Appl. Math. 13(1), pp 23-26.

Barahona, F., M. Grötschel, M. Jünger and G. Reinelt, (1988), "An application of combinatorial optimization to statistical physics and circuit layout design.", Oper. Res. 36(3), pp 493-513, May/Jun.

Barahona, F., M. Jünger and G. Reinelt, (1989), "Experiments in quadratic 0-1 programming", Math. Program. 44, pp 127-137.

Beasley, J. E., (1998), "Heuristic algorithms for the unconstrained binary quadratic programming problem", Technical Report, Management School , Imperial College , December.

Billionnet, A. and A. Faye, (1997), "A lower bound for a constrained quadratic 0-1 minimization problem", Discrete Appl. Math. 74(2), pp 135-146, April.

Billionnet, A. and A. Sutter, (1994), "Minimization of a quadratic pseudo-Boolean function", Eur. J. Oper. Res. 78(1), pp 106-115, October.

Billionnet, A. and B. Jaumard, (1989), "A decomposition method for minimizing quadratic pseudo-Boolean functions", Oper. Res. Lett. 8(3), pp 161-163, June.

Billionnet, A. and M. Minoux, (1985), "Maximizing a supermodular pseudoboolean function: A polynomial algorythm for supermodular cubic functions", Discrete Appl. Math. 12, pp 1-11.

Borchers, B. and J. Furman, (1998), "A two-phase exact algorithm for MAX-SAT and weighted MAX-SAT problems", Journal of Combinatorial Optimization 2(4), pp 299-306.

Boros, E. and P. L. Hammer, (1989), "A max-flow approach to improved roof-duality in quadratic 0-1 minimization", RUTCOR Research Report RRR 15-1989, RUTCOR - Rutgers Center for Operations Research, Rutgers University , March.

Boros, E. and P. L. Hammer, (1993), "Cut-polytopes, Boolean quadric polytopes and nonnegative quadratic pseudo-Boolean functions", Mathematics of Operations Research 18(1), pp 245-253, February.

Boros, E. and P. L. Hammer, (2002), "Pseudo-Boolean optimization", Discrete Appl. Math. 123, pp 155-225.

Boros, E., I. Lari and B. Simeone, (2000), "Block linear majorants in quadratic 0-1 optimization", RUTCOR Research Report RRR 18-2000, RUTCOR - Rutgers Center for Operations Research, Rutgers University, March.

Boros, E., P. L. Hammer and X. Sun, (1989), "The DDT method for quadratic 0-1 optimization", RUTCOR Research Report RRR 39-1989, RUTCOR - Rutgers Center for Operations Research, Rutgers University, October.

Boros, E., P. L. Hammer, M. Minoux, D. J. Rader and Jr., (1998), "Optimal cell flipping to minimize channel density in VLSI design and pseudo-Boolean optimization", RUTCOR Research Report RRR 3-1998, RUTCOR - Rutgers Center for Operations Research, Rutgers University, January.

Boros, E., Y. Crama and P. L. Hammer, (1990), "Upper-bounds for quadratic 0-1 maximization", Oper. Res. Lett. 9, pp 73-79.

Boros, E., Y. Crama and P. L. Hammer, (1992), "Chvátal cuts and odd cycle inequalities in quadratic 0-1 optimization",  SIAM Journal on Discrete Mathematics 5(2), pp 163-177, May.

Bourjolly, J.-M., P. Gill, G. Laporte and H. Mercure, (1996), "An exact quadratic 0-1 algorithm for the stable set problem", In (Johnson, D. S. and M. A. Trick, ed.), Cliques, coloring, and satisfiability, American Mathematical Society, Providence , pp 53-73.

Bourjolly, J.-M., P. L. Hammer, W. R. Pulleyblank and B. Simeone, (1989), "Combinatorial methods for bounding quadratic pseudo-Boolean functions", Research Report CORR 89-21, Faculty of Mathematics, University of Waterloo, May.

Bourjolly, J.-M., P. L. Hammer, W. R. Pulleyblank and B. Simeone, (1989), "Combinatorial methods for bounding quadratic pseudo-Boolean functions", RUTCOR Research Report RRR 27-1989, RUTCOR - Rutgers Center for Operations Research, Rutgers University, August.

Bourjolly, J.-M., P. L. Hammer, W. R. Pulleyblank and B. Simeone, (1992), "Boolean-combinatorial bounding of maximum 2-satisfiability", Serie A no. 9, Department of Statistics, "La Sapienza" University.

Carraresi, P., F. Farinaccio and F. Malucelli, (1995), "Testing optimality for quadratic 0-1 problems", Technical Report TR-95-11, Dipartimento di Informatica, Universitŕ di Pisa, December.

Carraresi, P., F. Farinaccio and F. Malucelli, (1999), "Testing optimality for quadratic 0-1 problems", Math. Program. 85(2), pp 407-421.

Carraresi, P., F. Malucelli and M. Pappalardo, (1995), "Testing optimality for quadratic 0-1 unconstrained problems", ZOR Math. Methods Oper. Res. 42(3), pp 295-311.

Carter, M. W., (1984), "The indefinite zero-one quadratic problem", Discrete Appl. Math. 7(1), pp 23-44, January.

Chakradhar, S. T. and M. L. Bushnell, (1992), "A solvable class of quadratic 0-1 programming", Discrete Appl. Math. 36(3), pp 233-251, May.

Chardaire, P. and A. Sutter, (1995), "A decomposition method for quadratic zero-one programming", Manage. Sci. 41(4), pp 704-712.

Crama, Y. and P. L. Hammer, (2002), "Pseudo-Boolean optimization", In (Pardalos, P. M. and M. G. C. Resende, ed.), Handbook of applied optimization, Oxford University Press, pp 445-450.

Crama, Y., (1993), "Concave extensions for nonlinear 0-1 maximization problems", Math. Program. 61, pp 53-60.

Crama, Y., P. Hansen and B. Jaumard, (1990), "The basic algorithm for pseudo-Boolean programming revisited", Discrete Appl. Math. 29, pp 171-185.

Crama, Y., P. L. Hammer and R. Holzman, (1989), "A characterization of a cone of pseudo-Boolean functions via supermodularity-type inequalities.", In (Kall, P., J. Kohlas, W. Popp and C. A. Zehnder, ed.), Quantitative Methoden in den Wirtschaftswissenschaften, Springer-Verlag, Berlin, pp 53-55.

Crama, Y., P. L. Hammer and T. Ibaraki, (1986), "Strong unimodularity for matrices and hypergraphs", Discrete Appl. Math. 15(2-3), pp 221-239.

Crama, Y., P. L. Hammer, B. Jaumard and B. Simeone, (1987), "Product form parametric representation of the solutions to a quadratic Boolean equation", RAIRO Rech. Oper. 21(4), pp 287-306, November.

Fraenkel, A. S. and P. L. Hammer, (1984), " Pseudo-Boolean functions and their graphs", Ann. Discrete Math. 20, pp 137-146.

Glover, F. W., B. Alidaee, C. Rego and G. A. Kochenberger, (2000), "One-pass heuristics for large-scale unconstrained binary quadratic problems", Eur. J. Oper. Res. 137(2), pp 272-287, March.

Glover, F. W., G. A. Kochenberger and B. Alidaee, (1998), "Adaptive memory tabu search for binary quadratic programs", Manage. Sci. 44(3), pp 336-345, March.

Glover, F. W., G. A. Kochenberger, B. Alidaee and M. M. Amini, (1998), "Tabu search with critical event memory: An enhaced application for binary quadratic programs", In (Voß, S., S. Martello, I. H. Osman and C. Roucairol, ed.), Meta-heuristics: Advancesand trends in local search paradigms for optimization, Kluwer Academic Publishers, pp 93-109.

Gueye, S. and P. Michelon, (2001), "A linearization framework for unconstrained quadratic (0-1) problems", Research Paper, Laboratoire d'Informatique d'Avignon, Université d'Avignon et des Pays de Vaucluse, November.

Guignard, M. and K. Spielberg, (1981), "Logical reduction methods in zero-one programming: Minimal preferred variables", Oper. Res. 29(1), pp 49-74, Jan.-Feb..

Gulati, V. P., S. K. Gupta and A. K. Mittal, (1984), "Unconstrained quadratic bivalent programming problem", Eur. J. Oper. Res. 15(1), pp 121-125.

Hammer, P. L. and B. Kalantari, (1987), "A bound on the roof duality gap", RUTCOR Research Report RRR 46-1987, RUTCOR - Rutgers Center for Operations Research, Rutgers University , December.

Hammer, P. L. and B. Kalantari, (1989), "A bound on the roof duality gap", Combinatorial Optimization, Lecture Notes in Mathematics 1403, pp 254-257.

Hammer, P. L. and B. Simeone, (1987), "Quadratic functions of binary variables", RUTCOR Research Report RRR 20-1987, RUTCOR - Rutgers Center for Operations Research, Rutgers University.

Hammer, P. L. and B. Simeone, (1989), "Quadratic functions of binary variables", Combinatorial Optimization, Lecture Notes in Mathematics 1403, pp 1-56.

Hammer, P. L. and P. Hansen, (1981), "Logical relations in quadratic 0-1 programming", Romanian Journal of Pure and Applied Mathematics 26(3), pp 421-429.

Hammer, P. L. and R. Holzman, (1992), "Approximations of pseudo-Boolean functions; Applications to game theory", ZOR Math. Methods Oper. Res. 36(1), pp 3-21.

Hammer, P. L. and U. N. Peled, (1972), "On the maximization of a pseudo-Boolean function",  Journal of the Association for Computing Machinery 19, pp 265-282.

Hammer, P. L., (1965), "Some network flow problems solved with pseudo-Boolean programming", Oper. Res. 13, pp 388-399.

Hammer, P. L., P. Hansen and B. Simeone, (1984), "Roof duality, complementation and persistency in quadratic 0-1 optimization", Math. Program. 28, pp 121-155.

Hansen, P. and B. Jaumard, (1990), "Algorithms for the maximum satisfiabilty problem", Computing 44, pp 279-303.

Hansen, P., B. Jaumard and C. Meyer, (2000), "A simple enumerative algorithm for unconstrained 0-1 quadratic programming", SFB Report No 203, Department of Mathematics, Graz University of Technology, November.

Hasan, M., T. M. AlKhamis and J. Ali, (2000), "A comparison between simulated annealing, genetic algorithm and tabu search methods for the unconstrained quadratic Pseudo-Boolean function", Computers & Industrial Engineering 38(3), pp 323-340, October.

Hui, L. S., (1984), "An improved enumerative algorithm for solving quadratic zero-one programming", Eur. J. Oper. Res. 15(1), pp 110-120, January.

Johnson, D. S. and M. A. Trick, (1996), Cliques, coloring, and satisfiability, American Mathematical Society, Providence .

Johnson, E. L. and M. W. Padberg, (1982), "Degree-two inequalities, clique facets, and biperfect graphs", Ann. Discrete Math. 16, pp 169-187.

Kalantari, B. and A. Baghchi, (1990), "An algorithm for quadratic zero-one programs", Nav. Res. Logist. 37, pp 527-538.

Kalantari, B., (1986), "Quadratic functions with exponential number of local maxima", Oper. Res. Lett. 5(1), pp 47-49.

Katayama, K. and H. Narihisa, (2001), "Performance of simulated annealing-based heuristic for the unconstrained binary quadratic programming problem", Eur. J. Oper. Res. 134(1), pp 103-119.

Katayama, K., M. Tani and H. Narihisa, (2000), "Solving large binary quadratic programming problems by effective genetic local search algorithm", Proceedings of the 2000 genetic and evolutionary computation conference (GECCO-2000), pp 643-650.

Kochenberger, G. A., F. W. Glover, B. Alidaee and C. Rego, (2003), "An unconstrained quadratic binary programming approach to the vertex coloring problem", Working Paper HCES-01-03, Hearin Center for Enterprise Science, University of Mississipi, February.

Kochenberger, G. A., F. W. Glover, B. Alidaee and C. Rego, (2003), "Solving combinatorial optimization problems via reformulation and adaptive memory metaheuristics", Working Paper HCES-03-03, Hearin Center for Enterprise Science, University of Mississipi, February.

Kochenberger, G. A., F. W. Glover, B. Alidaee and H. Wang, (2004), "Solving the maximum edge weight clique problem via unconstrained quadratic programming", Working Paper HCES-05-04, Hearin Center for Enterprise Science, University of Mississipi, July.

Körner, F., (1988), "A tight bound for the Boolean quadratic optimization problem and its use in a branch and bound algorithm", Optimization 19(5), pp 711-721.

Laughhunn, D. J., (1970), "Quadratic binary programming with applications to capital budgeting problems", Oper. Res. 18(3), pp 454-461, May/Jun.

Lewis, M., B. Alidaee and G. A. Kochenberger, (2003), "Modeling and solving the task allocation problem as an unconstrained quadratic binary program", Working Paper HCES-09-03, Hearin Center for Enterprise Science, University of Mississipi , December.

Lodi , A., K. Allemand and T. M. Liebling, (1999), "An evolutionary heuristic for quadratic 0-1 programming", Eur. J. Oper. Res. 119(3), pp 662-670, December.

Lu, S. H. and A. C. Williams, (1987), "Roof duality for polynomial 0-1 optimization", Math. Program. 37, pp 357-360.

Maaren, H. v. and J. P. Warners, (2000), "Bounds and fast approximation algorithms for binary quadratic optimization problems with application to MAX 2SAT", Discrete Appl. Math. 107(1-3), pp 225-239.

Marichal, J.-L., (2000), "The influence of variables on pseudo-Boolean functions with applications to game theory and multicriteria decision making", Discrete Appl. Math. 107(1-3), pp 139-164, December.

Merz, P. and B. Freisleben, (1999), "Genetic algorithms for binary quadratic programming", Proceedings of the 1999 international genetic and evolutionary computation conference (GECCO-1999), Morgan Kaufman Publishers, pp 417-424.

Merz, P. and B. Freisleben, (2002), "Greedy and local search heuristics for the unconstrained binary quadratic programming problem", Journal of Heuristics 8(2), pp 197-213.

Merz, P. and K. Katayama, (2004), "Memetic algorithms for the unconstrained binary quadratic programming problem", Bio Systems.

Merz, P., (2003), "The compact memetic algorithm", Presented at: (WOMA IV) in Fourth workshop on memetic algorithms, Chicago , United States of America .

Padberg, M. W., (1989), "The Boolean quadric polytope: Some characteristics, facets and relatives", Math. Program. 45, pp 139-172.

Palubeckis, G. and A. Tomkevičius, (2002), "GRASP implementations for the uncostrained binary quadratic optimization problem", Information Technology and Control 3, pp 14-20.

Palubeckis, G., (1990), "Quadratic 0-1 optimization", Informatica 1(1), pp 89-106.

Palubeckis, G., (1992), "Heuristics with a worst-case bound for unconstrained quadratic 0-1 programming", Informatica 3(2), pp 225-240.

Palubeckis, G., (1995), "A heuristic-based branch and bound algorithm for unconstrained quadratic zero-one programming", Computing 54, pp 283-301.

Palubeckis, G., (2004), "Multistart tabu search strategies for the unconstrained binary quadratic optimization problem", Ann. Oper. Res. 131, pp 259-282, October.

Pardalos, P. M. and G. P. Rodgers, (1990), "Computational aspects of a branch and bound algorithm for quadratic zero-one programming", Computing 45, pp 131-144.

Pardalos, P. M. and G. Schnitger, (1988), "Checking local optimality in constrained quadratic programming is NP-hard", Oper. Res. Lett. 7(1), pp 33-35, February.

Pardalos, P. M. and S. Jha , (1992), "Complexity of uniqueness and local search in quadratic 0-1 programming", Oper. Res. Lett. 11(2), pp 119-123, March.

Pardalos, P. M., (1987), "Generation of large-scale quadratic programs for use as global optimization test problems", ACM Transactions on Mathematical Software 13(2), pp 133-137, June.

Pardalos, P. M., (1991), "Construction of test problems in quadratic bivalent programming", ACM Transactions on Mathematical Software 17(1), pp 74-87, March.

Rosenberg, I. G., (1974), "Minimization of pseudo-Boolean functions by binary development", Discrete Math. 7, pp 151-165.

Sutter, A. and A. Billionnet, (1992), "Persistency in quadratic 0-1 optimization", Math. Program. 54, pp 115-119.

Williams, A. C., (1985), "Quadratic 0-1 programming using the roof dual with computational results", RUTCOR Research Report RRR 8-1985, RUTCOR - Rutgers Center for Operations Research, Rutgers University, December.

Zhang, H., H. Shen and F. Manyŕ, (2003), "Exact Algorithms for MAX-SAT", Electronic Notes in Theoretical Computer Science 86(1), pp 1-14, May.

 

Copyright © 2003 RUTCOR.
For problems or questions regarding the PBO website contact pbo@rutcor.rutgers.edu.
Last updated: February 13, 2005.