James Ostrowski This study presents a polynomial time algorithm to solve the lossless battery charging problem. In this problem the optimal charging and discharging schedules are chosen to maximize total profit. Traditional solution approaches have relied on either approximations or exponential algorithms. By studying the optimality conditions of this problem, we are able to reduce it to … Read more
Symmetry in optimization has been known to wreak havoc in optimization algorithms. Often, some of the hardest instances are highly symmetric. This is not the case in linear programming, as symmetry allows one to reduce the size of the problem, possibly dramatically, while still maintaining the same optimal objective value. This is done by aggregating … Read more
Cutting planes have been an important factor in the impressive progress made by integer programming (IP) solvers in the past two decades. However, cutting planes have had little impact on improving performance for symmetric IPs. Rather, the main breakthroughs for solving symmetric IPs have been achieved by cleverly exploiting symmetry in the enumeration phase of … Read more
Electricity markets worldwide allow participants to bid non-convex production offers. While non-convex offers can more accurately reflect a resource’s capabilities, they create challenges for market clearing processes. For example, system operators may be required to execute side payments to participants whose costs are not covered through energy sales as determined via traditional locational marginal pricing … Read more
This paper presents conditions for which the linear relaxation for the train scheduling problem is integer-optimal. These conditions are then used to identify how to partition a general problem’s feasible region into integer-optimal polytopes. Such an approach yields an extended formulation that contains far fewer binary variables. Our computational experiments show that this approach results … Read more
Citation Department of Industrial and Systems Engineering University of Tennessee, Knoxville, TN 37996 November 2018 Article Download View CHANGE ME
We present sufficient conditions under which thermal generators can be aggregated in mixed-integer linear programming (MILP) formulations of the unit commitment (UC) problem, while maintaining feasibility and optimality for the original disaggregated problem. Aggregating thermal generators with identical characteristics (e.g., minimum/maximum power output, minimum up/down-time, and cost curves) into a single unit reduces redundancy in … Read more
We present a novel formulation for startup cost computation in the unit commitment problem (UC). Both the proposed formulation and existing formulations in the literature are placed in a formal, theoretical dominance hierarchy based on their respective linear programming relaxations. The proposed formulation is tested empirically against existing formulations on large-scale unit commitment instances drawn … Read more
We present a branch-and-bound framework to solve the following problem: Given a graph G and an integer k, find a subgraph of G formed by removing no more than k edges that contains the most symmetry. We call symmetries on such a subgraph “almost symmetries” of G. We implement our branch-and-bound framework in PEBBL to … Read more
We present a perfect formulation for a single generator in the unit commitment problem, inspired by the dynamic programming approach taken by Frangioni and Gentile. This generator can have characteristics such as ramping constraints, time-dependent start-up costs, and start-up/shut-down ramping. To develop this perfect formulation we extend the result of Balas on unions of polyhedra … Read more