Free Access

Letter to the Editor—Reduction of Integer Polynomial Programming Problems to Zero-One Linear Programming Problems

Lawrence J. Watters
Lawrence J. Watters
The Rand Corporation, Santa Monica, California
Search for more papers by this author

Lawrence J. Watters

The Rand Corporation, Santa Monica, California

Search for more papers by this author

Published Online:1 Dec 1967https://doi.org/10.1287/opre.15.6.1171

Cited by
- Quantum optimisation for supply chain: QUBO formulations and QAOA solutions for facility location and load balancing
  Results in Engineering, Vol. 29
- Quadratization and convexification in polynomial binary optimization
  5 October 2025 | Journal of Combinatorial Optimization, Vol. 50, No. 3
- Synergy-Based Methodology for Portfolio Optimization in Strategic Planning Projects
- Balancing storage cost and customization time in product platform design: a bi-objective optimization model
  5 February 2025 | The International Journal of Advanced Manufacturing Technology, Vol. 136, No. 11-12
- Traceability Technology Adoption in Supply Chain Networks
  Philippe Blaettchen,
  Andre P. Calmon,
  Georgina Hall
  25 March 2024 | Management Science, Vol. 71, No. 1
- Modeling the Line Balancing Problem as a QUBO Model and Solving It by Quantum Annealing
  19 August 2025
- Combinatorial optimization methods for damage mitigation on National Ignition Facility final optics
- Revisiting some classical linearizations of the quadratic binary optimization problem and linkages with constraint aggregations
  Discrete Optimization, Vol. 54
- Dynamic, Reconfigurable and Green Network Slice Admission Control and Resource Allocation in the O-RAN Using Model Predictive Control
- Solving unconstrained binary polynomial programs with limited reach: Application to low autocorrelation binary sequences
  Computers & Operations Research, Vol. 165
- DiversiTree: A New Method to Efficiently Compute Diverse Sets of Near-Optimal Solutions to Mixed-Integer Optimization Problems
  Izuwa Ahanor,
  Hugh Medal,
  Andrew C. Trapp
  21 August 2023 | INFORMS Journal on Computing, Vol. 36, No. 1
- Converting Weak to Strong MIP Formulations: A Practitioner’s Guide
  29 December 2024
- Managing Mass Customization through Delayed Product Differentiation: a bi-objective model for product platforms design
  Procedia CIRP, Vol. 130
- Solving multiplicative programs by binary-encoding the multiplication operation
  Computers & Operations Research, Vol. 159
- Cooperative Beamforming for RIS-Aided Cell-Free Massive MIMO Networks
  IEEE Transactions on Wireless Communications, Vol. 22, No. 11
- Retail store layout optimization for maximum product visibility
  5 April 2022 | Journal of the Operational Research Society, Vol. 74, No. 4
- Portfolio selection of power generation projects considering the synergy of project and uncertainty of decision information
  Computers & Industrial Engineering, Vol. 175
- Discrete Dynamical System Approaches for Boolean Polynomial Optimization
  30 June 2022 | Journal of Scientific Computing, Vol. 92, No. 2
- Introduction to QUBO
  9 April 2022
- Mathematical Programming Models and Exact Algorithms
  9 April 2022
- Database parallelism, big data and analytics, deep learning
- Bibliography
- Computing representations using hypervolume scalarizations
  Computers & Operations Research, Vol. 137
- Inductive linearization for binary quadratic programs with linear constraints
  19 October 2020 | 4OR, Vol. 19, No. 4
- Product configuration using redundancy and standardisation in an uncertain environment
  22 September 2020 | International Journal of Production Research, Vol. 59, No. 21
- Mathematical models and approximate solution approaches for the stochastic bin packing problem
  Computers & Operations Research, Vol. 135
- Railway delay management with passenger rerouting considering train capacity constraints
  European Journal of Operational Research, Vol. 288, No. 2
- Traceability Technology Adoption in Supply Chain Networks
  SSRN Electronic Journal, Vol. 411
- An Efficient Dynamic Rule Placement for Distributed Firewall in SDN
- Optimal quadratic reformulations of fourth degree Pseudo-Boolean functions
  3 August 2019 | Optimization Letters, Vol. 14, No. 6
- Robust Quadratic Programming with Mixed-Integer Uncertainty
  Areesh Mittal,
  Can Gokalp,
  Grani A. Hanasusanto
  13 September 2019 | INFORMS Journal on Computing, Vol. 32, No. 2
- Structured linear reformulation of binary quadratically constrained quadratic programs
  17 November 2018 | Optimization Letters, Vol. 14, No. 3
- Solving multistatic sonar location problems with mixed-integer programming
  28 June 2019 | Optimization and Engineering, Vol. 21, No. 1
- An alternative efficient representation for the project portfolio selection problem
  European Journal of Operational Research, Vol. 281, No. 1
- Integer programming
- Incentive UAV-Enabled Mobile Edge Computing Based on Microwave Power Transmission
  IEEE Access, Vol. 8
- Accurate Long-Term Multiple People Tracking Using Video and Body-Worn IMUs
  IEEE Transactions on Image Processing, Vol. 29
- Integer Programming
  13 December 2019
- Optimal Countermeasures Selection Against Cyber Attacks: A Comprehensive Survey on Reaction Frameworks
  IEEE Communications Surveys & Tutorials, Vol. 20, No. 2
- A Genetic Algorithm for the Proactive Resource-Constrained Project Scheduling Problem With Activity Splitting
  IEEE Transactions on Engineering Management, Vol. 66, No. 3
- Simultaneous Identification and Tracking of Multiple People Using Video and IMUs
- Berge-acyclic multilinear 0–1 optimization problems
  European Journal of Operational Research, Vol. 273, No. 1
- A note on linearized reformulations for a class of bilevel linear integer problems
  15 November 2017 | Annals of Operations Research, Vol. 272, No. 1-2
- Compact linearization for binary quadratic problems subject to assignment constraints
  2 December 2017 | 4OR, Vol. 16, No. 3
- Improved formulations for minimum connectivity network interdiction problems
  Computers & Operations Research, Vol. 97
- A binarisation heuristic for non-convex quadratic programming with box constraints
  Operations Research Letters, Vol. 46, No. 5
- Novel and Necessary Structure of Overall On-Line Monitoring for Power System
- Norm bounds and underestimators for unconstrained polynomial integer minimization
  23 September 2017 | Mathematical Methods of Operations Research, Vol. 87, No. 1
- Fractional 0–1 programming: applications and algorithms
  19 December 2016 | Journal of Global Optimization, Vol. 69, No. 1
- A class of valid inequalities for multilinear 0–1 optimization problems
  Discrete Optimization, Vol. 25
- On linearization techniques for budget-constrained binary quadratic programming problems
  Operations Research Letters, Vol. 44, No. 6
- Approximation Algorithms for Optimization of Combinatorial Dynamical Systems
  IEEE Transactions on Automatic Control, Vol. 61, No. 9
- A simple technique to improve linearized reformulations of fractional (hyperbolic) 0–1 programming problems
  Operations Research Letters, Vol. 44, No. 4
- A modular product multi-platform configuration model
  24 July 2014 | International Journal of Computer Integrated Manufacturing, Vol. 28, No. 9
- Optimization of Pumping Energy and Maintenance Costs in Water Supply Systems
- Mixed Integer Linear Programming Formulation Techniques
  SIAM Review, Vol. 57, No. 1
- Ellipsoid Bounds for Convex Quadratic Integer Programming
  SIAM Journal on Optimization, Vol. 25, No. 2
- Reformulations of Mixed-Integer Programming Continuous-Time Models for Chemical Production Scheduling
  9 June 2014 | Industrial & Engineering Chemistry Research, Vol. 53, No. 24
- Combining Discrete Ellipsoid-Based Search and Branch-and-Cut for Binary Quadratic Programming Problems
- The Golf Director Problem: Forming Teams for Club Golf Competitions
  22 August 2014
- Practical guidelines for solving difficult mixed integer linear programs
  Surveys in Operations Research and Management Science, Vol. 18, No. 1-2
- Univariate parameterization for global optimization of mixed-integer polynomial problems
  European Journal of Operational Research, Vol. 229, No. 3
- Exploiting multiple access points diversity gain in the multi-access wireless network
- Several versions of the devour digest tidy-up heuristic for unconstrained binary quadratic problems
  8 June 2011 | Journal of Heuristics, Vol. 19, No. 4
- An improved framework for solving NLIPs with signomial terms in the objective or constraints to global optimality
  Computers & Chemical Engineering, Vol. 53
- Base-2 Expansions for Linearizing Products of Functions of Discrete Variables
  Warren P. Adams,
  Stephen M. Henry,
  20 November 2012 | Operations Research, Vol. 60, No. 6
- Two-stage quadratic integer programs with stochastic right-hand sides
  1 October 2010 | Mathematical Programming, Vol. 133, No. 1-2
- Scalable optimal countermeasure selection using implicit enumeration on attack countermeasure trees
- An exact solution method for unconstrained quadratic 0–1 programming: a geometric approach
  9 April 2011 | Journal of Global Optimization, Vol. 52, No. 4
- An improved linearization technique for a class of quadratic 0-1 programming problems
  16 October 2010 | Optimization Letters, Vol. 6, No. 1
- A continuous approach to combinatorial optimization: application of water system pump operations
  25 November 2010 | Optimization Letters, Vol. 6, No. 1
- Modeling disjunctive constraints with a logarithmic number of binary variables and constraints
  2 July 2009 | Mathematical Programming, Vol. 128, No. 1-2
- Integrated production planning with sequence-dependent family setup times
  International Journal of Production Economics, Vol. 131, No. 2
- Graph-Based Decoding in the Presence of ISI
  IEEE Transactions on Information Theory, Vol. 57, No. 4
- An efficient linearization technique for mixed 0–1 polynomial problem
  Journal of Computational and Applied Mathematics, Vol. 235, No. 6
- A mixed-integer linear program for optimizing sensor locations along freeway corridors
  Transportation Research Part B: Methodological, Vol. 45, No. 1
- Comparing heuristic algorithms of the planar storage location assignment problem
  Transportation Research Part E: Logistics and Transportation Review, Vol. 46, No. 1
- References
  13 September 2011
- Mathematical modeling and solving procedure of the planar storage location assignment problem
  Computers & Industrial Engineering, Vol. 57, No. 3
- Assembly block storage location assignment problem: revisited
  23 April 2009 | Production Planning & Control, Vol. 20, No. 3
- Improved compact linearizations for the unconstrained quadratic 0–1 minimization problem
  Discrete Applied Mathematics, Vol. 157, No. 6
- A linearization framework for unconstrained quadratic (0-1) problems
  Discrete Applied Mathematics, Vol. 157, No. 6
- On the Quadratic Programming Approach for Hub Location Problems
  25 May 2009
- A new Implicit Enumeration Method for Linear 0-1 Programming
- Cross-Layer Fair Bandwidth Sharing for Multi-Channel Wireless Mesh Networks
  IEEE Transactions on Wireless Communications, Vol. 7, No. 9
- Multi-Quadratic Integer Programming: Models and Applications
- Modeling Disjunctive Constraints with a Logarithmic Number of Binary Variables and Constraints
- Efficient Reduction of Polynomial Zero-One Optimization to the Quadratic Case
  SIAM Journal on Optimization, Vol. 18, No. 4
- Simple Modelling Techniques II
  10 November 2009
- A revised Taha's algorithm for polynomial 0-1 programming
  Optimization, Vol. 56, No. 5-6
- Computing exact solution to nonlinear integer programming: Convergent Lagrangian and objective level cut method
  16 January 2007 | Journal of Global Optimization, Vol. 39, No. 1
- Linear forms of nonlinear expressions: New insights on old ideas
  Operations Research Letters, Vol. 35, No. 4
- Optimum utilization of renewable energy sources in a remote area
  Renewable and Sustainable Energy Reviews, Vol. 11, No. 5
- Equalization on Graphs: Linear Programming and Message Passing
- New Implicit Enumeration Method for Polynomial 0-1 Programming
  Systems Engineering - Theory & Practice, Vol. 27, No. 3
- Joint Channel Allocation, Interface Assignment and MAC Design for Multi-Channel Wireless Mesh Networks
- Integrated design of workcells and unidirectional flowpath layout
  Computers & Industrial Engineering, Vol. 51, No. 1
- Polyhedra related to integer-convex polynomial systems
  12 October 2005 | Mathematical Programming, Vol. 105, No. 2-3
- A Generalized Fuzzy Optimization Framework for R&D Project Selection Using Real Options Valuation
- Decision-Aiding Methodology for the School Bus Routing and Scheduling Problem
  M. Spada,
  M. Bierlaire,
  Th. M. Liebling,
  1 November 2005 | Transportation Science, Vol. 39, No. 4
- A Hierarchy of Relaxations Leading to the Convex Hull Representation for General Discrete Optimization Problems
  Annals of Operations Research, Vol. 140, No. 1
- An enhanced formulation and simple heuristic for scheduling jobs on unrelated parallel machines
  Journal of Information and Optimization Sciences, Vol. 26, No. 1
- A new linearization technique for multi-quadratic 0–1 programming problems
  Operations Research Letters, Vol. 32, No. 6
- A linearized polynomial mixed integer programming model for the integration of process planning and scheduling
  Journal of Intelligent Manufacturing, Vol. 15, No. 5
- Short-term Scheduling of Non-sequential Multipurpose Batch Processes with Transfer and Set-up Times Under Various Intermediate Storage Policies
  Chemical Engineering Research and Design, Vol. 82, No. 10
- A genetic-based algorithm with the optimal partition approach for the cell formation in bi-directional linear flow layout
  19 February 2007 | International Journal of Computer Integrated Manufacturing, Vol. 17, No. 4
- Impact of personnel allocation on deterministic planning and scheduling
  21 April 2004 | AIChE Journal, Vol. 50, No. 5
- Unrelated parallel machine scheduling with job splitting
  IIE Transactions, Vol. 36, No. 4
- Design of manufacturing cells in the presence of alternative cell locations and material transporters
  21 December 2017 | Journal of the Operational Research Society, Vol. 54, No. 10
- Pseudo-Boolean optimization
  Discrete Applied Mathematics, Vol. 123, No. 1-3
- General continuous time models for production planning and scheduling of batch processing plants: mixed integer linear program formulations and computational issues
  Computers & Chemical Engineering, Vol. 25, No. 2-3
- pth Power Lagrangian Method for Integer Programming
  Annals of Operations Research, Vol. 98, No. 1-4
- A linearization method for mixed 0–1 polynomial programs
  Computers & Operations Research, Vol. 27, No. 10
- An efficient linearization approach for mixed-integer problems
  European Journal of Operational Research, Vol. 123, No. 3
- Management of Multi-Item Retail Inventory Systems with Demand Substitution
  Stephen A. Smith,
  Narendra Agrawal,
  1 February 2000 | Operations Research, Vol. 48, No. 1
- Reducing the integrality gap with a modified re-formulation linearization approach
  Computers & Chemical Engineering, Vol. 23
- The Theory of Discrete Lagrange Multipliers for Nonlinear Discrete Optimization
- A hybrid approach to resolving a differentiable integer program
  Computers & Operations Research, Vol. 25, No. 6
- Optimizing a library's loan policy: An integer programming approach
  Journal of the American Society for Information Science, Vol. 49, No. 13
- Optimizing a Retail Promotional Calendar by Mixed Integer, Linear Programming
- Locating sets of identical machines in a linear layout
  Annals of Operations Research, Vol. 77, No. 0
- Simultaneous route selection and cell formation: a mixed‐integer programming time‐cost model
  Integrated Manufacturing Systems, Vol. 8, No. 6
- A spine layout design method for semiconductor fabrication facilities containing automated material‐handling systems
  International Journal of Operations & Production Management, Vol. 17, No. 5
- A 0–1 quadratic knapsack problem for modelizing and solving the constraint satisfaction problems
  10 June 2005
- A dynamic reconfiguring tool for improving multiwavelength transport network robustness
- Scheduling of batch processes with operational uncertainties
  Computers & Chemical Engineering, Vol. 20
- A multiple criteria decision model for information system project selection
  Computers & Operations Research, Vol. 22, No. 8
- Rule allocation in distributed deductive database systems
  Data & Knowledge Engineering, Vol. 14, No. 2
- A branch and bound algorithm for solving separable convex integer programming problems
  Computers & Operations Research, Vol. 21, No. 9
- Cell formation: the need for an integrated solution of the subproblems
  International Journal of Production Research, Vol. 32, No. 5
- Configuration of manufacturing software through capability specification and selection
  Applied Mathematical Modelling, Vol. 18, No. 3
- REFORMULATING QUADRATIC ASSIGNMENT PROBLEMS FOR EFFICIENT OPTIMIZATION
  IIE Transactions, Vol. 25, No. 6
- Problem‐oriented modules for process simulation. resolution strategies for simulation and optimization
  27 March 2009 | The Canadian Journal of Chemical Engineering, Vol. 71, No. 4
- Mixed-integer bilinear programming problems
  Mathematical Programming, Vol. 59, No. 1-3
- 8 Integer programming
- A knowledge representation for constraint satisfaction problems
  IEEE Transactions on Knowledge and Data Engineering, Vol. 5, No. 5
- Reformulating nonlinear combinatorial optimization problems for higher computational efficiency
  European Journal of Operational Research, Vol. 58, No. 2
- On the assignment problem of arbitrary process systems to heterogeneous distributed computer systems
  IEEE Transactions on Computers, Vol. 41, No. 3
- A planning aid: an intelligent modeling system for planning problems based on constraint satisfaction
  IEEE Transactions on Knowledge and Data Engineering, Vol. 4, No. 4
- Computer communication modeling for a multisite distributed application design methodology
- MINLP model for cyclic multiproduct scheduling on continuous parallel lines
  Computers & Chemical Engineering, Vol. 15, No. 2
- An algorithm for indefinite integer quadratic programming
  Computers & Mathematics with Applications, Vol. 21, No. 6-7
- A Hybrid Algorithm for Solving Polynomial Zero-One Mathematical Programming Problems
  IIE Transactions, Vol. 22, No. 2
- Guide path design and location of load pick-up/drop-off points for an automated guided vehicle system
  30 March 2007 | International Journal of Production Research, Vol. 28, No. 5
- The allocation problem in parallel production systems
  Journal of Parallel and Distributed Computing, Vol. 8, No. 1
- An effective approach to vertical partitioning for physical design of relational databases
  IEEE Transactions on Software Engineering, Vol. 16, No. 2
- A continuous approach to nonlinear integer programming
  Applied Mathematics and Computation, Vol. 34, No. 1
- Performance comparison of IO shipping and database call shipping: Schemes in multisystem partitioned databases
  Performance Evaluation, Vol. 10, No. 1
- Choice of a Subset with Respect to Many Criteria
- On optimal site assignment for relations in the distributed database environment
  IEEE Transactions on Software Engineering, Vol. 15, No. 8
- Models and methods of solution of quadratic integer programming problems
  Cybernetics, Vol. 23, No. 3
- Optimal resolution sequence of problems modeled by directed graphs
  Mathematical and Computer Modelling, Vol. 10, No. 7
- Reduction of nonlinear integer separable programming problems ∗
  International Journal of Computer Mathematics, Vol. 24, No. 1
- Site assignment for relations and joint operations in the distributed transaction processing environment
- A new formulation of operation allocation problem in flexible manufacturing systems: mathematical modelling and computational experience
  22 October 2007 | International Journal of Production Research, Vol. 25, No. 9
- Optimizing the Structure of Distributed Process Control Systems
  IFAC Proceedings Volumes, Vol. 20, No. 5
- Analysis of affinity based routing in multi-system data sharing
  Performance Evaluation, Vol. 7, No. 2
- Flow path design for automated guided vehicle systems
  12 March 2007 | International Journal of Production Research, Vol. 25, No. 5
- A branch and bound algorithm for solving a class of nonlinear integer programming problems
  21 November 2006 | Naval Research Logistics Quarterly, Vol. 33, No. 4
- Task allocation in distributed processing systems
  Operations Research Letters, Vol. 5, No. 3
- The design of branch and bound algorithms for a class of nonlinear integer programs
  Annals of Operations Research, Vol. 5, No. 2
- The design of branch and bound algorithms for a class of nonlinear integer programs
  Annals of Operations Research, Vol. 5, No. 1-4
- An efficient approximate algorithm for solving system reliability optimization problems
  22 March 2007 | Electrical Engineering in Japan, Vol. 106, No. 5
- Computer Aided Design of Organization of Industrial Quality Inspection
- A loading and dispatching problem in a random flexible manufacturing system
  22 October 2007 | International Journal of Production Research, Vol. 23, No. 3
- Nonlinear 0–1 programming: I. Linearization techniques
  Mathematical Programming, Vol. 30, No. 1
- A dynamic production planning and scheduling algorithm for two products processed on one line
  European Journal of Operational Research, Vol. 17, No. 3
- A Portfolio Theoretic Approach to Multiplant Location Analysis
  3 September 2010 | Geographical Analysis, Vol. 16, No. 2
- On the problem of optimization of a quality inspection process structure
  27 April 2007 | International Journal of Production Research, Vol. 21, No. 3
- Mixed-integer quadratic programming
  Mathematical Programming, Vol. 22, No. 1
- Fault Diagnosis by Mathematical Programming
  IEEE Transactions on Reliability, Vol. R-30, No. 4
- Algebraic formulation of circuit design problems
  Cybernetics, Vol. 17, No. 2
- Mean-variance analysis for indivisible assets
  Omega, Vol. 9, No. 1
- Optimization of Staggered Inspection Schedules for Protective Systems
  IEEE Transactions on Reliability, Vol. R-29, No. 2
- Optimization Problems on System Supervision
- An algorithm (GIPC2) for solving integer programming problems with separable nonlinear objective functions
  29 October 2013 | Naval Research Logistics Quarterly, Vol. 26, No. 4
- Improvement of Supervision Schedules for Protective Systems
  IEEE Transactions on Reliability, Vol. R-28, No. 2
- Methods of Nonlinear 0-1 Programming
- UNCONSTRAINED DISCRETE NONLINEAR PROGRAMMING
  Engineering Optimization, Vol. 4, No. 2
- Using pseudoboolean programming in decomposition method
- MODELING COMBINATORIAL MATHEMATICAL PROGRAMMING PROBLEMS BY NETFORMS: AN ILLUSTRATIVE APPLICATION
- Scheduling Multispecialty Clinics Using Integer Programming
  A I I E Transactions, Vol. 9, No. 1
- Integer programming formulation of combinatorial optimization problems
  Discrete Mathematics, Vol. 16, No. 1
- An Algorithm for r ‐Bases of a Directed Graph
  2 March 2007 | Networks, Vol. 6, No. 2
- Modeling the product elimination decision
  Omega, Vol. 4, No. 6
- Zur linearisierung beliebiger 0-1-optimierungsprobleme
  27 June 2007 | Mathematische Operationsforschung und Statistik, Vol. 7, No. 2
- Solution of Capital Budgeting Problems Having Chance Constraints; Heuristic and Exact Methods
  A I I E Transactions, Vol. 7, No. 2
- Optimal control of pulse‐manipulated systems
  19 April 2007 | Electrical Engineering in Japan, Vol. 95, No. 4
- References††The first comprehensive references list is due to Balinski and Spielberg (1969). A later list appears in the work of Garfinkel and Nemhauser (1972b).
- The chromatic reduction problem
  11 October 2006 | Networks, Vol. 3, No. 4
- An improved algorithm for pseudo-boolean programming
  24 May 2005
- Sequencing by Implicit Ranking and Zero-One Polynomial Programming
  9 July 2007 | A I I E Transactions, Vol. 3, No. 4
- Ganzzahlige Programmierung — Ein Überblick
- Optimal File Allocation in a Multiple Computer System
  IEEE Transactions on Computers, Vol. C-18, No. 10

Volume 15, Issue 6

November-December 1967

Pages 985-1188

Article Information

Metrics

Information

Published Online:December 01, 1967

Cite as

Lawrence J. Watters, (1967) Letter to the Editor—Reduction of Integer Polynomial Programming Problems to Zero-One Linear Programming Problems. Operations Research 15(6):1171-1174.

https://doi.org/10.1287/opre.15.6.1171

PDF download

Available Issues

Available Issues

Available Issues

Available Issues

Available Issues

Available Issues

Available Issues

Available Issues

Available Issues

Letter to the Editor—Reduction of Integer Polynomial Programming Problems to Zero-One Linear Programming Problems

Volume 15, Issue 6

Article Information

Metrics

Information

Cite as

Sign Up for INFORMS Publications Updates and News