Some Network Flow Problems Solved with Pseudo-Boolean Programming

Peter L. Ivănescu
Peter L. Ivănescu
Institute of Mathematics, Romanian Academy, Bucharest, Romania
Search for more papers by this author

Institute of Mathematics, Romanian Academy, Bucharest, Romania

Published Online:1 Jun 1965https://doi.org/10.1287/opre.13.3.388

Abstract

The aim of this paper is to apply the method of pseudo-Boolean programming to the determination of the minimal cut and of the value of the maximal flow through a network without, or with, given lower bounds on the arc flows, as well as to the solution of some feasibility problems in networks.

Cited by
- Multi-view Ensemble Feature Selection via SemiDefinite Programming
  European Journal of Operational Research, Vol. 328, No. 1
- Quantum Subroutines in Branch-Price-and-Cut for Vehicle Routing
  IEEE Transactions on Quantum Engineering, Vol. 7
- Enhancing Quantum Algorithms for Quadratic Unconstrained Binary Optimization via Integer Programming
  13 February 2025 | ACM Transactions on Quantum Computing, Vol. 6, No. 2
- Joint Cutting for Hybrid Schrödinger-Feynman Simulation of Quantum Circuits
- Optimized Noise Suppression for Quantum Circuits
  Friedrich Wagner; ,
  Daniel J. Egger,
  Frauke Liers;
  29 October 2024 | INFORMS Journal on Computing, Vol. 37, No. 1
- The rotation distance of brooms
  European Journal of Combinatorics, Vol. 118
- A Family of Spanning-Tree Formulations for the Maximum Cut Problem
  22 May 2024
- Inductive linearization for binary quadratic programs with linear constraints
  19 October 2020 | 4OR, Vol. 19, No. 4
- Linear size MIP formulation of Max-Cut: new properties, links with cycle inequalities and computational results
  20 November 2020 | Optimization Letters, Vol. 15, No. 4
- Tight Cycle Relaxations for the Cut Polytope
  2 December 2021 | SIAM Journal on Discrete Mathematics, Vol. 35, No. 4
- A Lower Bound on DNNF Encodings of Pseudo-Boolean Constraints
  26 June 2020
- Projection Recurrent Neural Network Model: A New Strategy to Solve Weapon-Target Assignment Problem
  22 June 2019 | Neural Processing Letters, Vol. 50, No. 3
- Multi-task Recurrent Neural Networks and Higher-order Markov Random Fields for Stock Price Movement Prediction
  25 July 2019
- On a general framework for network representability in discrete optimization
  20 May 2017 | Journal of Combinatorial Optimization, Vol. 36, No. 3
- A binarisation heuristic for non-convex quadratic programming with box constraints
  Operations Research Letters, Vol. 46, No. 5
- What Works Best When? A Systematic Evaluation of Heuristics for Max-Cut and QUBO
  Iain Dunning,
  Swati Gupta,
  John Silberholz
  15 October 2018 | INFORMS Journal on Computing, Vol. 30, No. 3
- Strong formulations for quadratic optimization with M-matrices and indicator variables
  25 May 2018 | Mathematical Programming, Vol. 170, No. 1
- A Lagrangian decomposition approach to computing feasible solutions for quadratic binary programs
  8 March 2017 | Optimization Letters, Vol. 12, No. 1
- A New Method for Stock Price Prediction Based on MRFs and SSVM
- Directed Acyclic Graph Continuous Max-Flow Image Segmentation for Unconstrained Label Orderings
  17 February 2017 | International Journal of Computer Vision, Vol. 123, No. 3
- Efficient minimization of higher order submodular functions using monotonic Boolean functions
  Discrete Applied Mathematics, Vol. 220
- Empirical Minimum Bayes Risk Prediction
  IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 39, No. 1
- Dynamic Parallel and Distributed Graph Cuts
  IEEE Transactions on Image Processing, Vol. 25, No. 12
- Data-Dependent Higher-Order Clique Selection for Artery–Vein Segmentation by Energy Minimization
  14 September 2015 | International Journal of Computer Vision, Vol. 117, No. 2
- On a General Framework for Network Representability in Discrete Optimization
  10 September 2016
- Complexity of Discrete Energy Minimization Problems
  17 September 2016
- Crossing Minimization in Storyline Visualization
  8 December 2016
- The bipartite unconstrained 0–1 quadratic programming problem: Polynomially solvable cases
  Discrete Applied Mathematics, Vol. 193
- An optimized link scheduling technique for mobile ad hoc networks using directional antennas
- Learning Weighted Lower Linear Envelope Potentials in Binary Markov Random Fields
  IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 37, No. 7
- A Hypergraph-Based Reduction for Higher-Order Binary Markov Random Fields
  IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 37, No. 7
- Object Segmentation and Markov Random Fields
- SOME EXPERIENCES WITH SOLVING SEMIDEFINITE PROGRAMMING RELAXATIONS OF BINARY QUADRATIC OPTIMIZATION MODELS IN COMPUTATIONAL BIOLOGY
  20 August 2014 | Asia-Pacific Journal of Operational Research, Vol. 31, No. 04
- General Bibliography
  8 August 2014
- Quadratic Optimization in 0–1 Variables
  8 August 2014
- Empirical Minimum Bayes Risk Prediction: How to Extract an Extra Few % Performance from Vision Models with Just Three More Parameters
- A Polynomial Algorithm for a Class of 0–1 Fractional Programming Problems Involving Composite Functions, with an Application to Additive Clustering
  3 May 2014
- Occlusion and Motion Reasoning for Long-Term Tracking
- Towards Efficient and Exact MAP-Inference for Large Scale Discrete Computer Vision Problems via Combinatorial Optimization
- A computational study and survey of methods for the single-row facility layout problem
  6 September 2012 | Computational Optimization and Applications, Vol. 55, No. 1
- Quadratic Optimization in 0–1 Variables
  21 January 2013
- Multilabel partition moves for MRF optimization
  Image and Vision Computing, Vol. 31, No. 1
- VirCA NET and CogInfoCom: Novel challenges in future internet based augmented/Virtual Collaboration
- Canonical dual approach to solving the maximum cut problem
  16 March 2012 | Journal of Global Optimization, Vol. 54, No. 2
- Algebraic method to pseudo-Boolean function and its application in pseudo-Boolean optimization
- A Coding-Cost Framework for Super-Resolution Motion Layer Decomposition
  IEEE Transactions on Image Processing, Vol. 21, No. 3
- Recent Progress in Interior-Point Methods: Cutting-Plane Algorithms and Warm Starts
  26 September 2011
- Computational Approaches to Max-Cut
  26 September 2011
- Global Approaches for Facility Layout and VLSI Floorplanning
  26 September 2011
- Introduction
  27 August 2012
- Maximization of Submodular Functions: Theory and Algorithms
  27 August 2012
- Data Correcting Approach for the Maximization of Submodular Functions
  27 August 2012
- Data Correcting Approach for the Simple Plant Location Problem
  27 August 2012
- Summary
  27 August 2012
- Fast Fusion Moves for Multi-model Estimation
- Approximate MRF Inference Using Bounded Treewidth Subgraphs
- Contraction Moves for Geometric Model Fitting
- Expressibility of Submodular Languages
- 0-1 Quadratic Knapsack Problems: An Exact Approach Based on a $t$-Linearization
  SIAM Journal on Optimization, Vol. 22, No. 4
- OPTIMAL ALLOCATION PROBLEM WITH QUADRATIC UTILITY FUNCTIONS AND ITS RELATIONSHIP WITH GRAPH CUT PROBLEM
  Journal of the Operations Research Society of Japan, Vol. 55, No. 1
- Optimal Allocation in Combinatorial Auctions with Quadratic Utility Functions
- Fusion Moves for Markov Random Field Optimization
  IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 32, No. 8
- Speeding up IP-based algorithms for constrained quadratic 0–1 optimization
  8 May 2010 | Mathematical Programming, Vol. 124, No. 1-2
- Classes of submodular constraints expressible by graph cuts
  24 September 2009 | Constraints, Vol. 15, No. 3
- Beyond trees: MRF inference via outer-planar decomposition
- Globally optimal pixel labeling algorithms for tree metrics
- OBJCUT: Efficient Segmentation Using Top-Down and Bottom-Up Cues
  IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 32, No. 3
- Semidefinite Relaxations for Integer Programming
  6 November 2009
- The expressive power of binary submodular functions
  Discrete Applied Mathematics, Vol. 157, No. 15
- The Expressive Power of Binary Submodular Functions
- Constrained 0–1 quadratic programming: Basic approaches and extensions
  European Journal of Operational Research, Vol. 187, No. 3
- Exact inference in multi-label CRFs with higher order cliques
- A Comparative Study of Energy Minimization Methods for Markov Random Fields with Smoothness-Based Priors
  IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 30, No. 6
- Generating facets for the cut polytope of a graph by triangular elimination
  2 August 2006 | Mathematical Programming, Vol. 112, No. 2
- Minimizing Nonsubmodular Functions with Graph Cuts-A Review
  IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 29, No. 7
- A Linear Programming Approach to Max-Sum Problem: A Review
  IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 29, No. 7
- A Memetic Algorithm with Genetic Particle Swarm Optimization and Neural Network for Maximum Cut Problems
- Two-party Bell inequalities derived from combinatorics via triangular elimination
  30 November 2005 | Journal of Physics A: Mathematical and General, Vol. 38, No. 50
- Solving the fixed rank convex quadratic maximization in binary variables by a parallel zonotope construction algorithm
  European Journal of Operational Research, Vol. 166, No. 1
- Maximum Neural Network with Nonlinear Self-Feedback and Its Application to Maximum Independent Set Problem
  IEEJ Transactions on Electronics, Information and Systems, Vol. 125, No. 2
- Memetic algorithms for the unconstrained binary quadratic programming problem
  Biosystems, Vol. 78, No. 1-3
- Modelling competitive Hopfield networks for the maximum clique problem
  Computers & Operations Research, Vol. 30, No. 4
- Efficiently solving general weapon-target assignment problem by genetic algorithms with greedy eugenics
  IEEE Transactions on Systems, Man and Cybernetics, Part B (Cybernetics), Vol. 33, No. 1
- Pseudo-Boolean optimization
  Discrete Applied Mathematics, Vol. 123, No. 1-3
- An immunity-based ant colony optimization algorithm for solving weapon–target assignment problem
  Applied Soft Computing, Vol. 2, No. 1
- A genetic algorithm with domain knowledge for weapon‐target assignment problems
  3 March 2011 | Journal of the Chinese Institute of Engineers, Vol. 25, No. 3
- Greedy and Local Search Heuristics for Unconstrained Binary Quadratic Programming
  Journal of Heuristics, Vol. 8, No. 2
- Performance of simulated annealing-based heuristic for the unconstrained binary quadratic programming problem
  European Journal of Operational Research, Vol. 134, No. 1
- A comparison between simulated annealing, genetic algorithm and tabu search methods for the unconstrained quadratic Pseudo-Boolean function
  Computers & Industrial Engineering, Vol. 38, No. 3
- Fixing Variables in Semidefinite Relaxations
  SIAM Journal on Matrix Analysis and Applications, Vol. 21, No. 3
- An evolutionary heuristic for quadratic 0–1 programming
  European Journal of Operational Research, Vol. 119, No. 3
- Solving quadratic (0,1)-problems by semidefinite programs and cutting planes
  Mathematical Programming, Vol. 82, No. 3
- Simulated annealing for the unconstrained quadratic pseudo-Boolean function
  European Journal of Operational Research, Vol. 108, No. 3
- Optimum multiuser detection is tractable for synchronous CDMA systems using m-sequences
  IEEE Communications Letters, Vol. 2, No. 4
- Connections between semidefinite relaxations of the max-cut and stable set problems
  Mathematical Programming, Vol. 77, No. 1
- Global optimization for track finding
  Nuclear Instruments and Methods in Physics Research Section A: Accelerators, Spectrometers, Detectors and Associated Equipment, Vol. 389, No. 1-2
- A heuristic-based branch and bound algorithm for unconstrained quadratic zero-one programming
  Computing, Vol. 54, No. 4
- Some thoughts on combinatorial optimisation
  European Journal of Operational Research, Vol. 83, No. 2
- Exact determination of all ground states of random field systems in polynomial time
  Physica A: Statistical Mechanics and its Applications, Vol. 214, No. 2
- Applications of cut polyhedra — I
  Journal of Computational and Applied Mathematics, Vol. 55, No. 2
- A parallel computation network for the maximum clique problem
- A parallel computation network for the maximum clique problem
- Facets for the cut cone I
  Mathematical Programming, Vol. 56, No. 1-3
- Appendix C: Selected Readings
  24 October 2011
- Chvátal Cuts and Odd Cycle Inequalities in Quadratic 0–1 Optimization
  SIAM Journal on Discrete Mathematics, Vol. 5, No. 2
- The max-cut problem and quadratic 0–1 optimization; polyhedral aspects, relaxations and bounds
  Annals of Operations Research, Vol. 33, No. 3
- A parallel neural network computing for the maximum clique problem
- An algorithm for quadratic zero-one programs
  Naval Research Logistics, Vol. 37, No. 4
- The cut polytope and the Boolean quadric polytope
  Discrete Mathematics, Vol. 79, No. 1
- The boolean quadric polytope: Some characteristics, facets and relatives
  Mathematical Programming, Vol. 45, No. 1-3
- Experiments in quadratic 0–1 programming
  Mathematical Programming, Vol. 44, No. 1-3
- Best network flow bounds for the quadratic knapsack problem
  28 September 2006
- Problème de la bipartition minimale d'un graphe
  29 March 2011 | RAIRO - Operations Research, Vol. 21, No. 4
- Methods for Global Concave Minimization: A Bibliographic Survey
  SIAM Review, Vol. 28, No. 3
- A solvable case of quadratic 0–1 programming
  Discrete Applied Mathematics, Vol. 13, No. 1
- K best solutions to combinatorial optimization problems
  Annals of Operations Research, Vol. 4, No. 1
- On finding the K best cuts in a network
  Operations Research Letters, Vol. 2, No. 6
- Ranking the Cuts and Cut-Sets of a Network
- Activity selection games and the minimum‐cut problem
  11 October 2006 | Networks, Vol. 13, No. 1
- Determining minimal cuts with a minimal number of arcs
  11 October 2006 | Networks, Vol. 12, No. 4
- Selected Applications of Minimum Cuts in Networks
  25 May 2016 | INFOR: Information Systems and Operational Research, Vol. 20, No. 4
- A network flow solution to some nonlinear 0‐1 programming problems, with applications to graph theory
  11 October 2006 | Networks, Vol. 12, No. 2
- Methods of Nonlinear 0-1 Programming
- Minimum cuts and related problems
  11 October 2006 | Networks, Vol. 5, No. 4
- Minimization of pseudo-Boolean functions
  18 September 2006

Volume 13, Issue 3

May-June 1965

Pages 343-514

Article Information

Metrics

Information

Published Online:June 01, 1965

Cite as

Peter L. Ivănescu, (1965) Some Network Flow Problems Solved with Pseudo-Boolean Programming. Operations Research 13(3):388-399.

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

PDF download

Available Issues

Available Issues

Available Issues

Available Issues

Available Issues

Available Issues

Available Issues

Available Issues

Available Issues

Some Network Flow Problems Solved with Pseudo-Boolean Programming

Abstract

Volume 13, Issue 3

Article Information

Metrics

Information

Cite as

Sign Up for INFORMS Publications Updates and News