IRIS Università degli Studi di Bolognahttps://cris.unibo.itIl sistema di repository digitale IRIS acquisisce, archivia, indicizza, conserva e rende accessibili prodotti digitali della ricerca.Tue, 22 Jun 2021 20:48:38 GMT2021-06-22T20:48:38Z101431Performance Variability in Mixed-Integer Programminghttp://hdl.handle.net/11585/281318Titolo: Performance Variability in Mixed-Integer Programming
Abstract: The performance of mixed-integer programming solvers is subject to some unexpected variability that appears, for example, when changing from one computing platform to another, when permuting rows and/or columns of a model, when adding seemingly neutral changes to the solution process, etc. This phenomenon has been observed for decades, but only recently has it started to be methodologically analyzed with the two possible aims of either reducing or exploiting it, ideally both. In this tutorial we discuss the roots of performance variability, we provide useful tips to recognize it, and we point out some severe misinterpretations that might be generated by not performing/analyzing benchmark results carefully. Finally, we report on the most recent attempts to gain from variability.
Tue, 01 Jan 2013 00:00:00 GMThttp://hdl.handle.net/11585/2813182013-01-01T00:00:00ZPiecewise linear approximation of functions of two variables in MILP modelshttp://hdl.handle.net/11585/78272Titolo: Piecewise linear approximation of functions of two variables in MILP models
Abstract: In recent years, the increased efficiency of mixed integer linear programming (MILP) software tools has encouraged their use also in the solution of non-linear problems, bringing to the need for efficient techniques to linearize non-linear functions of one or more variables. The standard methodologies consist in the piecewise linear approximation of such functions. We consider three easy-to-implement methods for the piecewise linear approximation of functions of two variables. We experimentally evaluate their approximation quality, and give a detailed description of how the methods can be embedded in a MILP model. The advantages and drawbacks of the three methods are discussed on numerical examples.
Fri, 01 Jan 2010 00:00:00 GMThttp://hdl.handle.net/11585/782722010-01-01T00:00:00ZAn MILP Approach for Short-Term Hydro Scheduling and Unit Commitment With Head-Dependent Reservoirhttp://hdl.handle.net/11585/62525Titolo: An MILP Approach for Short-Term Hydro Scheduling and Unit Commitment With Head-Dependent Reservoir
Abstract: The paper deals with a unit commitment problem of
a generation company whose aim is to find the optimal scheduling
of a multiunit pump-storage hydro power station, for a short term
period in which the electricity prices are forecasted. The problem
has a mixed-integer nonlinear structure, which makes very hard
to handle the corresponding mathematical models. However,
modern mixed-integer linear programming (MILP) software
tools have reached a high efficiency, both in terms of solution
accuracy and computing time. Hence we introduce MILP models
of increasing complexity, which allow to accurately represent most
of the hydroelectric system characteristics, and turn out to be
computationally solvable. In particular we present a model that
takes into account the head effects on power production through
an enhanced linearization technique, and turns out to be more
general and efficient than those available in the literature. The
practical behavior of the models is analyzed through computational
experiments on real-world data.
Tue, 01 Jan 2008 00:00:00 GMThttp://hdl.handle.net/11585/625252008-01-01T00:00:00ZCP-based Local Branchinghttp://hdl.handle.net/11585/64039Titolo: CP-based Local Branching
Abstract: We propose the integration and extension of the local branching
search strategy in Constraint Programming (CP). Local branching
is a general purpose heuristic method which searches locally around the best known solution by employing tree search. It has been successfully used in MIP where local branching constraints are used to model the neighborhood of an incumbent solution and improve the bound. The integration of local branching in CP is not simply a matter of implementation, but requires a number of significant extensions (concerning the computation of the bound, cost-based filtering of the branching constraints, diversification, variable neighbourhood width and search heuristics) and can greatly benefit from the CP environment. In this paper, we discuss how such extensions are possible and provide some experimental
results to demonstrate the practical value of local branching in CP.
Mon, 01 Jan 2007 00:00:00 GMThttp://hdl.handle.net/11585/640392007-01-01T00:00:00ZPartial enumeration algorithms for Two-Dimensional Bin Packing Problem with guillotine constraintshttp://hdl.handle.net/11585/585869Titolo: Partial enumeration algorithms for Two-Dimensional Bin Packing Problem with guillotine constraints
Sun, 01 Jan 2017 00:00:00 GMThttp://hdl.handle.net/11585/5858692017-01-01T00:00:00ZOptimizing the Design of Water Distribution Networks Using Mathematical OptimizationCase Studies in Operations Researchhttp://hdl.handle.net/11585/397190Titolo: Optimizing the Design of Water Distribution Networks Using Mathematical OptimizationCase Studies in Operations Research
Abstract: Decaying infrastructure in municipalities is becoming a problem of
increasing importance as growing populations put increasing stress on all service systems. In tough economic times, renewing and maintaining infrastructure has become increasingly difficult. As an example, many municipal water networks were installed several decades ago and were designed to handle much smaller demand and additionally have decayed due to age. This chapter discusses an efficient approach for the problem of replacing all the pipes using the same network topology, at minimum cost, to achieve current pressure demands at junctions of the network.
Thu, 01 Jan 2015 00:00:00 GMThttp://hdl.handle.net/11585/3971902015-01-01T00:00:00ZJust MIP it!http://hdl.handle.net/11585/74179Titolo: Just MIP it!
Abstract: Modern Mixed-Integer Programming (MIP) solvers exploit a rich arsenal of tools to attack hard problems. It is widely accepted by the OR community that the solution of very hard MIPs can take advantage from the solution of a series of time-consuming auxiliary Linear Programs (LPs) intended to enhance the performance of the overall MIP solver. E.g., auxiliary LPs may be solved to generate powerful disjunctive cuts, or to implement a strong branching policy.
Also well established is the fact that finding good-quality heuristic MIP solutions often requires a computing time that is just comparable to that needed to solve the LP relaxations.
So, it makes sense to think of a new generation of MIP solvers where auxiliary MIPs (as opposed to LPs) are heuristically solved on the fly, with the aim of bringing the MIP technology under the chest of the MIP solver itself. This leads to the idea of "translating
into a MIP model" (MIPping) some crucial decisions to be taken within a MIP algorithm (How to cut? How to improve the incumbent solution? Is the current node dominated?).
In this paper we survey a number of successful applications of the above approach.
Thu, 01 Jan 2009 00:00:00 GMThttp://hdl.handle.net/11585/741792009-01-01T00:00:00ZAn Effective Branch-and-Bound Algorithm for Convex Quadratic Integer Programminghttp://hdl.handle.net/11585/99288Titolo: An Effective Branch-and-Bound Algorithm for Convex Quadratic Integer Programming
Abstract: We present a branch-and-bound algorithm for minimizing a convex quadratic objective function over integer variables subject to convex constraints. In a given node of the enumeration tree, corresponding to the fixing of a subset of the variables, a lower bound is given by the continuous minimum of the restricted objective function. We improve this bound by exploiting the integrality of the variables using suitably-defined lattice-free ellipsoids. Experiments show that our approach is very fast on both unconstrained problems and problems with box constraints. The main reason is that all expensive calculations can be done in a preprocessing phase, while a single node in the enumeration tree can be processed in linear time in the problem dimension.
Fri, 01 Jan 2010 00:00:00 GMThttp://hdl.handle.net/11585/992882010-01-01T00:00:00ZOptimahttp://hdl.handle.net/11585/73016Titolo: Optima
Abstract: This is the newsletter of the Mathematical Programming Society
Thu, 01 Jan 2009 00:00:00 GMThttp://hdl.handle.net/11585/730162009-01-01T00:00:00ZCombinatorial Traveling Salesman Problem Algorithmshttp://hdl.handle.net/11585/85425Titolo: Combinatorial Traveling Salesman Problem Algorithms
Abstract: Given a set of cities, and the cost of traveling between each pair
of them, the Traveling Salesman Problem, TSP for short,
calls for finding a unique tour visiting all cities at minimum
cost. Besides being for sure the best known combinatorial
optimization problem, the TSP has many applications, not only in
Operations Research/Management Science (especially in
transportation and logistics), but also in many other fields, such
as genome sequencing or drilling of printed circuits boards.
We review some of the TSP ancestors, including the famous Hamiltonian cycle problem, of which the TSP is the weighted version. We examine the most famous formulations for both symmetric and asymmetric TSP, and the main combinatorial approaches for its solution.
Sat, 01 Jan 2011 00:00:00 GMThttp://hdl.handle.net/11585/854252011-01-01T00:00:00Z