More Like this

1. A Systematic Formulation Tightening Approach for Unit Commitment Problems

   https://doi.org/10.1109/TPWRS.2019.2935003  

   Yan, Bing; Luh, Peter; Zheng, Tongxin; Schiro, Dane; Bragin, Mikhail; Zhao, Feng; Zhao, Jinye; Lelic, Izudin (August 2019, IEEE Transactions on Power Systems)

   Unit Commitment is usually formulated as a Mixed Binary Linear Programming (MBLP) problem. When considering a large number of units, state-of-the-art methods such as branch-and-cut may experience difficulties. To address this, an important but much overlooked direction is formulation transformation since if the problem constraints can be transformed to directly delineate the convex hull in the data pre-processing stage, then a solution can be obtained by using linear programming methods without combinatorial difficulties. In the literature, a few tightened formulations for single units with constant ramp rates were reported without presenting how they were derived. In this paper, a systematic approach is developed to tighten formulations in the data pre-processing stage. The idea is to derive vertices of the convex hull without binary requirements. From them, vertices of the original convex hull can be innovatively obtained. These vertices are converted to tightened constraints, which are then parameterized based on unit parameters for general use, tremendously reducing online computational requirements. By analyzing short-time horizons, e.g., two or three hours, tightened formulations for single units with constant and generation-dependent ramp rates are obtained, beyond what is in the literature. Results demonstrate computational efficiency and solution quality benefits of formulation tightening. 

   more » « less
2. Effects of Tightening Unit-level and System-level Constraints in Unit Commitment,

   Yan, Bing; Luh, Peter B.; Litvinov, Eugene; Zheng, Tongxin; Schiro, Dane; Bragin, Mikhail A.; Zhao, Feng; Zhao, Jinye; Lelic, Izudin (August 2019, IEEE Power & Energy Society General Meeting)

   Unit Commitment is an important problem faced by independent system operators. It is usually formulated as a Mixed Binary Linear Programming (MBLP) problem, and is believed to be NP hard. To solve UC problems efficiently, an idea is through formulation tightening. If constraints can be transformed to directly delineate an MBLP problem’s convex hull during data preprocessing, then the problem can be solved by using linear programming methods. The resulting formulation can be reused for other data sets, tremendously reducing computational requirements. To achieve the above goal, both unit- and system-level constraints are tightened with synergistic combination in this paper. Unit-level constraints are tightened based on existing cuts and novel “constraint-and-vertex conversion” and vertex projection processes. To tighten system-level constraints, selected cuts are applied and some potentially powerful cuts are identified. Numerical results demonstrate the effectiveness of tightening unit- and system-level constraints. 

   more » « less
3. Tightened Formulation and Resolution of Energy-Efficient Job-Shop Scheduling

   Bing Yan, Mikhail A. (August 2020, IEEE Conference on Automation Science and Engineering)

   null (Ed.)

   Job shops are an important production environment for low-volume high-variety manufacturing. When there are urgent orders, the speeds of certain machines can be adjusted with a high energy and wear and tear cost. Scheduling in such an environment is to achieve on-time deliveries and low energy costs. The problem is, however, complicated because part processing time depends on machine speeds, and machines need to be modeled individually to capture energy costs. This paper is to obtain near-optimal solutions efficiently. The problem is formulated as a Mixed-Integer Linear Programming (MILP) form to make effective use of available MILP methods. This is done by modeling machines in groups for simplicity while approximating energy costs, and by linking part processing status and machine speed variables. Nevertheless, the resulting problem is still complicated. The formulation is therefore transformed by extending our previous tightening approach for machines with constant speeds. The idea is that if constraints can be transformed to directly delineate the convex hull, then the problem can be solved by linear programming methods. To solve the problem efficiently, our advanced decomposition and coordination method is used. Numerical results show that near-optimal solutions are obtained, demonstrating significant benefits of our approach on on-time deliveries and energy costs. 

   more » « less
4. Synthesizing MILP Constraints for Efficient and Robust Optimization

   https://doi.org/10.1145/3591298  

   Wang, Jingbo; Gupta, Aarti; Wang, Chao (June 2023, Proceedings of the ACM on Programming Languages)

   While mixed integer linear programming (MILP) solvers are routinely used to solve a wide range of important science and engineering problems, it remains a challenging task for end users to write correct and efficient MILP constraints, especially for problems specified using the inherently non-linear Boolean logic operations. To overcome this challenge, we propose a syntax guided synthesis (SyGuS) method capable of generating high-quality MILP constraints from the specifications expressed using arbitrary combinations of Boolean logic operations. At the center of our method is an extensible domain specification language (DSL) whose expressiveness may be improved by adding new integer variables as decision variables, together with an iterative procedure for synthesizing linear constraints from non-linear Boolean logic operations using these integer variables. To make the synthesis method efficient, we also propose an over-approximation technique for soundly proving the correctness of the synthesized linear constraints, and an under-approximation technique for safely pruning away the incorrect constraints. We have implemented and evaluated the method on a wide range of benchmark specifications from statistics, machine learning, and data science applications. The experimental results show that the method is efficient in handling these benchmarks, and the quality of the synthesized MILP constraints is close to, or higher than, that of manually-written constraints in terms of both compactness and solving time. 

   more » « less
5. On the convex hull of convex quadratic optimization problems with indicators

   https://doi.org/10.1007/s10107-023-01982-0  

   Wei, Linchuan; Atamtürk, Alper; Gómez, Andrés; Küçükyavuz, Simge (June 2023, Mathematical Programming)

   Abstract We consider the convex quadratic optimization problem in$$\mathbb {R}^{n}$$ $R^n$with indicator variables and arbitrary constraints on the indicators. We show that a convex hull description of the associated mixed-integer set in an extended space with a quadratic number of additional variables consists of an$$(n+1) \times (n+1)$$ $(n+1)\times (n+1)$positive semidefinite constraint (explicitly stated) and linear constraints. In particular, convexification of this class of problems reduces to describing a polyhedral set in an extended formulation. While the vertex representation of this polyhedral set is exponential and an explicit linear inequality description may not be readily available in general, we derive a compact mixed-integer linear formulation whose solutions coincide with the vertices of the polyhedral set. We also give descriptions in the original space of variables: we provide a description based on an infinite number of conic-quadratic inequalities, which are “finitely generated.” In particular, it is possible to characterize whether a given inequality is necessary to describe the convex hull. The new theory presented here unifies several previously established results, and paves the way toward utilizing polyhedral methods to analyze the convex hull of mixed-integer nonlinear sets. 

   more » « less