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.Sun, 29 Nov 2020 02:01:54 GMT2020-11-29T02:01:54Z101371Repairing MIP Infeasibility through Local Branchinghttp://hdl.handle.net/11585/31054Titolo: Repairing MIP Infeasibility through Local Branching
Mon, 01 Jan 2007 00:00:00 GMThttp://hdl.handle.net/11585/310542007-01-01T00:00:00ZOptimistic MILP modeling of non-linear optimization problemshttp://hdl.handle.net/11585/281317Titolo: Optimistic MILP modeling of non-linear optimization problems
Abstract: We present a new piecewise linear approximation of non-linear optimization problems. It can be seen as a variant of classical triangulations that leaves more degrees of freedom to define any point as a convex combination of the samples. We show theoretical properties of the approximating functions, and provide computational evidence of the impact of their use within MILP models approximating non-linear problems.
Wed, 01 Jan 2014 00:00:00 GMThttp://hdl.handle.net/11585/2813172014-01-01T00:00:00ZSingle-commodity Robust Network Design Problem: Complexity, Instances and Heuristic Solutionshttp://hdl.handle.net/11585/281311Titolo: Single-commodity Robust Network Design Problem: Complexity, Instances and Heuristic Solutions
Abstract: We study a single-commodity Robust Network Design problem (RND) in which an undirected graph with edge costs is given together with a discrete set of balance matrices, representing different supply/demand scenarios. In each scenario, a subset of the nodes is exchanging flow. The goal is to determine the minimum cost installation of capacities on the edges such that the flow exchange is feasible for every scenario. Previously conducted computational investigations on the problem motivated the study of the complexity of some special cases and we present complexity results on them, including hypercubes. In turn, these results lead to the definition of new instances (random graphs with {1, 0, 1} balances) that are computationally hard for the natural flow formulation. These instances are then solved by means of a new heuristic algorithm for RND, which consists of three phases. In the first phase the graph representing the network is reduced by heuristically deleting a subset of the arcs, and a feasible solution is built. The second phase consists of a neighborhood search on the reduced graph based on a Mixed-Integer (Linear) Programming (MIP) flow model. Finally, the third phase applies a proximity search approach to further improve the solution, taking into account the original graph. The heuristic is tested on the new instances, and the comparison with the solutions obtained by Cplex on a natural flow formulation shows the effectiveness of the proposed method.
Wed, 01 Jan 2014 00:00:00 GMThttp://hdl.handle.net/11585/2813112014-01-01T00:00:00ZMathematical Programming techniques in Water Network Optimizationhttp://hdl.handle.net/11585/407567Titolo: Mathematical Programming techniques in Water Network Optimization
Abstract: In this article we survey mathematical programming approaches to problems in the field of drinking water distribution network optimization. Among the predominant topics treated in the literature, we focus on two different, but related problem classes. One can be described by the notion of network design, while the other is more aptly termed by network operation. The basic underlying model in both cases is a nonlinear network flow model, and we give an overview on the more specific modeling aspects in each case. The overall mathematical model is a Mixed Integer Nonlinear Program having a common structure with respect to how water dynamics in pipes are described. Finally, we survey the algorithmic approaches to solve the proposed problems and we discuss computation on various types of water networks.
Thu, 01 Jan 2015 00:00:00 GMThttp://hdl.handle.net/11585/4075672015-01-01T00:00:00ZOn the integration of Metaheuristic strategies in Constraint Programminghttp://hdl.handle.net/11585/17412Titolo: On the integration of Metaheuristic strategies in Constraint Programming
Thu, 01 Jan 2004 00:00:00 GMThttp://hdl.handle.net/11585/174122004-01-01T00:00:00ZOptimizing over the first Chvatal closurehttp://hdl.handle.net/11585/17425Titolo: Optimizing over the first Chvatal closure
Sat, 01 Jan 2005 00:00:00 GMThttp://hdl.handle.net/11585/174252005-01-01T00:00:00ZOn the Practical Strength of Two-Row Tableau Cutshttp://hdl.handle.net/11585/281312Titolo: On the Practical Strength of Two-Row Tableau Cuts
Abstract: Following the flurry of recent theoretical work on cutting planes from two-row mixed integer group relax- ations of a linear programming tableau, we report on computational tests to evaluate the strength of two-row cuts based on lattice-free triangles having more than one integer point on one side. A heuristic procedure to generate such triangles (referred to in the literature as “type 2” triangles) is presented, and then the coefficients of the integer variables are tightened by lifting. To test the effectiveness of triangle cuts, we compare the gap closed using Gomory mixed integer cuts for one round, the gap closed in one round using all the triangle cuts generated by our heuristic, and the gap closed by a small number of two-row split cuts. Our tests are carried out on randomly generated instances designed to represent different problem features by varying the number of integer nonbasic variables, bounds, nonnegativity constraints, and density, as well as on the classical MIPLIB instances. The outcome of this computational analysis is some insight into key characteristics of MIP instances whose presence makes two-row triangle cuts computationally effective. In particular, it appears to be necessary that the tableau row pairs are dense, and more subjectively that the nonbasic continuous variables are “important.” Unfortunately these characteristics seem to be rarely present among real-life instances, and more specifically the tableau rows of the MIPLIB instances are far from dense.
Wed, 01 Jan 2014 00:00:00 GMThttp://hdl.handle.net/11585/2813122014-01-01T00:00:00ZPolynomial-Time Separation of a Superclass of Simple Comb Inequalitieshttp://hdl.handle.net/11585/25654Titolo: Polynomial-Time Separation of a Superclass of Simple Comb Inequalities
Sun, 01 Jan 2006 00:00:00 GMThttp://hdl.handle.net/11585/256542006-01-01T00:00:00ZA Feasibility Pump for Mixed Integer Nonlinear Programshttp://hdl.handle.net/11585/57379Titolo: A Feasibility Pump for Mixed Integer Nonlinear Programs
Thu, 01 Jan 2009 00:00:00 GMThttp://hdl.handle.net/11585/573792009-01-01T00:00:00ZA reconfigurable heterogeneous multiprocessor System on Chiphttp://hdl.handle.net/11585/30033Titolo: A reconfigurable heterogeneous multiprocessor System on Chip
Sun, 01 Jan 2006 00:00:00 GMThttp://hdl.handle.net/11585/300332006-01-01T00:00:00Z