Gas network optimization manages the gas transport by minimizing operating costs and fulfilling contracts between consumers and suppliers. This is an NP- hard problem governed by non-convex and nonlinear gas transport functions that can be modeled by mixed integer linear programming (MILP) techniques. Under these methods, piecewise linear functions describe nonlinearities and bi- nary variables … Read more
In this work we consider the uniform capacitated single-item single-machine lot-sizing problem with continuous start-up costs. A continuous start-up cost is generated in a period whenever there is a nonzero production in the period and the production capacity in the previous period is not saturated. This concept of start-up does not correspond to the standard … Read more
In this paper we propose a methodology for constructing decision rules for integer and continuous decision variables in multiperiod robust linear optimization problems. This type of problems finds application in, for example, inventory management, lot sizing, and manpower management. We show that by iteratively splitting the uncertainty set into subsets one can differentiate the later-period … Read more
Given a directed graph G = (V, A) with arbitrary arc costs, the Elementary Shortest Path Problem (ESPP) consists of finding a minimum-cost path between two nodes s and t such that each node of G is visited at most once. If the costs induce negative cycles on G, the problem is NP-hard. In this … Read more
Private investors, flexibility, efficiency and environmental requirements from deregulated markets have led the existence and building of a significant number of combined-cycle gas turbines (CCGTs) in many power systems. These plants represent a complicated optimization problem for the short-term planning unit commitment (UC) carried out by independent system operators due to their multiple operating configurations. … Read more
Motivated by concave cost combinatorial optimization problems, we study the following mixed integer nonlinear set: P = {(w,x) : w >= f(a’x), e’x
In this paper we consider multiperiod mixed 0–1 linear programming models under uncertainty. We propose a risk averse strategy using stochastic dominance constraints (SDC) induced by mixed-integer linear recourse as the risk measure. The SDC strategy extends the existing literature to the multistage case and includes both first-order and second-order constraints. We propose a stochastic … Read more
The plethora of research on NP-hard parallel machine scheduling problems is focused on heuristics due to the theoretically and practically challenging nature of these problems. Only a handful of exact approaches are available in the literature, and most of these suffer from scalability issues. Moreover, the majority of the papers on the subject are restricted … Read more
When addressing the maximum stable set problem on a graph G = (V,E), rank inequalities prescribe that, for any subgraph G[U] induced by U ⊆ V , at most as many vertices as the stability number of G[U] can be part of a stable set of G. These inequalities are very general, as many of … Read more
Motivated by Bland’s linear-programming generalization of the renowned Edmonds-Karp efficient refinement of the Ford-Fulkerson maximum-flow algorithm, we discuss three closely-related natural augmentation rules for linear and integer-linear optimization. In several nice situations, we show that polynomially-many augmentation steps suffice to reach an optimum. In particular, when using “discrete steepest-descent augmentations” (i.e., directions with the best … Read more