New MINLP Formulations for the Unit Commitment Problem with Ramping Constraints

T. Bacci, A. Frangioni, C. Gentile, K. Tavlaridis-Gyparakis

Operations Research Article in Advance, 2023.

Abstract: The unit commitment (UC) problem in electrical power production requires to optimally operate a set of power generation units over a short time horizon. Operational con­ straints of each unit depend on its type and can be rather complex. For thermal units, typical ones concern minimum and maximum power output, minimum up- and down-time, start- up and shut-down limits, ramp-up and ramp-down limits, and nonlinear objective function. In this work, we present the first mixed-integer nonlinear program formulation that des­ cribes the convex hull of the feasible solutions of the single-unit commitment problem compris­ ing all the above constraints and convex power generation costs. The new formulation has a polynomial number of both variables and constraints, and it is based on the efficient dynamic programming algorithm proposed by Frangioni and Gentile together with the per­ spective reformulation. The proof that the formulation is exact is based on a new extension of a result previously only available in the polyhedral case, which is potentially of interest in itself. We then analyze the effect of using it to develop tight formulations for the more gen­ eral UC problem. Because the formulation is rather large, we also propose two new formula­ tions, based on partial aggregations of variables, with different trade-offs between quality of the bound and cost of solving the continuous relaxation. Our results show that navigating these trade-offs may lead to improved performances.

Keywords: Unit commitment problem, Ramp constraints, MIP formulations, Dynamic Programming, convex costs.

The published paper is available at https://doi.org/10.1287/opre.2023.2435. A Technical Report version is available here.

Comparing Perspective Reformu- lations for Piecewise-Convex Optimization

R. S. Trindade, C. D’Ambrosio, A. Frangioni, C. Gentile

Operations Research Letters 51(6), 702-708, 2023.

Abstract: Our study is motivated by the solution of Mixed-Integer Non-Linear Programming (MINLP) problems with separable non-convex functions via the Sequential Convex MINLP technique, an iterative method whose main characteristic is that of solving, for bounding purposes, piecewise-convex MINLP relaxations obtained by identifying the intervals in which each univariate function is convex or concave and then relaxing the concave parts with piecewise-linear relaxations of increasing precision. This process requires the introduction of new binary variables for the activation of the intervals where the functions are defined. In this paper we compare the three different standard formulations for the lower bounding subproblems and we show, both theoretically and computationally, that -- unlike in the piecewise-linear case -- they are not equivalent when the perspective reformulation is applied to reinforce the formulation in the segments where the original functions are convex.

Keywords: Piecewise-convex MINLP problems, Perspective reformulation, Formulations comparison, Sequential convex MINLP technique

The published paper is available at https://doi.org/10.1016/j.orl.2023.11.003. A Technical Report version is available here.

Price of robustness optimization through demand forecasting with an application to waste management

C. Gentile, D.M. Pinto, G. Stecca

Soft Computing 27(18), 13013-13024, 2023.

Abstract: Robust optimization can be effectively used to protect production plans against uncertainties. This is particularly important in sectors where variability is inherent the process to be planned. The drawback of robust optimization is the chance of producing over-conservative solutions with respect to the real occurrences of the stochastic parameters. Information can be added in order to better control the extra cost resulting from considering the parameter variability. This work investigates how demand forecasting can be used in conjunction with robust optimization in order to achieve an optimal planning while considering demand uncertainties. In the proposed procedure, forecast is used to update uncertain parameters of the robust model. Moreover, the robustness budget is optimized at each planned stage in a rolling planning horizon. In this way, the parameters of the robust model can be dynamically updated tacking information from the data. The study is applied to a reverse logistics case, where the planning of sorting for material recycling is affected by uncertainties in the demand, consisting of waste material to be sorted and recycled. Results are compared with a standard robust optimization approach, using real case instances, showing potentialities of the proposed method.

Keywords: Robust Optimization; Circular Economy; Waste Recycling; Lot Sizing; Mixed Integer Linear Programming

The published paper is available at https://link.springer.com/article/10.1007/s00500-022-07148-y. A Technical Report version is available here.

An algorithm for the Microaggregation problem combining Column Generation and Polyhedral Methods

C. Gentile, E. Spagnolo, J. Castro

Computers and Operations Research 144, Article 105817, 2022.

Abstract: The field of statistical disclosure control aims to reduce the risk of re-identifying an individual from disseminated data, a major concern among national sta- tistical agencies. Operations Research (OR) techniques have been widely used in the past for protecting tabular data, but not microdata (i.e., files of individuals and attributes). To our knowledge, this is the first work to apply OR techniques to the microaggregation problem, which is considered one of the best methods for microdata protection and is known to be NP-hard. The new heuristic approach is based on a column generation scheme and, unlike previous (primal) heuristics for microaggregation, it also provides a lower bound on the optimal microaggregation. Using real data that is typi- cally used in the literature, our computational results show, first, that solu- tions with small gaps are often achieved and, second, that dramatic improve- ments are obtained relative to the literature’s most popular heuristics.

Keywords: Integer Programming, Column Generation, Data Privacy, Clustering, Microaggregation

The published paper is available at https://doi.org/10.1016/j.cor.2022.105817. A Technical Report version is available here.
Data used in the paper are available here.

Mathematical programming formulations for the alternating current optimal power flow problem

D. Bienstock, M. Escobar, C. Gentile, L. Liberti

Annals of Operations Research 314, 277-315, 2022.

Abstract: Power flow refers to the injection of power on the lines of an electrical grid, so that all the injections at the nodes form a consistent flow within the network. Optimality, in this setting, is usually intended as the minimization of the cost of generating power. Current can either be direct or alternating: while the former yields approximate linear programming formulations, the latter yields formulations of a much more interesting sort: namely, nonconvex nonlinear programs in complex numbers. In this technical survey, we derive formulation variants and relaxations of the alternating current optimal power flow problem.

Keywords: ACOPF, OPF, Power grid, Smart grid, Complex numbers


The published paper is available at https://doi.org/10.1007/s10479-021-04497-z.

Decompositions of Semidefinite Matrices and the Perspective Reformulation of Nonseparable Quadratic Programs

A. Frangioni, C. Gentile, J. Hungerford

Mathematics of Operations Research 45(1), 15 - 33, 2020.

Abstract: We study the problem of decomposing the Hessian matrix of a Mixed-Integer Convex Quadratic Program into the sum of positive semidefinite 2x2 matrices. Solving this problem enables the use of Perspective Reformulation techniques for obtaining strong lower bounds for MICQPs with semi-continuous variables but a nonseparable objective function. An explicit formula is derived for constructing 2x2 decompositions when the underlying matrix is Weakly Scaled Diagonally Dominant, and necessary and sufficient conditions are given for the decomposition to be unique. For matrices lying outside this class, two exact SDP approaches and an efficient heuristic are developed for finding approximate decompositions. We present preliminary results on the bound strength of a 2x2 Perspective Reformulation for the Portfolio Optimization Problem, showing that for some classes of instances the use of 2x2 matrices can significantly improve the quality of the bound w.r.t. the best previously known approach, although at a possibly high computational cost.

Keywords: Mixed-Integer Quadratic Programming, Matrix Decomposition, Scaled Diagonal Dominance, Semicontinuous variables, Portfolio Optimization.


The published paper is available at https://doi.org/10.1287/moor.2018.0969, but thanks to INFORMS provisions on Rights and Permissions, you can download the author accepted manuscript (AAM).

Mathematical programming formulations for the alternating current optimal power flow problem

D. Bienstock, M. Escobar, C. Gentile, L. Liberti

4OR 18(3), 249-292, 2020.

Abstract: Power flow refers to the injection of power on the lines of an electrical grid, so that all the injections at the nodes form a consistent flow within the network. Optimality, in this setting, is usually intended as the minimization of the cost of generating power. Current can either be direct or alternating: while the former yields approximate linear programming formulations, the latter yields formulations of a much more interesting sort: namely, nonconvex nonlinear programs in complex numbers. In this technical sur- vey, we derive formulation variants and relaxations of the alternating current optimal power flow problem.

Keywords: ACOPF, Smart grid, Complex numbers


The published paper is available at https://link.springer.com/article/10.1007/s10288-020-00455-w.

Strengthening the Sequential Convex MINLP Technique by Perspective Reformulations

C. D'Ambrosio, A. Frangioni, C. Gentile

Optimization Letters 13(4), p. 673 - 684, 2019.

Abstract: The Sequential Convex MINLP (SC-MINLP) technique is a solution method for nonconvex Mixed-Integer NonLinear Problems where the nonconvexities are separable. It is based on solving a sequence of convex MINLPs which trade a better and better relaxation of the nonconvex part of the problem with the introduction of more and more piecewise-linear nonconvex terms, and therefore binary variables. The convex MINLPs are obtained by partitioning the domain of each separable nonconvex term in the intervals in which it is convex and those in which it is concave. In the former, the term is left in its original form, while in the latter it is piecewise-linearized. Since each interval corresponds to a semi-continuous variable, we propose to modify the convex terms using the Perspective Reformulation technique to strengthen the bounds. We show by means of experimental results on different classes of instances that doing so significantly decreases the solution time of the convex MINLPs, which is the most time consuming part of the approach, and has therefore the potential to improving the overall effectiveness of SC-MINLP.

Keywords: Global Optimization, NonConvex Separable Functions, Sequential Convex MINLP Technique, Perspective Reformulation.

The published paper is available at https://link.springer.com/article/10.1007/s11590-018-1360-9. Thanks to the provisions of Springer's Copyright Transfer Statement, you can download the author-created version of the accepted manuscript here.

An Integral LP relaxation for a Drayage Problem

M. Di Francesco, C. Gentile, S. Schirra, G. Stecca, P. Zuddas

Discrete Optimization 31, p 93-102, 2019.

Abstract: This paper investigates a drayage problem, where a fleet of trucks must ship container loads from a port to importers and from exporters to the same port, without separating trucks and containers during customer service. We present three formulations for this problem that are valid when each truck carries one container. For the third formulation, we also assume that the arc costs are equal for all trucks, and then we prove that its continuous relaxation admits integer optimal solutions by checking that its constraint matrix is totally unimodular. Under the same hypothesis on costs, even the continuous relaxations of the first two models is proved to admit an integer optimal solution. Finally, the third model is transformed into a circulation problem, that can be solved by efficient network algorithms.

Keywords: Logistics, Vehicle Routing Problem, Drayage Problem, Total Unimodularity.

The published paper is available at https://doi.org/10.1016/j.disopt.2018.09.002.

Improving the Approximated Projected Perspective Reformulation by Dual Information

A. Frangioni, F. Furini, C. Gentile

Operations Research Letters 45(5), 519 - 524, 2017.

Abstract: We propose an improvement of the Approximated Projected Perspective Reformulation (AP2R) of [FFG16] for the case in which constraints linking the binary variables exist. The new approach requires to solve the Perspective Reformulation (PR) once, and then use the corresponding dual information to reformulate the problem prior to applying AP2R, thereby combining the root bound quality of the PR with the reduced relaxation computing time of AP2R. Computational results for the cardinality-constrained Mean-Variance portfolio optimization problem show that the new approach is competitive with state-of-the-art ones.

Keywords: Mixed-Integer NonLinear Problems, Semi-continuous Variables, Perspective Reformulation, Projection, Lagrangian Relaxation, Portfolio Optimization.

The published paper is available at http://dx.doi.org/10.1016/j.orl.2017.08.001. Thanks to Elsevier's provisions about Article Sharing, you can download the Author's accepted manuscript version here.

A Tight MIP Formulation of the Unit Commitment Problem with Start-up and Shut-down Constraints

C. Gentile, G. Morales-España, A. Ramos

EURO Journal on Computational Optimization 5(1), p. 177 - 201, 2017.

Abstract: This paper provides the convex hull description of the single thermal Unit Commitment (UC) problem with the following basic operating constraints: (1) generation limits, (2) start-up and shut-down capabilities, and (3) minimum up and down times. The proposed constraints can be used as the core of any unit commitment formulation to strengthen the lower bound in enumerative approaches. We provide evidence that dramatic improvements in computational time are obtained by solving the self-UC problem and the network-constrained UC problem with the new inequalities for different case studies.

Keywords: Unit commitment (UC) Mixed-integer programming (MIP) Facet/convex hull description

The published paper is available at http://dx.doi.org/10.1007/s13675-016-0066-y.
An open version of the accepted paper is available here.

The stable set polytope of icosahedral graphs

A. Galluccio, C. Gentile

Discrete Mathematics 339(2), p. 614 - 625, 2016.

Abstract: The problem of finding a complete linear description of the stable set polytope of claw-free graphs has been a major topic in combinatorial optimization in the last decades and it is still not completely solved. While it is known that this linear description contains facet defining inequalities with arbitrarily many and arbitrarily high coefficients, the set of claw-free graphs whose stable set polytope is described only by inequalities with {0,1,2}{0,1,2}-valued coefficients is considerably large. In fact Galluccio et al. (2014) proved that this set contains almost all claw-free graphs with stability number greater than three plus some of the building blocks with stability number smaller than or equal to three, identified by Chudnovsky and Seymour in their Structure Theorem.

Here we show that another important class of claw-free graphs with stability number three belongs to this set: the class of icosahedral graphs, named S1S1 by Chudnovsky and Seymour (2008). In particular, we prove that the stable set polytope of icosahedral graphs is described by: rank, lifted 5-wheel and lifted wedge inequalities, and all these linear inequalities have coefficients in {0,1,2}.


Keywords: Stable set polytope; Claw-free graphs; Icosahedron

The published paper is available at http://doi.org/10.1016/j.disc.2015.09.028.

Approximated Perspective Relaxations: a Project&Lift Approach

A. Frangioni, F. Furini, C. Gentile

Computational Optimization and Applications 63(3), p. 705 - 735, 2016.

Abstract: The Perspective Reformulation (PR) of a Mixed-Integer NonLinear Program with semi-continuous variables is obtained by replacing each term in the (separable) objective function with its convex envelope. Solving the corresponding continuous relaxation requires appropriate techniques. Under some rather restrictive assumptions, the Projected PR (P2R) can be defined where the integer variables are eliminated by projecting the solution set onto the space of the continuous variables only. This approach produces a simple piecewise-convex problem with the same structure as the original one; however, this prevents the use of general-purpose solvers, in that some variables are then only implicitly represented in the formulation. We show how to construct an Approximated Projected PR (AP2R) whereby the projected formulation is ``lifted'' back to the original variable space, with each integer variable expressing one piece of the obtained piecewise-convex function. In some cases, this produces a reformulation of the original problem with exactly the same size and structure as the standard continuous relaxation, but providing substantially improved bounds. In the process we also substantially extend the approach beyond the original P2R development by relaxing the requirement that the objective function be quadratic and the left endpoint of the domain of the variables be non-negative. While the AP2R bound can be weaker than that of the PR, this approach can be applied in many more cases and allows direct use of off-the-shelf MINLP software; this is shown to be competitive with previously proposed approaches in some applications.

Keywords: Mixed-integer nonlinear problems, Semi-continuous variables, Perspective reformulation, Projection

The published paper is available at http://doi.org/10.1007/s10589-015-9787-8. An open version of the accepted paper is available here.

Tight MIP Formulations of the Power-Based Unit Commitment Problem

G. Morales-España, C. Gentile, A. Ramos

OR Spectrum 37, p. 929 - 950, 2015.

Abstract: This paper provides the convex hull description for the basic operation of slow- and quick-start units in power-based unit commitment (UC) problems. The basic operating constraints that are modeled for both types of units are (1) generation limits and (2) minimum up and down times. Apart from this, the startup and shutdown processes are also modeled, using (3) startup and shutdown power trajectories for slow-start units, and (4) startup and shutdown capabilities for quick-start units. In the conventional UC problem, power schedules are used to represent the staircase energy schedule; however, this simplification leads to infeasible energy delivery, as stated in the literature. To overcome this drawback, this paper provides a power-based UC formulation drawing a clear distinction between power and energy. The proposed constraints can be used as the core of any power-based UC formulation, thus tightening the final mixed-integer programming UC problem. We provide evidence that dramatic improvements in computational time are obtained by solving different case studies, for self-UC and network-constrained UC problems.

Keywords: Convex hull, Unit commitment (UC), Mixed-integer programming (MIP), Tight formulation, Slow-start units, Quick-start units

The published paper is available at http://doi.org/10.1007/s00291-015-0400-4.

Perspective Reformulations of the CTA Problem with L2 Distances

J. Castro, A. Frangioni, C. Gentile

Operations Research 62(4), p. 891 - 909, 2014.

Abstract: Any institution that disseminates data in aggregated form has the duty to ensure that individual confidential information is not disclosed, either by not releasing data or by perturbing the released data, while maintaining data utility. Controlled tabular adjustment (CTA) is a promising technique of the second type where a protected table that is close to the original one in some chosen distance is constructed. The choice of the specific distance shows a trade-off: while the Euclidean distance has been shown (and is confirmed here) to produce tables with greater "utility", it gives rise to Mixed Integer Quadratic Problems (MIQPs) with pairs of linked semi-continuous variables that are more difficult to solve than the Mixed Integer Linear Problems corresponding to linear norms. We provide a novel analysis of Perspective Reformulations (PRs) for this special structure; in particular, we devise a Projected PR (P2R) which is piecewise-conic but simplifies to a (nonseparable) MIQP when the instance is symmetric. We then compare different formulations of the CTA problem, showing that the ones based on P2R most often obtain better computational results.

Keywords: Mixed Integer Quadratic Programming, Perspective Reformulation, Data Privacy, Statistical Disclosure Control, Tabular Data Protection, Controlled Tabular Adjustment

The published paper is available at http://dx.doi.org/10.1287/opre.2014.1293. A Technical Report version is available here.

The stable set polytope of claw-free graphs with stability number at least four. I. Fuzzy antihat graphs are W-perfect

A. Galluccio, C. Gentile, P. Ventura

Journal of Combinatorial Theory B 107, p. 92 - 122, 2014.

Abstract: Fuzzy antihat graphs are graphs obtained as 2-clique-bond compositions of fuzzy line graphs with three different types of three-cliqued graphs. By the decomposition theorem of Chudnovsky and Seymour, fuzzy antihat graphs form a large subclass of claw-free, not quasi-line graphs with stability number at least four and with no 1-joins. A graph is W-perfect if its stable set polytope is described by: nonnegativity, rank, and lifted 5-wheel inequalities. By exploiting the polyhedral properties of the 2-clique-bond composition, we prove that fuzzy antihat graphs are W-perfect and we move a crucial step towards the solution of the longstanding open question of finding an explicit linear description of the stable set polytope of claw-free graphs.

Keywords: Polyhedral combinatorics, stable set polytope, claw-free graphs

The published paper is available at http://doi.org/10.1016/j.jctb.2014.02.006

The stable set polytope of claw-free graphs with stability number at least four. II. Striped graphs are G-perfect

A. Galluccio, C. Gentile, P. Ventura

Journal of Combinatorial Theory B 108, p. 1 - 28, 2014.

Abstract: In 1965, Edmonds provided the first complete description of the polyhedron associated with a combinatorial optimization problem: the matching polytope. As the matching problem is equivalent to the stable set problem on line graphs, many researchers tried to generalize Edmonds' result by considering the stable set problem on a superclass of line graphs: the claw-free graphs. However, as testified also by Grötschel, Lovász, and Schrijver, "in spite of considerable efforts, no decent system of inequalities describing STAB(G) for claw-free graphs is known''. Here, we provide an explicit linear description of the stable set polytope of claw-free graphs with stability number at least four and with no 1-join.

Keywords: stable set polytope, claw-free graphs, homogeneous set

The published paper is available at http://doi.org/10.1016/j.jctb.2014.02.009

2-clique-bond of stable set polyhedra

A. Galluccio, C. Gentile, P. Ventura

Discrete Applied Mathematics 161, p. 1988 - 2000, 2013.

Abstract: The 2-bond is a generalization of the 2-join where the subsets of nodes that are connected on each shore of the partition are not necessarily disjoint. If all the subsets are cliques we say that the 2-bond is a 2-clique-bond. The 2-clique-bond composition builds a graph G admitting a 2-clique-bond starting from two graphs G1 and G2. We prove that a linear description of the stable set polytope of G is obtained by properly composing the linear inequalities describing the stable set polytopes of G1, G2 and two other related graphs. We explain how to apply iteratively the 2-clique-bond composition to provide the complete linear description of the stable set polytope of new classes of graphs.

Keywords: stable set polytope, claw-free graphs, homogeneous set

The published paper is available at http://doi.org/10.1016/j.dam.2013.02.022.

Projected Perspective Reformulations With Applications in Design Problems

A. Frangioni, C. Gentile, E. Grande, A. Pacifici

Operations Research 59(5), p. 1225 - 1232, 2011.

Abstract: The Perspective Relaxation (PR) is a general approach for constructing tight approximations to Mixed Integer Non Linear Programs (MINLP) with semicontinuous variables. The PR of a MINLP can be formulated either as a Mixed Integer Second Order Cone Program (provided that the original objective function is SOCP-representable), or as a Semi-Infinite MINLP. In this paper, we show that under some further assumptions (rather restrictive, but satisfied in several practical applications), the PR of a Mixed Integer Quadratic Program can also be reformulated as a piecewise quadratic problem, ultimately yielding a QP relaxation of roughly the same size of the standard continuous relaxation. Furthermore, if the original problem has some exploitable structure, then this structure is typically preserved in the reformulation, thus allowing the construction of specialized approaches for solving the PR. We report on implementing these ideas on two MIQPs with appropriate structure: a sensor placement problem and a quadratic-cost (single-commodity) network design problem.

Keywords: Mixed Integer Non Linear Problems, Semicontinuous Variables, Perspective Relaxation, Sensor Placement Problem, Network Design Problem

The published paper is available at http://dx.doi.org/10.1287/opre.1110.0930. A Technical Report version is available here.

Sequential Lagrangian-MILP approaches for Unit Commitment problems

A. Frangioni, C. Gentile, F. Lacalandra

International Journal of Electrical Power and Energy Systems 33, p. 585 - 593, 2011.

Abstract: The short-term Unit Commitment (UC) problem in hydro-thermal power generation is a fundamental problem in short-term electrical generation scheduling. Historically, Lagrangian techniques have been used to tackle this large-scale, difficult Mixed-Integer NonLinear Program (MINLP); this requires being able to efficiently solve the Lagrangian subproblems, which has only recently become possible (efficiently enough) for units subject to significant ramp constraints. In the last years, alternative approaches have been devised where the nonlinearities in the problem are approximated by means of piecewise-linear functions, so that UC can be approximated by a Mixed-Integer Linear Program (MILP); in particular, using a recently developed class of valid inequalities for the problem, called ``Perspective Cuts'', significant improvements have been obtained in the efficiency and effectiveness of the solution algorithms. These two different approaches have complementary strengths; Lagrangian ones provide very good lower bounds quickly, but they require sophisticated heuristics---which may need to be changed every time that the mathematical model changes---for producing actual feasible solutions. MILP approaches have been shown to be able to provide very good feasible solutions quickly, but their lower bound is significantly worse. We present a sequential approach which combines the two methods, trying to exploit each one's strengths; we show, by means of extensive computational experiments on realistic instances, that the sequential approach may exhibit significantly better efficiency than either of the two basic ones, depending on the degree of accuracy requested to the feasible solutions.

Keywords: OR in energy, Hydro-Thermal Unit Commitment, Mixed-Integer NonLinear Program Formulations, Lagrangian Relaxation.

The published paper is available at http://dx.doi.org/10.1016/j.ijepes.2010.12.013. A Technical Report version is available here.

A Computational Comparison of Reformulations of the Perspective Relaxation: SOCP vs. Cutting Planes

A. Frangioni, C. Gentile

Operations Research Letters 37(3), p. 206 - 210, 2009

Abstract: The Perspective Reformulation is a general approach for constructing tight approximations to MINLP problems with semicontinuous variables. Two different reformulations have been proposed for solving it, one resulting in a Second-Order Cone Program, the other based on representing the perspective function by (an infinite number of) cutting planes. We compare the two reformulations on two sets of MIQPs to determine which one is most effective in the context of exact or approximate Branch-and-Cut algorithms.

Keywords:Mixed-Integer Non Linear Programs, Reformulations, Second-Order Cone Programs, Valid Inequalities, Unit Commitment problem, Portfolio Optimization

The published paper is available at http://dx.doi.org/10.1016/j.orl.2009.02.003. A technical report version is available here.

Gear composition of stable set polytopes and G-perfection

A. Galluccio, C. Gentile, P. Ventura

Mathematics of Operations Research 34, p. 813-836, 2009.

Abstract: Graphs obtained by applying the gear composition to a given graph H are called geared graphs. We show how a linear description of the stable set polytope STAB(G) of a geared graph G can be obtained by extending the linear inequalities defining STAB(H) and STAB(He), where He is the the graph obtained from H by subdividing the edge e. We also introduce the class of G-perfect graphs, i.e., graphs whose stable set polytope is described by: nonnegativity inequalities, rank inequalities, lifted 5-wheel inequalities, and some special inequalities called geared inequalities and g-lifted inequalities. We prove that graphs obtained by repeated applications of the gear composition to a given graph H are G-perfect, provided that any graph obtained from H by subdividing a subset of its simplicial edges is G-perfect. In particular, we show that a large subclass of claw-free graphs is G-perfect, thus providing a partial answer to the well-known problem of finding a defining linear system for the stable set polytope of claw-free graphs.

Keywords: Stable set polytope, Graph composition, Polyhedral combinatorics.

The published paper is available at http://dx.doi.org/10.1287/moor.1090.0407. A technical report version is available here.

Tighter approximated MILP formulations for Unit Commitment Problems

A. Frangioni, C. Gentile, F. Lacalandra

IEEE Transactions on Power Systems 24(1), p. 105 - 113, 2009.

Abstract: The short-term Unit Commitment (UC) problem in hydro-thermal power generation is a large-scale, Mixed-Integer NonLinear Program (MINLP), which is difficult to solve efficiently, especially for large-scale instances. It is possible to approximate the nonlinear objective function of the problem by means of piecewise-linear functions, so that UC can be approximated by a Mixed-Integer Linear Program (MILP); applying the available efficient general-purpose MILP solvers to the resulting formulations, good quality solutions can be obtained in a relatively short amount of time. We build on this approach, presenting a novel way to approximating the nonlinear objective function based on a recently developed class of valid inequalities for the problem, called ``Perspective Cuts''. At least for many realistic instances of a general basic formulation of UC, a MILP-based heuristic obtains comparable or slightly better solutions in less time when employing the new approach rather than the standard piecewise linearizations, while being not more difficult to implement and use. Furthermore, ``dynamic'' formulations, whereby the approximation is iteratively improved, provide even better results if the approximation is appropriately controlled.

Keywords: Hydro-Thermal Unit Commitment, Mixed-Integer Linear Program Formulations, Valid Inequalities.

The published paper is available at http://dx.doi.org/10.1109/TPWRS.2008.20047447. A technical report version is available here.

Gear composition and the Stable Set Polytope

A. Galluccio, C. Gentile, P. Ventura

Operations Research Letters 36, p. 419 - 423, 2008.

Abstract: We present a new graph composition that produces a graph G from a given graph H and a fixed graph B called gear and we study its polyhedral properties. This composition yields counterexamples to a conjecture on the facial structure of STAB(G) when G is claw-free.

Keywords: Stable set polytope, Graph composition, Polyhedral combinatorics.

The published paper is available at http://dx.doi.org/10.1016/j.orl.2008.01.003. A technical report version is available here.

New Lagrangian Heuristics for Ramp-constrained Unit Commitment Problems

A. Frangioni, C. Gentile, F. Lacalandra

Proceedings 19a Mini-EURO Conference in Operational Research Models and Methods in the Energy Sector - ORMMES 2006, Coimbra, Portogallo, 6-8 settembre 2006.

Abstract: Lagrangian Relaxation (LR) algorithms are among the most successful approaches for solving large-scale hydro-thermal Unit Commitment (UC) problems; this is largely due to the fact that the Single-Unit Commitment (1UC) problems resulting from the decomposition can be efficiently solved by Dynamic Programming (DP) techniques. Ramp constraints have historically eluded efficient exact DP approaches; however, this has recently changed [FrG06b]. We show that the newly proposed DP algorithm for ramp-constrained (1UC) problems, together with a new heuristic phase that explicitly takes into account ramp limits on the maximum and minimum available power at each hour, can reliably find good-quality solutions to even large-scale (UC) instances in short time.

Keywords: Hydro-Thermal Unit Commitment, Ramp Limits, Lagrangian Relaxation.

Download (.pdf)

Solving Unit Commitment Problems with General Ramp Contraints

A. Frangioni, C. Gentile, F. Lacalandra

International Journal of Electrical Power and Energy Systems 30, p. 316 - 326, 2008.

Abstract:Lagrangian Relaxation (LR) algorithms are among the most successful approaches for solving large-scale hydro-thermal Unit Commitment (UC) problems; this is largely due to the fact that the Single-Unit Commitment (1UC) problems resulting from the decomposition, incorporating many kinds of technical constraints such as minimum up- and down-time requirements and time-dependent startup costs, can be efficiently solved by Dynamic Programming (DP) techniques. Ramp constraints have historically eluded efficient exact DP approaches; however, this has recently changed [FrG06b]. We show that the newly proposed DP algorithm for ramp-constrained (1UC) problems allows to extend existing LR approaches to ramp-constrained (UC); this is not obvious since the heuristic procedures typically used to recover a primal feasible solution are not easily extended to take into account ramp limits. However, dealing with ramp constraints in the subproblems turns out to be sufficient to provide the LR heuristic enough guidance to produce good feasible solutions even with no other modification of the approach; this is due to the fact that (sophisticated) LR algorithms to (UC) duly exploit the primal information computed by the Lagrangian Dual, which in the proposed approach is ramp feasible.

Keywords: Hydro-Thermal Unit Commitment, Ramp Limits, Lagrangian Relaxation.

The published paper is available at http://dx.doi.org/10.1016/j.ijepes.2007.10.003. A technical report version is available here.

SDP Diagonalizations and Perspective Cuts for a Class of Nonseparable MIQP

A. Frangioni, C. Gentile

Operations Research Letters 35(2), p. 181 - 185, 2007

Abstract: Perspective cuts are a computationally effective family of valid inequalities, belonging to the general family of disjunctive cuts, for Mixed-Integer Convex NonLinear Programming problems with a specific structure. The required structure can be forced upon models that would not originally display it by decomposing the Hessian of the problem into the sum of two positive semidefinite matrices, a generic and a diagonal one, so that the latter is ``as large as possible''. We compare two ways for computing the diagonal matrix: an inexpensive approach requiring a minimum eigenvalue computation and a more costly procedure which require the solution of a SemiDefinite Programming problem. The latter dramatically outperforms the former at least upon instances of the Mean-Variance problem in portfolio optimization.

Keywords:Mixed-Integer Quadratic Programs, Valid Inequalities, SemiDefinite Programming, Portfolio Optimization

The published paper is available at http://dx.doi.org/10.1016/j.orl.2006.03.008. A technical report version is available here.

Prim-based BCT preconditioners for Min-Cost Flow Problems

A. Frangioni, C. Gentile

Computational Optimization and Applications 36(2-3), p. 271 - 287, 2007

Abstract: Subgraph-based preconditioners have been shown to be a valuable tool for the iterative solution, via a Preconditioned Conjugate Gradient method, of the (core part of the) KKT systems that must be solved at each iteration of an Interior Point algorithm for the solution of Min Cost Flow problems. These preconditioners are based on the idea of extracting a proper triangulated subgraph, with ``large'' weight, of the original graph: in practice, trees and Brother-Connected Trees (BCT) of depth two have been shown to be the most computationally efficient families of subgraphs. In the literature, heuristics based on approximate versions of the Kruskal algorithm for the maximum-weight spanning tree have always been used to select the subgraph at each IP iteration. In this article, we propose heuristics based on the Prim algorithm for the maximum-weight spanning tree, showing that they outperform the previously proposed Kruskal-based heuristics on several classes of instances, especially if complemented with a weight-based automatic switching rule for deciding when the BCT preconditioner has to be used.

Keywords: Min Cost Flow problems, Interior Point algorithms, Preconditioned Conjugated Gradient method, Prim algorithm.

The published paper is available at http://dx.doi.org/10.1007/s10589-006-9005-9. A technical report version is available here.

Perspective Cuts for a class of convex 0-1 Mixed Integer Programs

A. Frangioni, C. Gentile

Mathematical Programming 106(2), p. 225 - 236, 2006

Abstract: We show that the convex envelope of the objective function of Mixed-Integer Programming problems with a specific structure is the perspective function of the continuous part of the objective function. Using a characterization of the subdifferential of the perspective function, we derive "perspective cuts", a family of valid inequalities for the problem. Perspective cuts can be shown to belong to the general family of disjunctive cuts, but they do not require the solution of a potentially costly nonlinear programming problem to be separated. Using perspective cuts substantially improves the performance of Branch-and-Cut approaches for at least two models that, either ``naturally'' or after a proper reformulation, have the required structure: the Unit Commitment problem in electrical power production and the Mean-Variance problem in portfolio optimization.

Keywords: Mixed-Integer Programs, Valid Inequalities, Unit Commitment problem, Portfolio Optimization

The published paper is available at http://dx.doi.org/10.1007/s10107-005-0594-3. A technical report version is available here.

Solving nonlinear single-unit commitment problems with ramping constraints

A. Frangioni, C. Gentile

Operations Research 54(4), p. 767 - 775, 2006

Abstract: We present a dynamic programming algorithm for solving the single-Unit Commitment (1UC) problem with ramping constraints and arbitrary convex cost function. The algorithm is based on a new approach for efficiently solving the single-unit Economic Dispatch (ED) problem with ramping constraints and arbitrary convex cost functions, improving on previously known ones that were limited to piecewise-linear functions. For simple convex functions, such as the quadratic ones typically used in applications, the solution cost of all the involved (ED) problems, comprised that of finding an optimal primal and dual solution, is O(n3). Coupled with a ``smart'' visit of the state-space graph in the dynamic programming algorithm, this enables one to solve (1UC) in O(n3) overall.

Keywords: Dynamic Programming, Unit Commitment problem, Ramping constraints

The published paper is available at http://dx.doi.org/10.1287/opre.1060.0309. A technical report version is available here.

Experiments with a hybrid interior point/combinatorial approach for network flow problems

A. Frangioni, C. Gentile

Optimization Methods & Software 22(4), p. 573 - 585, 2007

Abstract: Interior Point (IP) algorithms for Min Cost Flow (MCF) problems have been shown to be competitive with combinatorial approaches, at least on some problem classes and for very large instances. This is in part due to availability of specialized crossover routines for MCF; these allow early termination of the IP approach, sparing it with the final iterations where the KKT systems become more difficult to solve. As the crossover procedures are nothing but combinatorial approaches to MCF that are only allowed to perform few iterations, the IP algorithm can be seen as a complex "multiple crash start" routine for the combinatorial ones. We report our experiments about allowing one primal-dual combinatorial algorithm to MCF to perform as many iterations as required to solve the problem after being warm-started by an IP approach. Our results show that the efficiency of the combined approach critically depends on the accurate selection of a set of parameters among very many possible ones, for which designing accurate guidelines appears not to be an easy task; however, they also show that the combined approach can be competitive with the original combinatorial algorithm, at least on some "difficult" instances.

Keywords: Min Cost Flow problems, Interior Point algorithms, Relaxation Method, Crossover.

The published paper is available at http://dx.doi.org/10.1080/00207160600848017. A technical report version is available here.

New Preconditioners for KKT Systems of Network Flow Problems

A. Frangioni, C. Gentile

SIAM Journal on Optimization 14(3), p. 894 - 913, 2004

Abstract: We propose a new set of preconditioners for the iterative solution, via a Preconditioned Conjugate Gradient (PCG) method, of the KKT systems that must be solved at each iteration of an Interior Point (IP) algorithm for the solution of linear Min Cost Flow (MCF) problems. These preconditioners are based on the idea of extracting a proper triangulated subgraph of the original graph which strictly contains a spanning tree. We define a new class of triangulated graphs, called Brother-Connected Trees (BCT), and discuss some fast heuristics for finding BCTs of ``large'' weight. Computational experience shows that the new preconditioners can complement tree preconditioners, outperforming them both in iterations count and in running time on some classes of graphs.

Keywords: Min Cost Flow problems, Interior Point algorithms, Preconditioned Conjugated Gradient method, Triangulated Graphs.

The published paper is available at http://dx.doi.org/10.1137/S105262340240519X. Due to the provisions of SIAM Copyright Assignment Agreement, it can also be downloaded here.

Mod-2 cuts generation yields the convex hull of bounded integer feasible sets

C. Gentile, P. Ventura, R. Weismantel

SIAM Journal on Discrete Mathematics 20(4), p. 913 - 919 , 2006

Abstract: This paper focuses on the outer description of the convex hull of all integer solutions to a given system of linear inequalities. It is shown that if the given system contains lower and upper bounds for the variables, then the convex hull can be produced by iteratively generating so-called mod-2 cuts only. This fact is surprising and might even be counterintuitive, since many integer rounding cuts exist that are not mod-2, i.e., representable as the zero- one-half combination of the given constraint system. The key, however, is that in general many more rounds of mod-2 cut generation are necessary to produce the final description compared to the traditional integer rounding procedure.

Keywords:Integer Programming, Mod-2 cuts, Convex Hull.

The published paper is available at http://dx.doi.org/10.1137/04061831X. A technical report version is available here.

A Polyhedral Approach for the Staff Rostering Problem

G. Felici, C. Gentile

Management Science 50(3), p. 381-393, 2004

Abstract: In this paper Staff Scheduling Problems for large organizations that provide continuous services to customers are formulated and efficiently solved. We describe an Integer Programming approach for a class of such problems, where solutions have to obey a number of constraints related to workload balancing, shift compatibility, and distribution of days off. The formulation of the constraints is general and can be extended to different personnel management problems where staff members have to cover shifts and a fixed number of rests per week is to be assigned. The model maximizes staff satisfaction, expressed by positive weights for pairs of shifts in consecutive days. We consider the associated polytope and study its structure, determining some classes of inequalities that are facet-inducing for special subproblems and other valid classes. We also identify a particular subproblem whose solution can be used to determine strong cuts for the complete problem. In addition, we design special branching rules that break the symmetries that arise in the solution space and have a large impact in the efficiency of the method. The validity of this approach has been ascertained by extensive computational tests; moreover, the method has been implemented by the OR Department of an airline company, where it is used to solve ground staff management problems.

Keywords:Manpower planning,Rostering, Integer Programming, Cutting plane/facet defining inequalities.

The published paper is available at http://dx.doi.org/10.1287/mnsc.1030.0142. A technical report version is available here.

On the Way to Perfection: Primal Operations for Stable Sets in Graphs

C. Gentile, U.-U. Haus, M. Köppe, G. Rinaldi, R. Weismantel

The Sharpest Cut: The Impact of Manfred Padberg and His Work M. Götschel ed., MPS-SIAM Series in Optimization 4, Chapter 6, p. 51-76, 2004

Abstract: In this paper some operations are described that transform every graph into a perfect graph by replacing nodes with sets of new nodes. The transformation is done in such a way that every stable set in the perfect graph corresponds to a stable set in the original graph. These operations can be used in an augmentation procedure for finding a maximum weighted stable set in a graph. Starting with a stable set in a given graph one defines a simplex type tableau whose associated basic feasible solution is the incidence vector of the stable set. In an iterative fashion, nonbasic columns that would lead to pivoting into nonintegral basic feasible solutions, are replaced by new columns that one can read off from special graph structures such as odd holes, odd antiholes, and various generalizations. Eventually, either a pivot leading to an integral basic feasible solution is performed, or the optimality of the current solution is proved.

Keywords:Stable set problem, perfect graphs, primal integer programming.

The published paper is available at http://dx.doi.org/10.1137/1.9780898718805.ch6. A technical report version is available here.

Zero-lifting for Integer Block Structured Problems

G. Felici, C. Gentile

Journal of Combinatorial Optimization 7(2), p. 161-167, 2003

Abstract: This paper deals with the relations between the polyhedron described by the inequalities of a block structured problem and the polyhedra described by the inequalities of the single blocks. In particular, classes of block structured problems are described for which zero-lifting of facet inducing inequalities of a single block yields facet inducing inequalities for the whole problem. Some applications are discussed.

Keywords:Integer Programming, block structured problems, lifting procedures

The published paper is available at http://dx.doi.org/10.1023/A:1024423013607.

Max Horn SAT and the Minimum Cut Problem in Directed Hypergraphs

G. Gallo, C. Gentile, D. Pretolani, G. Rago

Mathematical Programming 80(2), p.213-237, 1998

Abstract: In this paper we consider the Maximum Horn Satisfiability problem, which is reduced to the problem of finding a minimum cardinality cut on a directed hypergraph. For the latter problem, we propose different IP formulations, related to three different definitions of hyperpath weight. We investigate the properties of their linear relaxations, showing that they define a hierarchy. The weakest relaxation is shown to be equivalent to the relaxation of a well known IP formulation of Max Horn SAT, and to a max-flow problem on hypergraphs. The tightest relaxation, which is a disjunctive programming problem, is shown to have integer optimum. The intermediate relaxation consists in a set covering problem with a possible exponential number of constraints. This latter relaxation provides an approximation of the convex hull of the integer solutions which, as proven by the experimental results given, is much tighter than the one known in the literature.

Keywords:Maximum satisfiability, Horn clauses, Directed hypergraphs, Minimum cut, Generalized set covering

The published paper is available at http://dx.doi.org/10.1007/BF01581727.