共查询到20条相似文献,搜索用时 0 毫秒
1.
In this paper, we describe the implementation of some heuristics for convex mixed integer nonlinear programs. The work focuses
on three families of heuristics that have been successfully used for mixed integer linear programs: diving heuristics, the
Feasibility Pump, and Relaxation Induced Neighborhood Search (RINS). We show how these heuristics can be adapted in the context
of mixed integer nonlinear programming. We present results from computational experiments on a set of instances that show
how the heuristics implemented help finding feasible solutions faster than the traditional branch-and-bound algorithm and
how they help in reducing the total solution time of the branch-and-bound algorithm. 相似文献
2.
We describe a computationally effective method for generating lift-and-project cuts for convex mixed-integer nonlinear programs (MINLPs). The method relies on solving a sequence of cut-generating linear programs and in the limit generates an inequality as strong as the lift-and-project cut that can be obtained from solving a cut-generating nonlinear program. Using this procedure, we are able to approximately optimize over the rank one lift-and-project closure for a variety of convex MINLP instances. The results indicate that lift-and-project cuts have the potential to close a significant portion of the integrality gap for convex MINLPs. In addition, we find that using this procedure within a branch-and-cut solver for convex MINLPs significantly reduces the total solution time for many instances. We also demonstrate that combining lift-and-project cuts with an extended formulation that exploits separability of convex functions yields significant improvements in both relaxation bounds and the time to calculate the relaxation. Overall, these results suggest that with an effective separation routine, like the one proposed here, lift-and-project cuts may be as effective for solving convex MINLPs as they have been for solving mixed-integer linear programs. 相似文献
3.
This paper is motivated by the fact that mixed integer nonlinear programming is an important and difficult area for which there is a need for developing new methods and software for solving large-scale problems. Moreover, both fundamental building blocks, namely mixed integer linear programming and nonlinear programming, have seen considerable and steady progress in recent years. Wishing to exploit expertise in these areas as well as on previous work in mixed integer nonlinear programming, this work represents the first step in an ongoing and ambitious project within an open-source environment. COIN-OR is our chosen environment for the development of the optimization software. A class of hybrid algorithms, of which branch-and-bound and polyhedral outer approximation are the two extreme cases, are proposed and implemented. Computational results that demonstrate the effectiveness of this framework are reported. Both the library of mixed integer nonlinear problems that exhibit convex continuous relaxations, on which the experiments are carried out, and a version of the software used are publicly available. 相似文献
4.
This tutorial presents a theory of valid inequalities for mixed integer linear sets. It introduces the necessary tools from
polyhedral theory and gives a geometric understanding of several classical families of valid inequalities such as lift-and-project
cuts, Gomory mixed integer cuts, mixed integer rounding cuts, split cuts and intersection cuts, and it reveals the relationships
between these families. The tutorial also discusses computational aspects of generating the cuts and their strength.
Supported by NSF grant DMI-0352885, ONR grant N00014-03-1-0188 and ANR grant BLAN06-1-138894. 相似文献
7.
We present an algorithm for finding a feasible solution to a convex mixed integer nonlinear program. This algorithm, called
Feasibility Pump, alternates between solving nonlinear programs and mixed integer linear programs. We also discuss how the
algorithm can be iterated so as to improve the first solution it finds, as well as its integration within an outer approximation
scheme. We report computational results.
P. Bonami is supported in part by a grant from IBM and by ANR grant BLAN06-1-138894.
G. Cornuéjols is supported in part by NSF grant CMMI-0653419, ANR grant BLAN06-1-138894 and ONR grant N00014-03-1-0188.
Part of this research was carried out when Andrea Lodi was Herman Goldstine Fellow of the IBM T.J. Watson Research Center
whose support is gratefully acknowledged.
F. Margot is supported in part by a grant from IBM and by ONR grant N00014-03-1-0188. 相似文献
8.
A simple condition on the underlying subadditive function is shown to characterize minimal valid inequalities. This result is proved in a very general master problem framework and completes the characterization there. We explain the condition also in the context of value functions and finally give some related, unresolved questions. 相似文献
9.
We develop a general framework for linear intersection cuts for convex integer programs with full-dimensional feasible regions by studying integer points of their translated tangent cones, generalizing the idea of Balas (1971). For proper (i.e, full-dimensional, closed, convex, pointed) translated cones with fractional vertices, we show that under certain mild conditions all intersection cuts are indeed valid for the integer hull, and a large class of valid inequalities for the integer hull are intersection cuts, computable via polyhedral approximations. We also give necessary conditions for a class of valid inequalities to be tangent halfspaces of the integer hull of proper translated cones. We also show that valid inequalities for non-pointed regular translated cones can be derived as intersection cuts for associated proper translated cones under some mild assumptions. 相似文献
10.
We present two new algorithms for convex Mixed Integer Nonlinear Programming (MINLP), both based on the well known Extended Cutting Plane (ECP) algorithm proposed by Weterlund and Petersson. Our first algorithm, Refined Extended Cutting Plane (RECP), incorporates additional cuts to the MILP relaxation of the original problem, obtained by solving linear relaxations of NLP problems considered in the Outer Approximation algorithm. Our second algorithm, Linear Programming based Branch-and-Bound (LP-BB), applies the strategy of generating cuts that is used in RECP, to the linear approximation scheme used by the LP/NLP based Branch-and-Bound algorithm. Our computational results show that RECP and LP-BB are highly competitive with the most popular MINLP algorithms from the literature, while keeping the nice and desirable characteristic of ECP, of being a first-order method. 相似文献
11.
We investigate strong inequalities for mixed 0-1 integer programs derived from flow cover inequalities. Flow cover inequalities
are usually not facet defining and need to be lifted to obtain stronger inequalities. However, because of the sequential nature
of the standard lifting techniques and the complexity of the optimization problems that have to be solved to obtain lifting
coefficients, lifting of flow cover inequalities is computationally very demanding. We present a computationally efficient
way to lift flow cover inequalities based on sequence independent lifting techniques and give computational results that show
the effectiveness of our lifting procedures.
Received May 15, 1996 / Revised version received August 7, 1998
Published online June 28, 1999 相似文献
12.
A wide range of optimization problems arising from engineering applications can be formulated as Mixed Integer NonLinear Programming problems (MINLPs). Duran and Grossmann (1986) suggest an outer approximation scheme for solving a class of MINLPs that are linear in the integer variables by a finite sequence of relaxed MILP master programs and NLP subproblems.Their idea is generalized by treating nonlinearities in the integer variables directly, which allows a much wider class of problem to be tackled, including the case of pure INLPs. A new and more simple proof of finite termination is given and a rigorous treatment of infeasible NLP subproblems is presented which includes all the common methods for resolving infeasibility in Phase I.The worst case performance of the outer approximation algorithm is investigated and an example is given for which it visits all integer assignments. This behaviour leads us to include curvature information into the relaxed MILP master problem, giving rise to a new quadratic outer approximation algorithm.An alternative approach is considered to the difficulties caused by infeasibility in outer approximation, in which exact penalty functions are used to solve the NLP subproblems. It is possible to develop the theory in an elegant way for a large class of nonsmooth MINLPs based on the use of convex composite functions and subdifferentials, although an interpretation for the l
1 norm is also given.This work is supported by SERC grant no. SERC GR/F 07972.Corresponding author. 相似文献
13.
This is a summary of the main results presented in the author’s PhD thesis, supervised by D. Conforti and P. Beraldi and defended on March 2005. The thesis, written in English, is available from the author upon request. It describes one of the very few existing implementations of a method for solving stochastic mixed integer nonlinear programming problems based on deterministic global optimization. In order to face the computational challenge involved in the solution of such multi-scenario nonconvex problems, a branch and bound approach is proposed that exploits the peculiar structure of stochastic programming problem. 相似文献
14.
We introduce a new class of valid inequalities for general integer linear programs, called binary clutter (BC) inequalities. They include the -cuts of Caprara and Fischetti as a special case and have some interesting connections to binary matroids, binary clutters and Gomory corner polyhedra.
We show that the separation problem for BC-cuts is strongly -hard in general, but polynomially solvable in certain special cases. As a by-product we also obtain new conditions under which -cuts can be separated in polynomial time.
These ideas are then illustrated using the Traveling Salesman Problem (TSP) as an example. This leads to an interesting link between the TSP and two apparently unrelated problems, the T- join and max-cut problems. Mathematics Subject Classification: 90C10 相似文献
16.
We examine progress over the last fifteen years in finding strong valid inequalities and tight extended formulations for
simple mixed integer sets lying both on the ``easy' and ``hard' sides of the complexity frontier. Most progress has been
made in studying sets arising from knapsack and single node flow sets, and a variety of sets motivated by different lot-sizing
models. We conclude by citing briefly some of the more intriguing new avenues of research.
Received: January 15, 2003 / Accepted: April 10, 2003
Published online: May 28, 2003
Key words. mixed integer programming – strong valid inequalities – convex hull – extended formulations – single node flow sets – lot-sizing
This paper presents research results of the Belgian Program on Interuniversity Poles of Attraction initiated by the Belgian
State, Prime Minister's Office, Science Policy Programming. The scientific responsibility is assumed by the authors.
Research carried out with financial support of the project TMR-DONET nr. ERB FMRX–CT98–0202 of the European Union. 相似文献
17.
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 & 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. 相似文献
19.
We give a method for strengthening cutting planes for pure and mixed integer programs. The method improves the coefficients of the integer-constrained variables, while leaving unchanged those of the continuous variables. We first state the general principle on which the method is based; then apply it to the class of cuts that can be obtained from disjunctive constraints. Finally, we give simple procedures for calculating the improved coefficients of cats in this class, and illustrate them on a numerical example. 相似文献
20.
We investigate a scheme, called pairing, for generating new valid inequalities for mixed integer programs by taking pairwise combinations of existing valid inequalities. The pairing scheme essentially produces a split cut corresponding to a specific disjunction, and can also be derived through the mixed integer rounding procedure. The scheme is in general sequence-dependent and therefore leads to an exponential number of inequalities. For some important cases, we identify combination sequences that lead to a manageable set of non-dominated inequalities. We illustrate the framework for some deterministic and stochastic integer programs and we present computational results showing the efficiency of adding the new generated inequalities as cuts. 相似文献
|