We derive and study a reformulation technique for general 0–1 quadratic programs (QP) that uses diagonal as well as nondiagonal perturbation of the objective function. The technique is an extension ...of the Quadratic Convex Reformulation (QCR) method developed by Billionnet and co-workers, adding nondiagonal perturbations, whereas QCR is in a sense diagonal. In this work a set of redundant reformulation-linearization technique (RLT) inequalities are included in the problem. The redundant inequalities are used to induce nondiagonal perturbations of the objective function that improve the bounding characteristics of the continuous relaxation. The optimal convexification is obtained from the solution of a semidefinite program. We apply the nondiagonal QCR (NDQCR) technique to four different types of problems and compare the bounding properties and solution times with the original QCR method. The proposed method outperforms the original QCR method on all four types of test problems.
In this paper, we present a global optimization method for solving nonconvex mixed integer nonlinear programming (MINLP) problems. A convex overestimation of the feasible region is obtained by ...replacing the nonconvex constraint functions with convex underestimators. For signomial functions single-variable power and exponential transformations are used to obtain the convex underestimators. For more general nonconvex functions two versions of the so-called
α
BB-underestimator, valid for twice-differentiable functions, are integrated in the actual reformulation framework. However, in contrast to what is done in branch-and-bound type algorithms, no direct branching is performed in the actual algorithm. Instead a piecewise convex reformulation is used to convexify the entire problem in an extended variable-space, and the reformulated problem is then solved by a convex MINLP solver. As the piecewise linear approximations are made finer, the solution to the convexified and overestimated problem will form a converging sequence towards a global optimal solution. The result is an easily-implementable algorithm for solving a very general class of optimization problems.
In this paper, we present a global optimization method for solving nonconvex mixed integer nonlinear programming (MINLP) problems. A convex overestimation of the feasible region is obtained by ...replacing the nonconvex constraint functions with convex underestimators. For signomial functions single-variable power and exponential transformations are used to obtain the convex underestimators. For more general nonconvex functions two versions of the so-called alphaBB-underestimator, valid for twice-differentiable functions, are integrated in the actual reformulation framework. However, in contrast to what is done in branch-and-bound type algorithms, no direct branching is performed in the actual algorithm. Instead a piecewise convex reformulation is used to convexify the entire problem in an extended variable-space, and the reformulated problem is then solved by a convex MINLP solver. As the piecewise linear approximations are made finer, the solution to the convexified and overestimated problem will form a converging sequence towards a global optimal solution. The result is an easily-implementable algorithm for solving a very general class of optimization problems. Keywords Global optimization * Reformulation technique * Convex underestimators * Mixed integer nonlinear programming * Twice-differentiable functions * Signomial functions * Piecewise linear functions * alphaBB-underestimator * SGO-algorithm
Most branch-and-bound algorithms in global optimization depend on convex underestimators to calculate lower bounds of a minimization objective function. The
BB methodology produces such ...underestimators for sufficiently smooth functions by analyzing interval Hessian approximations. Several methods to rigorously determine the
BB parameters have been proposed, varying in tightness and computational complexity. We present new polynomial-time methods and compare their properties to existing approaches. The new methods are based on classical eigenvalue bounds from linear algebra and a more recent result on interval matrices. We show how parameters can be optimized with respect to the average underestimation error, in addition to the maximum error commonly used in
BB methods. Numerical comparisons are made, based on test functions and a set of randomly generated interval Hessians. The paper shows the relative strengths of the methods, and proves exact results where one method dominates another.
This paper presents a new LP (Linear Programming) model to solve a tactical wood procurement and harvesting problem. This optimization problem occurs in several wood supply chains today. The goal ...with the optimization is to find a 12 month procurement, harvesting and transportation plan that minimizes total costs. The case study is found in one of the Finnish wood supply chains and the model is implemented to aid the decision making process. The focus of the paper is on the modeling of some phenomena peculiar to wood procurement.
