Publication Type

Conference Proceeding Article

Version

publishedVersion

Publication Date

6-2023

Abstract

A disjointly constrained bilinear program (DBLP) has various practical and industrial applications, e.g., in game theory, facility location, supply chain management, and multi-agent planning problems. Although earlier work has noted the equivalence of DBLP and mixed-integer linear programming (MILP) from an abstract theoretical perspective, a practical and exact closed-form reduction of a DBLP to a MILP has remained elusive. Such explicit reduction would allow us to leverage modern MILP solvers and techniques along with their solution optimality and anytime approximation guarantees. To this end, we provide the first constructive closed-form MILP reduction of a DBLP by extending the technique of symbolic variable elimination (SVE) to constrained optimization problems with bilinear forms. We apply our MILP reduction method to difficult DBLPs including XORs of linear constraints and show that we significantly outperform Gurobi. We also evaluate our method on a variety of synthetic instances to analyze the effects of DBLP problem size and sparsity w.r.t. MILP compilation size and solution efficiency.

Keywords

Bilinear programming; Symbolic variable elimination

Discipline

Artificial Intelligence and Robotics | Operations Research, Systems Engineering and Industrial Engineering

Research Areas

Intelligent Systems and Optimization

Publication

Integration of Constraint Programming, Artificial Intelligence, and Operations Research: 20th International Conference, CPAIOR 2023, Nice, France, May 29-June 1: Proceedings

Volume

13884

First Page

79

Last Page

95

ISBN

9783031332708

Identifier

10.1007/978-3-031-33271-5_6

Publisher

Springer

City or Country

Cham

Additional URL

https://doi.org/10.1007/978-3-031-33271-5_6

Download

Share

COinS