Principal component analysis (PCA) is one of the most widely used dimensionality reduction methods in scientific data analysis. In many applications, for additional interpretability, it is desirable for the factor loadings to be sparse, that is, we solve PCA with an additional cardinality (l0) constraint. The resulting optimization problem is called the sparse principal component … Read more
We develop a new class of approximate linear programs (ALPs) that project the high-dimensional value function of dynamic programs onto a class of basis functions, each defined as a network that represents aggregrations over the state space. The resulting ALP is a minimum-cost flow problem over an extended variable space that synchronizes flows across multiple … Read more
We discuss a tightly feasible mixed-integer linear programs arising in the energy industry, for which branch-and-bound appears to be ineffective. We consider its hardness, measure the probability that randomly generated instances are feasible or almost feasible, and introduce heuristic solution methods based on relaxing different constraints of the problem. We show the computational efficiency of … Read more
We propose an algorithm based on infeasible irreducible subsystems (IIS) to solve general binary chance-constrained problems. By leverag- ing on the problem structure we are able to generate good quality upper bounds to the optimal value early in the algorithm, and the discrete do- main is used to guide us eciently in the search of … Read more
In this paper, we consider the two-stage extension of the one-dimensional cutting stock problem which arises when technical requirements inhibit the cutting of large stock rolls to demanded widths of finished rolls directly. Therefore, the demands on finished rolls are fulfilled through two subsequent cutting processes, in which the rolls produced in the former are … Read more
We exactly solve the NP-hard combinatorial optimization problem of finding a minimum cardinality vertex separator with k (or arbitrarily many) capacitated shores in a hypergraph. We present an exponential size integer programming formulation which we solve by branch-and-price. The pricing problem, an interesting optimization problem on its own, has a decomposable structure that we exploit … Read more
In this paper, we study the strength of aggregation cuts for sign-pattern integer programs (IPs). Sign-pattern IPs are a generalization of packing IPs and are of the form {x \in Z^n | Ax = 0} where for a given column j, A_{ij} is either non-negative for all i or non-positive for all i. Our first … Read more
In this paper we derive an efficient optimization approach to calculate optimal controls of electric transmission lines. These controls consist of time-dependent inflows and switches that temporarily disable single arcs or whole subgrids to reallocate the flow inside the system. The aim is then to find the best energy input in terms of boundary controls … Read more
A probabilistic framework for large classes of binary integer programming problems is constructed. The approach is given by a mean field annealing scheme where the annealing phase is substituted by the solution of a dual problem that gives a lower (upper) bound for the original minimization (maximization) integer task. This bound has an information theoretic … Read more
We study the covering-type k-violation linear program where at most $k$ of the constraints can be violated. This problem is formulated as a mixed integer program and known to be strongly NP-hard. In this paper, we present a simple (k+1)-approximation algorithm using a natural LP relaxation. We also show that the integrality gap of the … Read more