skip to main content
US FlagAn official website of the United States government
dot gov icon
Official websites use .gov
A .gov website belongs to an official government organization in the United States.
https lock icon
Secure .gov websites use HTTPS
A lock ( lock ) or https:// means you've safely connected to the .gov website. Share sensitive information only on official, secure websites.

Explore Research Products in the PAR
It may take a few hours for recently added research products to appear in PAR search results.


Title: A Systematic Formulation Tightening Approach for Unit Commitment Problems
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
Award ID(s):
1810108 1831811
PAR ID:
10110465
Author(s) / Creator(s):
; ; ; ; ; ; ;
Date Published:
Journal Name:
IEEE Transactions on Power Systems
ISSN:
0885-8950
Page Range / eLocation ID:
1 to 1
Format(s):
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. ; ; (, IEEE Transactions on Automation Science and Engineering)
    null (Ed.)
    Job shops are an important production environment for low-volume high-variety manufacturing. Its scheduling has recently been formulated as an Integer Linear Programming (ILP) problem to take advantages of popular Mixed-Integer Linear Programming (MILP) methods, e.g., branch-and-cut. When considering a large number of parts, MILP methods may combinatorial difficulties. To address this, a critical but much overlooked issue is formulation tightening. The idea is that if problem constraints can be transformed to directly delineate the problem convex hull in the data preprocessing stage, then a solution can be obtained by using linear programming methods without combinatorial difficulties. The tightening process, however, is fundamentally challenging because of the existence of integer variables. In this paper, an innovative and systematic approach is established for the first time to tighten the formulations of individual parts, each with multiple operations, in the data preprocessing stage. It is a major advancement of our previous work on problems with binary and continuous variables to integer variables. The idea is to first link integer variables to binary variables by innovatively combining constraints so that the integer variables are uniquely determined by the binary variables. With binary and continuous variables only, it is proved that the vertices of the convex hull can be obtained based on vertices of the linear problem after relaxing binary requirements. These vertices are then converted to tightened constraints for general use. This approach significantly improves our previous results on tightening individual operations. Numerical results demonstrate significant benefits on solution quality and computational efficiency. This approach also applies to other ILP problems with similar characteristics and fundamentally changes the way how such problems are formulated and solved. 
    more » « less
  2. ; ; ; ; ; ; ; ; (, 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. (, 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. ; ; ; (, 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 ) × ( 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
  5. ; ; ; (, IEEE international conference on computer communications (INFOCOM))
    We investigate competitive online algorithms for online convex optimization (OCO) problems with linear in-stage costs, switching costs and ramp constraints. While OCO problems have been extensively studied in the literature, there are limited results on the corresponding online solutions that can attain small competitive ratios. We first develop a powerful computational framework that can compute an optimized competitive ratio based on the class of affine policies. Our computational framework can handle a fairly general class of costs and constraints. Compared to other competitive results in the literature, a key feature of our proposed approach is that it can handle scenarios where infeasibility may arise due to hard feasibility constraints. Second, we design a robustification procedure to produce an online algorithm that can attain good performance for both average-case and worst-case inputs. We conduct a case study on Network Functions Virtualization (NFV) orchestration and scaling to demonstrate the effectiveness of our proposed methods. 
    more » « less
  • Citation Formats
  • MLA
  • APA
  • Chicago
  • BibTeX
  • Save / Share this Record
  • Send to Email