The Min-up/min-down Unit Commitment Problem (MUCP) is to find a minimum-cost production plan on a discrete time horizon for a set of fossil-fuel units for electricity production. At each time period, the total production has to meet a forecasted demand. Each unit must satisfy minimum up-time and down-time constraints besides featuring production and start-up costs. … Read more
In this paper, we consider the control problem with the Average-Value-at-Risk (AVaR) criteria of the possibly unbounded L 1 -costs in infinite horizon on a Markov Decision Process (MDP). With a suitable state aggregation and by choosing a priori a global variable s heuristically, we show that there exist optimal policies for the infinite horizon … Read more
In this paper, we analyze the convergence of the alternating direction method of multipliers (ADMM) for minimizing a nonconvex and possibly nonsmooth objective function, $\phi(x_0,\ldots,x_p,y)$, subject to coupled linear equality constraints. Our ADMM updates each of the primal variables $x_0,\ldots,x_p,y$, followed by updating the dual variable. We separate the variable $y$ from $x_i$’s as it … Read more
SAP’s decision support systems for optimized supply network planning rely on mixed-integer programming as the core engine to compute optimal or near-optimal solutions. The modeling flexibility and the optimality guarantees provided by mixed-integer programming greatly aid the design of a robust and future-proof decision support system for a large and diverse customer base. In this … Read more
Software for mixed-integer linear programming can return incorrect results for a number of reasons, one being the use of inexact floating-point arithmetic. Even solvers that employ exact arithmetic may suffer from programming or algorithmic errors, motivating the desire for a way to produce independently verifiable certificates of claimed results. Due to the complex nature of … Read more
The analysis of infeasible subproblems plays an import role in solving mixed integer programs (MIPs) and is implemented in most major MIP solvers. There are two fundamentally different concepts to generate valid global constraints from infeasible subproblems. The first is to analyze the sequence of implications obtained by domain propagation that led to infeasibility. The … Read more
In this paper, we focus our study on the convergence of (proximal) gradient methods and accelerated (proximal) gradient methods for smooth (composite) optimization under a H\”{o}lderian error bound (HEB) condition. We first show that proximal gradient (PG) method is automatically adaptive to HEB while accelerated proximal gradient (APG) method can be adaptive to HEB by … Read more
We show how random projections can be used to solve large-scale dense linear programs approximately. This is a new application of techniques which are now fairly well known in probabilistic algorithms, but have never yet been systematically applied to the fundamental class of Linear Programming. We develop the necessary theoretical framework, and show that this … Read more
We investigate three competing notions that generalize the notion of a facet of finite-dimensional polyhedra to the infinite-dimensional Gomory–Johnson model. These notions were known to coincide for continuous piecewise linear functions with rational breakpoints. We show that two of the notions, extreme functions and facets, coincide for the case of continuous piecewise linear functions, removing … Read more
We are interested in the existence of Pareto solutions to the vector optimization problem $$\text{\rm Min}_{\,\mathbb{R}^m_+} \{f(x) \,|\, x\in \mathbb{R}^n\},$$ where $f\colon\mathbb{R}^n\to \mathbb{R}^m$ is a polynomial map. By using the {\em tangency variety} of $f$ we first construct a semi-algebraic set of dimension at most $m – 1$ containing the set of Pareto values of … Read more