Skip to main content

Please enter a keyword and click the arrow to search the site

A unified approach to mixed-integer optimization with logical constraints

Journal

SIAM Journal on Optimization

Subject

Management Science and Operations

Authors / Editors

Bertsimas D;Cory-Wright R;Pauphilet J

Biographies

Publication Year

2021

Abstract

We propose a united framework to address a family of classical mixed-integer optimization problems with logically constrained decision variables, including network design, facility location, unit commitment, sparse portfolio selection, binary quadratic optimization, sparse principal component analysis, and sparse learning problems. These problems exhibit logical relationships between continuous and discrete variables, which are usually reformulated linearly using a big-M formulation. In this work, we challenge this longstanding modeling practice and express the logical constraints in a non-linear way. By imposing a regularization condition, we reformulate these problems as convex binary optimization problems, which are solvable using an outer-approximation procedure. In numerical experiments, we establish that a general-purpose numerical strategy, which combines cutting-plane, first-order, and local search methods, solves these problems faster and at a larger scale than state-of-the-art mixed-integer linear or second-order cone methods. Our approach successfully solves network design problems with 100s of nodes and provides solutions up to 40% better than the state-of-the-art; sparse portfolio selection problems with up to 3,200 securities compared with 400 securities for previous attempts; and sparse regression problems with up to 100,000 covariates.

Available on ECCH

No


Select up to 4 programmes to compare

Select one more to compare
×
subscribe_image_desktop 5949B9BFE33243D782D1C7A17E3345D0

Sign up to receive our latest news and business thinking direct to your inbox

×

Sign up to receive our latest course information and business thinking

Leave your details above if you would like to receive emails containing the latest thought leadership, invitations to events and news about courses that could enhance your career. If you would prefer not to receive our emails, you can still access the case study by clicking the button below. You can opt-out of receiving our emails at any time by visiting: https://london.edu/my-profile-preferences or by unsubscribing through the link provided in our emails. View our Privacy Policy for more information on your rights.