- Award ID(s):
- 1810108
- NSF-PAR ID:
- 10257305
- Date Published:
- Journal Name:
- IEEE Transactions on Automation Science and Engineering
- Volume:
- Early access
- ISSN:
- 1545-5955
- Page Range / eLocation ID:
- 1 to 14
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
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
-
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
-
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
-
Abstract We consider the convex quadratic optimization problem in
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$$\mathbb {R}^{n}$$ 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.$$(n+1) \times (n+1)$$ -
Abstract Mixed-Integer Linear Programming (MILP) plays an important role across a range of scientific disciplines and within areas of strategic importance to society. The MILP problems, however, suffer from
combinatorial complexity . Because of integer decision variables, as the problem size increases, the number of possible solutions increasessuper-linearly thereby leading to a drastic increase in the computational effort. To efficiently solve MILP problems, a “price-based” decomposition and coordination approach is developed to exploit 1. the super-linear reduction of complexity upon the decomposition and 2. the geometric convergence potential inherent to Polyak’s stepsizing formula for the fastest coordination possible to obtain near-optimal solutions in a computationally efficient manner. Unlike all previous methods to set stepsizes heuristically by adjusting hyperparameters, the key novel way to obtain stepsizes is purely decision-based: a novel “auxiliary” constraint satisfaction problem is solved, from which the appropriate stepsizes are inferred. Testing results for large-scale Generalized Assignment Problems demonstrate that for the majority of instances, certifiably optimal solutions are obtained. For stochastic job-shop scheduling as well as for pharmaceutical scheduling, computational results demonstrate the two orders of magnitude speedup as compared to Branch-and-Cut. The new method has a major impact on the efficient resolution of complex Mixed-Integer Programming problems arising within a variety of scientific fields.