Integer Programming

On the convexification of constrained quadratic optimization problems with indicator variables

Categories (Mixed) Integer Nonlinear Programming, Quadratic Programming Tags , , , ,

Motivated by modern regression applications, in this paper, we study the convexification of quadratic optimization problems with indicator variables and combinatorial constraints on the indicators. Unlike most of the previous work on convexification of sparse regression problems, we simultaneously consider the nonlinear objective, indicator variables, and combinatorial constraints. We prove that for a separable quadratic … Read more

Lossless Compression of Deep Neural Networks

Categories (Mixed) Integer Linear Programming, Applications - Science and Engineering

Deep neural networks have been successful in many predictive modeling tasks, such as image and language recognition, where large neural networks are often used to obtain good accuracy. Consequently, it is challenging to deploy these networks under limited computational resources, such as in mobile devices. In this work, we introduce an algorithm that removes units … Read more

Achieving Consistency with Cutting Planes

Categories 0-1 Programming, Cutting Plane Approaches Tags , , , ,

Cutting planes accelerate branch-and-bound search primarily by cutting off fractional solutions of the linear programming (LP) relaxation, resulting in tighter bounds for pruning the search tree. Yet cutting planes can also reduce backtracking by excluding inconsistent partial assignments that occur in the course of branching. A partial assignment is inconsistent with a constraint set when … Read more

Stochastic Dual Dynamic Programming for Multistage Stochastic Mixed-Integer Nonlinear Optimization

Categories (Mixed) Integer Nonlinear Programming, Global Optimization, Stochastic Programming Tags , , ,

In this paper, we study multistage stochastic mixed-integer nonlinear programs (MS-MINLP). This general class of problems encompasses, as important special cases, multistage stochastic convex optimization with \emph{non-Lipschitz-continuous} value functions and multistage stochastic mixed-integer linear optimization. We develop stochastic dual dynamic programming (SDDP) type algorithms with nested decomposition, deterministic sampling, and stochastic sampling. The key ingredient … Read more

Outer Approximation for Global Optimization of Mixed-Integer Quadratic Bilevel Problems

Categories (Mixed) Integer Nonlinear Programming, Quadratic Programming Tags , , ,

Bilevel optimization problems have received a lot of attention in the last years and decades. Besides numerous theoretical developments there also evolved novel solution algorithms for mixed-integer linear bilevel problems and the most recent algorithms use branch-and-cut techniques from mixed-integer programming that are especially tailored for the bilevel context. In this paper, we consider MIQP-QP … Read more

Convex Hulls for Non-Convex Mixed-Integer Quadratic Programs with Bounded Variables

Categories (Mixed) Integer Nonlinear Programming, Cutting Plane Approaches, Polyhedra

We consider non-convex mixed-integer quadratic programs in which all variables are explicitly bounded. Many exact methods for such problems use additional variables, representing products of pairs of original variables. We study the convex hull of feasible solutions in this extended space. Some other approaches use bit representation to convert bounded integer variables into binary variables. … Read more

Inversion of Convection-Diffusion Equation with Discrete Sources

Categories (Mixed) Integer Nonlinear Programming, Systems governed by Differential Equations Optimization

We present a convection-diffusion inverse problem that aims to identify an unknown number of sources and their locations. We model the sources using a binary function, and we show that the inverse problem can be formulated as a large-scale mixed-integer nonlinear optimization problem. We show empirically that current state-of-the-art mixed-integer solvers cannot solve this problem … Read more

Exact and Heuristic Approaches for a New Circular Layout Problem

Categories (Mixed) Integer Linear Programming, Meta Heuristics, Production and Logistics Tags , , , ,

We discuss a new facility layout problem, the so-called Directed Circular Facility Layout Problem (DCFLP). The DCFLP aims to find an optimal arrangement of machines on a circular material handling system such that the total weighted sum of the center-to-center distances between all pairs of machines measured in clockwise direction is minimized. Several real-world applications, … Read more

Sample Average Approximation for Stochastic Nonconvex Mixed Integer Nonlinear Programming via Outer Approximation

Categories (Mixed) Integer Nonlinear Programming, Stochastic Programming Tags , , ,

Stochastic mixed-integer nonlinear programming (MINLP) is a very challenging type of problem. Although there have been recent advances in developing decomposition algorithms to solve stochastic MINLPs, none of the existing algorithms can address stochastic MINLPs with continuous distributions. We propose a sample average approximation-based outer approximation algorithm (SAAOA) that can address nonconvex two-stage stochastic programs … Read more

The Impact of Neighboring Markets on Renewable Locations, Transmission Expansion, and Generation Investment

Categories (Mixed) Integer Nonlinear Programming, Applications - OR and Management Sciences, Global Optimization Tags , , , ,

Many long-term investment planning models for liberalized electricity markets either optimize for the entire electricity system or focus on confined jurisdictions, abstracting from adjacent markets. In this paper, we provide models for analyzing the impact of the interdependencies between a core electricity market and its neighboring markets on key long-run decisions. This we do both … Read more