共查询到20条相似文献,搜索用时 31 毫秒
1.
In this paper, we consider the linear complementarity problem (LCP) and present a global optimization algorithm based on an application of the reformulation-linearization technique (RLT). The matrix M associated with the LCP is not assumed to possess any special structure. In this approach, the LCP is formulated first as a mixed-integer 0–1 bilinear programming problem. The RLT scheme is then used to derive a new equivalent mixed-integer linear programming formulation of the LCP. An implicit enumeration scheme is developed that uses Lagrangian relaxation, strongest surrogate and strengthened cutting planes, and a heuristic, designed to exploit the strength of the resulting linearization. Computational experience on various test problems is presented. 相似文献
2.
In this paper, we consider a dynamic Lagrangian dual optimization procedure for solving mixed-integer 0–1 linear programming
problems. Similarly to delayed relax-and-cut approaches, the procedure dynamically appends valid inequalities to the linear
programming relaxation as induced by the Reformulation-Linearization Technique (RLT). A Lagrangian dual algorithm that is
augmented with a primal solution recovery scheme is applied implicitly to a full or partial first-level RLT relaxation, where
RLT constraints that are currently being violated by the primal estimate are dynamically generated within the Lagrangian dual
problem, thus controlling the size of the dual space while effectively capturing the strength of the RLT-enhanced relaxation.
We present a preliminary computational study to demonstrate the efficacy of this approach. 相似文献
3.
The Reformulation-Linearization Technique (RLT) provides a hierarchy of relaxations spanning the spectrum from the continuous relaxation to the convex hull representation for linear 0-1 mixed-integer and general mixed-discrete programs. We show in this paper that this result holds identically for semi-infinite programs of this type. As a consequence, we extend the RLT methodology to describe a construct for generating a hierarchy of relaxations leading to the convex hull representation for bounded 0-1 mixed-integer and general mixed-discrete convex programs, using an equivalent semi-infinite linearized representation for such problems as an intermediate stepping stone in the analysis. For particular use in practice, we provide specialized forms of the resulting first-level RLT formulation for such mixed 0-1 and discrete convex programs, and illustrate these forms through two examples. 相似文献
5.
In this paper we introduce DRL*, a new hierarchy of linear relaxations for 0-1 mixed integer linear programs (MIPs), based on the idea of Reformulation-Linearization, and explore its links with the Lift-and-Project (L&P) hierarchy and the Sherali-Adams (RLT) hierarchy. The relaxations of the new hierarchy are shown to be intermediate in strength between L&P and RLT relaxations, and examples are shown for which it leads to significantly stronger bounds than those obtained from Lift-and-Project relaxations. On the other hand, as opposed to the RLT relaxations, a key advantage of the DRL* relaxations is that they feature a decomposable structure when formulated in extended space, therefore lending themselves to more efficient solution algorithms by properly exploiting decomposition. Links between DRL* and both the L&P and RLT hierarchies are further explored, and those constraints which should be added to the rank d L&P relaxation (resp to the rank d RLT relaxation) to make it coincide with the rank d DRL* relaxation (resp: to the rank d RLT relaxation) are identified. Furthermore, a full characterization of those 0-1 MIPs for which the DRL* and RLT relaxations coincide is obtained. As an application, we show that both the RLT and DRL* relaxations are the same up to rank d for the problem of optimizing a pseudoboolean function of degree d over a polyhedron. We report computational results comparing the strengths of the rank 2 L&P, DRL* and RLT relaxations. Impact on possible improved efficiency in computing some bounds for the quadratic assignment problem and other directions for future research are suggested in the conclusions. 相似文献
6.
Including integer variables into traditional stochastic linear programs has considerable implications for structural analysis
and algorithm design. Starting from mean-risk approaches with different risk measures we identify corresponding two- and multi-stage
stochastic integer programs that are large-scale block-structured mixed-integer linear programs if the underlying probability
distributions are discrete. We highlight the role of mixed-integer value functions for structure and stability of stochastic
integer programs. When applied to the block structures in stochastic integer programming, well known algorithmic principles
such as branch-and-bound, Lagrangian relaxation, or cutting plane methods open up new directions of research. We review existing
results in the field and indicate departure points for their extension.
Received: December 2, 2002 / Accepted: April 23, 2003
Published online: May 28, 2003
Mathematics Subject Classification (2000): 90C15, 90C11, 90C06, 90C57 相似文献
7.
A common way to produce a convex relaxation of a Mixed Integer Quadratically Constrained Program (MIQCP) is to lift the problem
into a higher-dimensional space by introducing variables Y
ij
to represent each of the products x
i
x
j
of variables appearing in a quadratic form. One advantage of such extended relaxations is that they can be efficiently strengthened
by using the (convex) SDP constraint
Y - x xT \succeq 0{Y - x x^T \succeq 0} and disjunctive programming. On the other hand, the main drawback of such an extended formulation is its huge size, even
for problems for which the number of x
i
variables is moderate. In this paper, we study methods to build low-dimensional relaxations of MIQCP that capture the strength
of the extended formulations. To do so, we use projection techniques pioneered in the context of the lift-and-project methodology.
We show how the extended formulation can be algorithmically projected to the original space by solving linear programs. Furthermore,
we extend the technique to project the SDP relaxation by solving SDPs. In the case of an MIQCP with a single quadratic constraint,
we propose a subgradient-based heuristic to efficiently solve these SDPs. We also propose a new eigen-reformulation for MIQCP, and a cut generation technique to strengthen this reformulation using polarity. We present extensive computational
results to illustrate the efficiency of the proposed techniques. Our computational results have two highlights. First, on
the GLOBALLib instances, we are able to generate relaxations that are almost as strong as those proposed in our companion
paper even though our computing times are about 100 times smaller, on average. Second, on box-QP instances, the strengthened
relaxations generated by our code are almost as strong as the well-studied SDP+RLT relaxations and can be solved in less than
2 s, even for large instances with 100 variables; the SDP+RLT relaxations for the same set of instances can take up to a couple
of hours to solve using a state-of-the-art SDP solver. 相似文献
8.
A common strategy for solving 0-1 cubic programs is to reformulate the non-linear problem into an equivalent linear representation, which can then be submitted directly to a standard mixed-integer programming solver. Both the size and the strength of the continuous relaxation of the reformulation determine the success of this method. One of the most compact linear representations of 0-1 cubic programs is based on a repeated application of the linearization technique for 0-1 quadratic programs introduced by Glover. In this paper, we develop a pre-processing step that serves to strengthen the linear programming bound provided by this concise linear form of a 0-1 cubic program. The proposed scheme involves using optimal dual multipliers of a partial level-2 RLT formulation to rewrite the objective function of the cubic program before applying the linearization. We perform extensive computational tests on the 0-1 cubic multidimensional knapsack problem to show the advantage of our approach. 相似文献
9.
We propose two primal heuristics for nonconvex mixed-integer nonlinear programs. Both are based on the idea of rounding the
solution of a continuous nonlinear program subject to linear constraints. Each rounding step is accomplished through the solution
of a mixed-integer linear program. Our heuristics use the same algorithmic scheme, but they differ in the choice of the point
to be rounded (which is feasible for nonlinear constraints but possibly fractional) and in the linear constraints. We propose
a feasibility heuristic, that aims at finding an initial feasible solution, and an improvement heuristic, whose purpose is
to search for an improved solution within the neighborhood of a given point. The neighborhood is defined through local branching cuts or box constraints. Computational results show the effectiveness in practice of these simple ideas, implemented within
an open-source solver for nonconvex mixed-integer nonlinear programs. 相似文献
10.
Mixed-integer rounding (MIR) inequalities play a central role in the development of strong cutting planes for mixed-integer
programs. In this paper, we investigate how known MIR inequalities can be combined in order to generate new strong valid inequalities.?Given
a mixed-integer region S and a collection of valid “base” mixed-integer inequalities, we develop a procedure for generating new valid inequalities
for S. The starting point of our procedure is to consider the MIR inequalities related with the base inequalities. For any subset
of these MIR inequalities, we generate two new inequalities by combining or “mixing” them. We show that the new inequalities
are strong in the sense that they fully describe the convex hull of a special mixed-integer region associated with the base
inequalities.?We discuss how the mixing procedure can be used to obtain new classes of strong valid inequalities for various
mixed-integer programming problems. In particular, we present examples for production planning, capacitated facility location,
capacitated network design, and multiple knapsack problems. We also present preliminary computational results using the mixing
procedure to tighten the formulation of some difficult integer programs. Finally we study some extensions of this mixing procedure.
Received: April 1998 / Accepted: January 2001?Published online April 12, 2001 相似文献
11.
This paper explores equivalent, reduced size Reformulation-Linearization Technique (RLT)-based formulations for polynomial
programming problems. Utilizing a basis partitioning scheme for an embedded linear equality subsystem, we show that a strict
subset of RLT defining equalities imply the remaining ones. Applying this result, we derive significantly reduced RLT representations
and develop certain coherent associated branching rules that assure convergence to a global optimum, along with static as
well as dynamic basis selection strategies to implement the proposed procedure. In addition, we enhance the RLT relaxations
with v-semidefinite cuts, which are empirically shown to further improve the relative performance of the reduced RLT method over
the usual RLT approach. We present computational results for randomly generated instances to test the different proposed reduction
strategies and to demonstrate the improvement in overall computational effort when such reduced RLT mechanisms are employed. 相似文献
12.
In this paper, we propose a decomposition-based branch-and-bound ( DBAB) algorithm for solving two-stage stochastic programs having mixed-integer first- and second-stage variables. A modified Benders'
decomposition method is developed, where the Benders' subproblems define lower bounding second-stage value functions of the
first-stage variables that are derived by constructing a certain partial convex hull representation of the two-stage solution
space. This partial convex hull is sequentially generated using a convexification scheme such as the Reformulation-Linearization
Technique (RLT) or lift-and-project process, which yields valid inequalities that are reusable in the subsequent subproblems
by updating the values of the first-stage variables. A branch-and-bound algorithm is designed based on a hyperrectangular
partitioning process, using the established property that any resulting lower bounding Benders' master problem defined over
a hyperrectangle yields the same objective value as the original stochastic program over that region if the first-stage variable
solution is an extreme point of the defining hyperrectangle or the second-stage solution satisfies the binary restrictions.
We prove that this algorithm converges to a global optimal solution. Some numerical examples and computational results are
presented to demonstrate the efficacy of this approach. 相似文献
13.
Given a set of R
n
and a function f from into R
n
we consider a problem of finding a point x
* in such that (x–x
*)
t
f(x
*)0 holds for every point x in . This problem is called the stationary point problem and the point x
* is called a stationary point. We present a variable dimension algorithm for solving the stationary point problem with an affine function f on a polytope defined by constraints of linear equations and inequalities. We propose a system of equations whose solution set contains a piecewise linear path connecting a trivial starting point in with a stationary point. The path can be followed by solving a series of linear programs which inherit the structure of constraints of . The linear programs are solved efficiently with the Dantzig-Wolfe decomposition method by exploiting fully the structure.Part of this research was carried out when the first author was supported by the Center for Economic Research, Tilburg University, The Netherlands and the third author was supported by the Alexander von Humboldt-Foundation, Federal Republic of Germany. 相似文献
14.
Current mixed-integer linear programming solvers are based on linear programming routines that use floating-point arithmetic. Occasionally, this leads to wrong solutions, even for problems where all coefficients and all solution components are small integers. An example is given where many state-of-the-art MILP solvers fail. It is then shown how, using directed rounding and interval arithmetic, cheap pre- and postprocessing of the linear programs arising in a branch-and-cut framework can guarantee that no solution is lost, at least for mixed-integer programs in which all variables can be bounded rigorously by bounds of reasonable size.
Mathematics Subject Classification (2000):primary 90C11, secondary 65G20 相似文献
15.
To estimate the number and location of limit cycles of Kukles systems in a strip of the phase plane xOy, we develop a method for constructing the Dulac function in the form of a polynomial in the phase variable y with coefficients depending on the second phase variable x. The suggested method is regular for h
2( x) = 0. The proof of the fact that the constructed function is a Dulac function is reduced to finding a specific number of
positive functions that are linear combinations of known functions of the single phase variable x with arbitrary constants. To construct the Dulac function, we use a solution of the corresponding linear programming problem.
In addition, we show that the presented approach is efficient from the practical viewpoint and permits one to obtain a global
exact estimate for the number of limit cycles of above-mentioned systems in some cases. 相似文献
16.
This work attempts to combine the strengths of two major technologies that have matured over the last three decades: global mixed-integer nonlinear optimization and branch-and-price. We consider a class of generally nonconvex mixed-integer nonlinear programs (MINLPs) with linear complicating constraints and integer linking variables. If the complicating constraints are removed, the problem becomes easy to solve, e.g. due to decomposable structure. Integrality of the linking variables allows us to apply a discretization approach to derive a Dantzig-Wolfe reformulation and solve the problem to global optimality using branch-andprice. It is a remarkably simple idea; but to our surprise, it has barely found any application in the literature. In this work, we show that many relevant problems directly fall or can be reformulated into this class of MINLPs. We present the branch-and-price algorithm and demonstrate its effectiveness (and sometimes ineffectiveness) in an extensive computational study considering multiple large-scale problems of practical relevance, showing that, in many cases, orders-of-magnitude reductions in solution time can be achieved. 相似文献
17.
We develop explicit, piecewise-linear formulations of functions f( x):ℝ
n
↦ℝ, n≤3, that are defined on an orthogonal grid of vertex points. If mixed-integer linear optimization problems (MILPs) involving
multidimensional piecewise-linear functions can be easily and efficiently solved to global optimality, then non-analytic functions
can be used as an objective or constraint function for large optimization problems. Linear interpolation between fixed gridpoints
can also be used to approximate generic, nonlinear functions, allowing us to approximately solve problems using mixed-integer
linear optimization methods. Toward this end, we develop two different explicit formulations of piecewise-linear functions
and discuss the consequences of integrating the formulations into an optimization problem. 相似文献
18.
This paper presents a general, self-contained treatment of convexity or intersection cuts. It describes two equivalent ways of generating a cut—via a convex set or a concave function—and a partial-order notion
of cut strength. We then characterize the structure of the sets and functions that generate cuts that are strongest with respect
to the partial order. Next, we specialize this analytical framework to the case of mixed-integer linear programming (MIP).
For this case, we formulate two kinds of the deepest cut generation problem, via sets or via functions, and subsequently consider
some special cases which are amenable to efficient computation. We conclude with computational tests of one of these procedures
on a large set of MIPLIB problems. 相似文献
19.
This paper studies the global optimization of polynomial programming problems using Reformulation-Linearization Technique
(RLT)-based linear programming (LP) relaxations. We introduce a new class of bound-grid-factor constraints that can be judiciously used to augment the basic RLT relaxations in order to improve the quality of lower bounds
and enhance the performance of global branch-and-bound algorithms. Certain theoretical properties are established that shed
light on the effect of these valid inequalities in driving the discrepancies between RLT variables and their associated nonlinear
products to zero. To preserve computational expediency while promoting efficiency, we propose certain concurrent and sequential
cut generation routines and various grid-factor selection rules. The results indicate a significant tightening of lower bounds,
which yields an overall reduction in computational effort for solving a test-bed of polynomial programming problems to global
optimality in comparison with the basic RLT procedure as well as the commercial software BARON. 相似文献
20.
Summary. We consider boundary value problems for linear differential-algebraic equations with variable coefficients with no restriction
on the index. A well-known regularisation procedure yields an equivalent index one problem with d differential and a= n-d algebraic equations. Collocation methods based on the regularised BVP approximate the solution x by a continuous piecewise polynomial of degree k and deliver, in particular, consistent approximations at mesh points by using the Radau schemes. Under weak assumptions,
the collocation problems are uniquely and stably solvable and, if the unique solution x is sufficiently smooth, convergence of order min { k+1,2 k-1} and superconvergence at mesh points of order 2 k-1 is shown. Finally, some numerical experiments illustrating these results are presented.
Received October 1, 1999 / Revised version received April 25, 2000 / Published online December 19, 2000 相似文献
|