共查询到20条相似文献,搜索用时 31 毫秒
1.
Andrea Tramontani 《4OR: A Quarterly Journal of Operations Research》2011,9(3):325-328
This is a summary of the author’s PhD thesis supervised by Andrea Lodi and Paolo Toth and defended on 16 April 2009 at the
Università di Bologna. The thesis is written in English and is available from the author upon request. This work is focused
on Mixed Integer Programming (MIP). In particular, the first part of the thesis deals with general purpose cutting planes,
which are probably the key ingredient behind the success of the current generation of MIP solvers. The second part is instead
focused on the heuristic and exact exploitation of integer programming techniques for hard combinatorial optimization problems
in the context of routing applications. 相似文献
2.
In hybrid solvers for combinatorial optimisation, combining Constraint (Logic) Programming (CLP) and Mixed Integer Programming (MIP), it is important to have tight connections between the two domains. We extend and generalise previous work on automatic linearisations and propagation of symbolic CLP constraints that cross the boundary between CLP and MIP. We also present how reduced costs from the linear programming relaxation can be used for domain reduction on the CLP side. Computational results comparing our hybrid approach with pure CLP and MIP on a configuration problem show significant speed-ups. 相似文献
3.
In modern MIP solvers, primal heuristics play a key role in finding high-quality solutions. However, classical performance measures reflect the impact of primal heuristics on the overall solving process badly. In this article, we introduce a new performance measure, the “primal integral”, which depends on the quality of solutions and on the time when they are found. We compare five state-of-the-art MIP solvers w.r.t. the newly proposed measure, and show that heuristics improve their performance by up to 80%. 相似文献
4.
University course timetabling covers the task of assigning rooms and time periods to courses while ensuring a minimum violation of soft constraints that define the quality of the timetable. These soft constraints can have attributes that make it difficult for mixed-integer programming solvers to find good solutions fast enough to be used in a practical setting. Therefore, metaheuristics have dominated this area despite the fact that mixed-integer programming solvers have improved tremendously over the last decade. This paper presents a matheuristic where the MIP-solver is guided to find good feasible solutions faster. This makes the matheuristic applicable in practical settings, where mixed-integer programming solvers do not perform well. To the best of our knowledge this is the first matheuristic presented for the University Course Timetabling problem. The matheuristic works as a large neighborhood search where the MIP solver is used to explore a part of the solution space in each iteration. The matheuristic uses problem specific knowledge to fix a number of variables and create smaller problems for the solver to work on, and thereby iteratively improves the solution. Thus we are able to solve very large instances and retrieve good solutions within reasonable time limits. The presented framework is easily extendable due to the flexibility of modeling with MIPs; new constraints and objectives can be added without the need to alter the algorithm itself. At the same time, the matheuristic will benefit from future improvements of MIP solvers. The matheuristic is benchmarked on instances from the literature and the 2nd International Timetabling Competition (ITC2007). Our algorithm gives better solutions than running a state-of-the-art MIP solver directly on the model, especially on larger and more constrained instances. Compared to the winner of ITC2007, the matheuristic performs better. However, the most recent state-of-the-art metaheuristics outperform the matheuristic. 相似文献
5.
Kai Zhou Mustafa R. Kılınç Xi Chen Nikolaos V. Sahinidis 《Journal of Global Optimization》2018,70(3):497-516
Solving mixed-integer nonlinear programming (MINLP) problems to optimality is a NP-hard problem, for which many deterministic global optimization algorithms and solvers have been recently developed. MINLPs can be relaxed in various ways, including via mixed-integer linear programming (MIP), nonlinear programming, and linear programming. There is a tradeoff between the quality of the bounds and CPU time requirements of these relaxations. Unfortunately, these tradeoffs are problem-dependent and cannot be predicted beforehand. This paper proposes a new dynamic strategy for activating and deactivating MIP relaxations in various stages of a branch-and-bound algorithm. The primary contribution of the proposed strategy is that it does not use meta-parameters, thus avoiding parameter tuning. Additionally, this paper proposes a strategy that capitalizes on the availability of parallel MIP solver technology to exploit multicore computing hardware while solving MINLPs. Computational tests for various benchmark libraries reveal that our MIP activation strategy works efficiently in single-core and multicore environments. 相似文献
6.
Josef Kallrath 《Optimization Letters》2011,5(3):453-466
Based on the Greek term monolithos (stone consisting of one single block) Kallrath (Comput Chem Eng 33:1983–1993, 2009) introduced the term polylithic for modeling and solution approaches in which mixed integer or non-convex nonlinear optimization problems are solved by tailor-made
methods involving several models and/or algorithmic components, in which the solution of one model is input to another one.
This can be exploited to initialize certain variables, or to provide bounds on them (problem-specific preprocessing). Mathematical
examples of polylithic approaches are decomposition techniques, or hybrid methods in which constructive heuristics and local
search improvement methods are coupled with exact MIP algorithms. Tailor-made polylithic solution approaches with thousands
or millions of solve statements are challenges on algebraic modeling languages. Local objects and procedural structures are
almost necessary. Warm-start and hot-start techniques can be essential. The effort of developing complex tailor-made polylithic
solutions is awarded by enabling us to solve real-world problems far beyond the limits of monolithic approaches and general
purpose solvers. 相似文献
7.
Mathematical Programming - A key ingredient in branch and bound (B&B) solvers for mixed-integer programming (MIP) is the selection of branching variables since poor or arbitrary selection... 相似文献
8.
Tobias Achterberg 《Mathematical Programming Computation》2009,1(1):1-41
Constraint integer programming (CIP) is a novel paradigm which integrates constraint programming (CP), mixed integer programming (MIP), and satisfiability (SAT) modeling and solving techniques. In this paper we discuss the software framework and solver SCIP (Solving Constraint
Integer Programs), which is free for academic and non-commercial use and can be downloaded in source code. This paper gives
an overview of the main design concepts of SCIP and how it can be used to solve constraint integer programs. To illustrate
the performance and flexibility of SCIP, we apply it to two different problem classes. First, we consider mixed integer programming
and show by computational experiments that SCIP is almost competitive to specialized commercial MIP solvers, even though SCIP
supports the more general constraint integer programming paradigm. We develop new ingredients that improve current MIP solving
technology. As a second application, we employ SCIP to solve chip design verification problems as they arise in the logic
design of integrated circuits. This application goes far beyond traditional MIP solving, as it includes several highly non-linear
constraints, which can be handled nicely within the constraint integer programming framework. We show anecdotally how the
different solving techniques from MIP, CP, and SAT work together inside SCIP to deal with such constraint classes. Finally,
experimental results show that our approach outperforms current state-of-the-art techniques for proving the validity of properties
on circuits containing arithmetic.
相似文献
9.
Dmytro Matsypura Oleg A. Prokopyev Aizat Zahar 《European Journal of Operational Research》2018,264(2):774-796
Wildfires are a common phenomenon on most continents. They have occurred for an estimated 60 million years and are part of a regular climatic cycle. Nevertheless, wildfires represent a real and continuing problem that can have a major impact on people, wildlife and the environment. The intensity and severity of wildfires can be reduced through fuel management activities. The most common and effective fuel management activity is prescribed burning. We propose a multi-period optimization framework based on mixed integer programming (MIP) techniques to determine the optimal spatial allocation of prescribed burning activities over a finite planning horizon. In contrast to the existing fuel management optimization literature, we model fuel accumulation with Olson’s equation. To capture potential fire spread along with irregular landscape connectivity considerations, we use a graph-theoretical approach that allows us to exploit graph connectivity measures (e.g., the number of connected components) as optimization objectives. The resulting mathematical programs can be tackled by general purpose MIP solvers, while for handling larger instances we propose a simple heuristic. Our computational experiments with test instances constructed based on real-life data reveal interesting insights and demonstrate the advantages and limitations of the proposed approaches. 相似文献
10.
Silvia Bonettini Emanuele Galligani Valeria Ruggiero 《Computational Optimization and Applications》2007,37(1):1-34
This paper deals with the solution of nonlinear programming problems arising from elliptic control problems by an interior
point scheme. At each step of the scheme, we have to solve a large scale symmetric and indefinite system; inner iterative
solvers, with an adaptive stopping rule, can be used in order to avoid unnecessary inner iterations, especially when the current
outer iterate is far from the solution.
In this work, we analyse the method of multipliers and the preconditioned conjugate gradient method as inner solvers for interior
point schemes. We discuss the convergence of the whole approach, the implementation details and report the results of numerical
experimentation on a set of large scale test problems arising from the discretization of elliptic control problems. A comparison
with other interior point codes is also reported.
This research was supported by the Italian Ministry for Education, University and Research (MIUR) projects: FIRB Project:
“Parallel Nonlinear Numerical Optimization PN
2
O” (grant n. RBAU01JYPN, ) and COFIN/PRIN04 Project “Numerical Methods and Mathematical Software for Applications” (grant n. 2004012559, ). 相似文献
11.
In this note new Rosenbrock methods for ODEs, DAEs, PDEs and PDAEs of index 1 are presented. These solvers are of order 3,
have 3 or 4 internal stages, and fulfil certain order conditions to obtain a better convergence if inexact Jacobians and approximations
of
are used. A comparison with other Rosenbrock solvers shows the advantages of the new methods.
AMS subject classification (2000) 34A09, 65L80 相似文献
12.
Edward Tsang John Ford Patrick Mills Richard Bradwell Richard Williams Paul Scott 《Annals of Operations Research》2007,155(1):257-277
The profitability and morale of many organizations (such as factories, hospitals and airlines) are affected by their ability
to schedule their personnel properly. Sophisticated and powerful constraint solvers such as ILOG, CHIP, ECLiPSe, etc. have
been demonstrated to be extremely effective on scheduling. Unfortunately, they require non-trivial expertise to use. This
paper describes ZDC-rostering, a constraint-based tool for personnel scheduling that addresses the software crisis and fills
a void in the space of solvers. ZDC-rostering is easier to use than the above constraint-based solvers and more effective
than Microsoft’s Excel Solver. ZDC-rostering is based on an open-source computer-aided constraint programming package called
ZDC, which decouples problem formulation (or modelling) from solution generation in constraint satisfaction. ZDC is equipped
with a set of constraint algorithms, including Extended Guided Local Search, whose efficiency and effectiveness have been
demonstrated in a wide range of applications. Our experiments show that ZDC-rostering is capable of solving realistic-sized
and very tightly-constrained problems efficiently. ZDC-rostering demonstrates the feasibility of applying constraint satisfaction
techniques to solving rostering problems, without having to acquire deep knowledge in constraint technology. 相似文献
13.
C. Beltran-Royo J.-P. Vial A. Alonso-Ayuso 《Computational Optimization and Applications》2012,51(1):387-409
We show how the performance of general purpose Mixed Integer Programming (MIP) solvers, can be enhanced by using the Semi-Lagrangian
Relaxation (SLR) method. To illustrate this procedure we perform computational experiments on large-scale instances of the
Uncapacitated Facility Location (UFL) problems with unknown optimal values. CPLEX solves 3 out of the 36 instances. By combining CPLEX with SLR, we manage to solve 18 out of the 36
instances and improve the best known lower bound for the other instances. The key point has been that, on average, the SLR
approach, has reduced by more than 90% the total number of relevant UFL variables. 相似文献
14.
This paper presents the application of simulated annealing (SA), Tabu search (TS) and hybrid TS–SA to solve a real-world mining optimisation problem called open pit block sequencing (OPBS). The OPBS seeks the optimum extraction sequences under a variety of geological and technical constraints over short-term horizons. As industry-scale OPBS instances are intractable for standard mixed integer programming (MIP) solvers, SA, TS and hybrid TS–SA are developed to solve the OPBS problem. MIP exact solution is also combined with the proposed metaheuristics to polish solutions in feasible neighbourhood moves. Extensive sensitivity analysis is conducted to analyse the characteristics and determine the optimum sets of values of the proposed metaheuristics algorithms’ parameters. Computational experiments show that the proposed algorithms are satisfactory for solving the OPBS problem. Additionally, this comparative study shows that the hybrid TS–SA is superior to SA or TS in solving the OPBS problem in several aspects. 相似文献
15.
This paper investigates the computational tractability of aircraft sequencing problems over multiple runways under mixed mode operations, contrasting an enhanced mixed-integer programme (MIP) and an accelerated column generation approach. First, we examine the benefit of augmenting a base MIP with valid inequalities, preprocessing routines, and symmetry-defeating hierarchical constraints in order to improve the performance of branch-and-bound (B&B)/cut techniques as implemented in commercial solvers. Second, we alternatively reformulate the problem as a set partitioning model that prompts the development of a specialized column generation approach. The latter is accelerated by incorporating an interior point dual stabilization scheme and a complementary column generation routine. Empirical results using a set of new, computationally challenging instances and classical instances in the OR Library reveal the potential and limitations of the two methodologies. 相似文献
16.
Quadratic Spline Collocation (QSC) methods of optimal order of convergence have been recently developed for the solution of elliptic Partial Differential Equations (PDEs). In this paper, linear solvers based on Fast Fourier Transforms (FFT)are developed for the solution of the QSC equations. The complexity of the FFT solvers is O(N
2 log N), where N is the gridsize in one dimension. These direct solvers can handle PDEs with coefficients in one variable or constant, and Dirichlet, Neumann, alternating Dirichlet-Neumann or periodic boundary conditions, along at least one direction of a rectangular domain. General variable coefficient PDEs are handled by preconditioned iterative solvers. The preconditioner is the QSC matrix arising from a constant coefficient PDE. The convergence analysis of the preconditioner is presented. It is shown that, under certain conditions, the convergence rate is independent of the gridsize. The preconditioner is solved by FFT techniques, and integrated with one-step or acceleration methods, giving rise to asymptotically almost optimal linear solvers, with complexity O(N
2 log N). Numerical experiments verify the effectiveness of the solvers and preconditioners, even on problems more general than the analysis assumes. The development and analysis of FFT solvers and preconditioners is extended to QSC equations corresponding to systems of elliptic PDEs. 相似文献
17.
The authors have developed a Taylor series method for solving numerically an initial-value problem differential-algebraic
equation (DAE) that can be of high index, high order, nonlinear, and fully implicit, BIT, 45 (2005), pp. 561–592. Numerical
results have shown that this method is efficient and very accurate. Moreover, it is particularly suitable for problems that
are of too high an index for present DAE solvers.
This paper develops an effective method for computing a DAE’s System Jacobian, which is needed in the structural analysis
of the DAE and computation of Taylor coefficients. Our method involves preprocessing of the DAE and code generation employing
automatic differentiation. Theory and algorithms for preprocessing and code generation are presented.
An operator-overloading approach to computing the System Jacobian is also discussed.
AMS subject classification (2000) 34A09, 65L80, 65L05, 41A58 相似文献
18.
Marco Chiarandini Luca Di Gaspero Stefano Gualandi Andrea Schaerf 《Journal of Heuristics》2012,18(1):119-148
The Balanced Academic Curriculum Problem (BACP) consists in assigning courses to teaching terms satisfying prerequisites and
balancing the credit course load within each term. The BACP is part of the CSPLib with three benchmark instances, but its
formulation is simpler than the problem solved in practice by universities. In this article, we introduce a generalized version
of the problem that takes different curricula and professor preferences into account, and we provide a set of real-life problem
instances arisen at University of Udine. Since the existing formulation based on a min–max objective function does not balance
effectively the credit load for the new instances, we also propose alternative objective functions. Whereas all the CSPLib
instances are efficiently solved with Integer Linear Programming (ILP) state-of-the-art solvers, our new set of real-life
instances turns out to be much more challenging and still intractable for ILP solvers. Therefore, we have designed, implemented,
and analyzed heuristics based on local search. We have collected computational results on all the new instances with the proposed
approaches and assessed the quality of solutions with respect to the lower bounds found by ILP on a relaxed and decomposed
problem. Results show that a selected heuristic finds solutions of quality at 9%–60% distance from the lower bound. We make
all data publicly available, in order to stimulate further research on this problem. 相似文献
19.
This study shows how data envelopment analysis (DEA) can be used to reduce vertical dimensionality of certain data mining databases. The study illustrates basic concepts using a real-world graduate admissions decision task. It is well known that cost sensitive mixed integer programming (MIP) problems are NP-complete. This study shows that heuristic solutions for cost sensitive classification problems can be obtained by solving a simple goal programming problem by that reduces the vertical dimension of the original learning dataset. Using simulated datasets and a misclassification cost performance metric, the performance of proposed goal programming heuristic is compared with the extended DEA-discriminant analysis MIP approach. The holdout sample results of our experiments shows that the proposed heuristic approach outperforms the extended DEA-discriminant analysis MIP approach. 相似文献
20.
Youssef Hamadi Sa?d Jabbour Lakhdar Sa?s 《4OR: A Quarterly Journal of Operations Research》2012,10(1):15-32
Learning is a general concept, playing an important role in many Artificial intelligence domains. In this paper, we address
the learning paradigm used to explain failures or conflicts encountered during search. This explanation, derived by conflict
analysis, and generally expressed as a new constraint, is usually used to dynamically avoid future occurrences of similar
situations. Before focusing on clause learning in Boolean satisfiability (SAT), we first overview some important works on
this powerful reasoning tool in other domains such as constraint satisfaction and truth maintenance systems. Then, we present
a comprehensive survey of the most important works having led to what is called today—conflict driven clause learning (CDCL)—which
is one of the key components of modern SAT solvers. In theory, current SAT solvers with clause learning are as powerful as
general resolution proof systems. In practice, real-world SAT instances with millions of variables and clauses are now in
the scope of this solving paradigm. 相似文献