WEBINAR / EVENT
Graph-Based Approaches to Solving Binary Quadratic Programs
August 9-10, 2023
WEBINAR / EVENT
Graph-Based Approaches to Solving Binary Quadratic Programs
August 9-10, 2023
WEBINAR / EVENT
Graph-Based Approaches to Solving Binary Quadratic Programs
August 9-10, 2023
Event Recap
Binary quadratic and quadratically constrained programs (BQPs and BQCPs) have some unique characteristics among integer programs that have motivated various specialized strategies to solve them more efficiently. While they can be reformulated as binary integer programs (BIPs) or unconstrained binary quadratic programs (QUBOS), examination of the original binary quadratic formulation before any such transformations can help improve performance. Graphs can often facilitate this process. The product graph from Padberg’s Boolean Quadric Polytope paper in 1989 is probably the most well-known example. Padberg’s work focused on deriving cuts from the product graph and just the quadratic objective of the BQP.
In this webinar, we will consider incorporating constraints in the BQP or BQCP to derive cuts. We will then consider some other graph based approaches, and illustrate with some examples on some challenging publicly available problems.
View the presentation slides here.
Event Recap
Binary quadratic and quadratically constrained programs (BQPs and BQCPs) have some unique characteristics among integer programs that have motivated various specialized strategies to solve them more efficiently. While they can be reformulated as binary integer programs (BIPs) or unconstrained binary quadratic programs (QUBOS), examination of the original binary quadratic formulation before any such transformations can help improve performance. Graphs can often facilitate this process. The product graph from Padberg’s Boolean Quadric Polytope paper in 1989 is probably the most well-known example. Padberg’s work focused on deriving cuts from the product graph and just the quadratic objective of the BQP.
In this webinar, we will consider incorporating constraints in the BQP or BQCP to derive cuts. We will then consider some other graph based approaches, and illustrate with some examples on some challenging publicly available problems.
View the presentation slides here.
Event Recap
Binary quadratic and quadratically constrained programs (BQPs and BQCPs) have some unique characteristics among integer programs that have motivated various specialized strategies to solve them more efficiently. While they can be reformulated as binary integer programs (BIPs) or unconstrained binary quadratic programs (QUBOS), examination of the original binary quadratic formulation before any such transformations can help improve performance. Graphs can often facilitate this process. The product graph from Padberg’s Boolean Quadric Polytope paper in 1989 is probably the most well-known example. Padberg’s work focused on deriving cuts from the product graph and just the quadratic objective of the BQP.
In this webinar, we will consider incorporating constraints in the BQP or BQCP to derive cuts. We will then consider some other graph based approaches, and illustrate with some examples on some challenging publicly available problems.
View the presentation slides here.
Speakers
Meet Your Expert Speaker
Learn from the best in the industry, bringing years of experience and groundbreaking insights to the forefront of AI personalization.
Ed Klotz
Senior Mathematical Optimization Specialist
Dr. Ed Klotz has over 30 years of experience in the mathematical optimization software industry. He is a technical expert who, over the course of his career, has worked with a wide array of customers to help them solve some of world’s most challenging mathematical optimization problems. In his role as a Senior Mathematical Optimization Specialist on the Gurobi R&D team, Dr. Klotz works closely with our customers to support them in implementing and utilizing mathematical optimization in their organizations. He also interacts heavily with the R&D team based on his experiences with the customers.
Prior to joining Gurobi, Dr. Klotz was a member of the CPLEX development team of IBM. He was involved in product development, customer training, product documentation, and numerous other tasks, with a primary focus on delivering CPLEX customer support and leveraging his experiences with customers to help inform the R&D team about customer needs and product improvements. Dr. Klotz has extensive knowledge in linear programming, integer programming, and numerical linear algebra for finite precision computing. Using this knowledge, he was able to investigate customer support issues at the source code level and identify potential improvements in CPLEX, both in terms of performance and accuracy of computation.
Before joining IBM, Dr. Klotz was a principal technical support engineer at ILOG, Inc., and a mathematical programming specialist at CPLEX Optimization, Inc.
Dr. Klotz has presented at numerous conferences, workshops, and web seminars and published numerous papers on mathematical optimization. His interests are in all aspects of mathematical programming, with a primary interest in research that can impact mathematical programming software. He obtained a BA in Math and Economics from Oberlin College and a PhD in Operations Research from Stanford University.
Speakers
Meet Your Expert Speaker
Learn from the best in the industry, bringing years of experience and groundbreaking insights to the forefront of AI personalization.
Ed Klotz
Senior Mathematical Optimization Specialist
Dr. Ed Klotz has over 30 years of experience in the mathematical optimization software industry. He is a technical expert who, over the course of his career, has worked with a wide array of customers to help them solve some of world’s most challenging mathematical optimization problems. In his role as a Senior Mathematical Optimization Specialist on the Gurobi R&D team, Dr. Klotz works closely with our customers to support them in implementing and utilizing mathematical optimization in their organizations. He also interacts heavily with the R&D team based on his experiences with the customers.
Prior to joining Gurobi, Dr. Klotz was a member of the CPLEX development team of IBM. He was involved in product development, customer training, product documentation, and numerous other tasks, with a primary focus on delivering CPLEX customer support and leveraging his experiences with customers to help inform the R&D team about customer needs and product improvements. Dr. Klotz has extensive knowledge in linear programming, integer programming, and numerical linear algebra for finite precision computing. Using this knowledge, he was able to investigate customer support issues at the source code level and identify potential improvements in CPLEX, both in terms of performance and accuracy of computation.
Before joining IBM, Dr. Klotz was a principal technical support engineer at ILOG, Inc., and a mathematical programming specialist at CPLEX Optimization, Inc.
Dr. Klotz has presented at numerous conferences, workshops, and web seminars and published numerous papers on mathematical optimization. His interests are in all aspects of mathematical programming, with a primary interest in research that can impact mathematical programming software. He obtained a BA in Math and Economics from Oberlin College and a PhD in Operations Research from Stanford University.
Speakers
Meet Your Expert Speaker
Learn from the best in the industry, bringing years of experience and groundbreaking insights to the forefront of AI personalization.
Senior Mathematical Optimization Specialist
Ed Klotz
Dr. Ed Klotz has over 30 years of experience in the mathematical optimization software industry. He is a technical expert who, over the course of his career, has worked with a wide array of customers to help them solve some of world’s most challenging mathematical optimization problems. In his role as a Senior Mathematical Optimization Specialist on the Gurobi R&D team, Dr. Klotz works closely with our customers to support them in implementing and utilizing mathematical optimization in their organizations. He also interacts heavily with the R&D team based on his experiences with the customers.
Prior to joining Gurobi, Dr. Klotz was a member of the CPLEX development team of IBM. He was involved in product development, customer training, product documentation, and numerous other tasks, with a primary focus on delivering CPLEX customer support and leveraging his experiences with customers to help inform the R&D team about customer needs and product improvements. Dr. Klotz has extensive knowledge in linear programming, integer programming, and numerical linear algebra for finite precision computing. Using this knowledge, he was able to investigate customer support issues at the source code level and identify potential improvements in CPLEX, both in terms of performance and accuracy of computation.
Before joining IBM, Dr. Klotz was a principal technical support engineer at ILOG, Inc., and a mathematical programming specialist at CPLEX Optimization, Inc.
Dr. Klotz has presented at numerous conferences, workshops, and web seminars and published numerous papers on mathematical optimization. His interests are in all aspects of mathematical programming, with a primary interest in research that can impact mathematical programming software. He obtained a BA in Math and Economics from Oberlin College and a PhD in Operations Research from Stanford University.
