Let (MQP) be a general mixed integer quadratic program that consists of minimizing a quadratic function subject to linear constraints. In this paper, we present a convex reformulation of (MQP), i.e. we reformulate (MQ...
详细信息
Let (MQP) be a general mixed integer quadratic program that consists of minimizing a quadratic function subject to linear constraints. In this paper, we present a convex reformulation of (MQP), i.e. we reformulate (MQP) into an equivalent program, with a convex objective function. Such a reformulation can be solved by a standard solver that uses a branch and bound algorithm. We prove that our reformulation is the best one within a convex reformulation scheme, from the continuous relaxation point of view. This reformulation, that we call MIQCR (Mixed integer Quadratic Convex Reformulation), is based on the solution of an SDP relaxation of (MQP). Computational experiences are carried out with instances of (MQP) including one equality constraint or one inequality constraint. The results show that most of the considered instances with up to 40 variables can be solved in 1 h of CPU time by a standard solver.
作者：
Joseph, AGass, SIUniv Miami
Sch Business Adm Dept Management Sci Coral Gables FL 33124 USA Univ Maryland
Robert H Smith Sch Business Dept Decis & Informat Technol College Pk MD 20742 USA
The paper is concerned with constructing general integer programming problems (GIP) with well-determined duality gaps. That is, given an integer solution vector, X*, our problem is to develop a set of integer linear i...
详细信息
The paper is concerned with constructing general integer programming problems (GIP) with well-determined duality gaps. That is, given an integer solution vector, X*, our problem is to develop a set of integer linear inequalities AX less than or equal to b and an objective function c such that X* lies within some known objective function distance of the optimal solution of the relaxed linear-programming problem. By well-determined, we mean that on completion an upper bound on the problem duality gap and an integer solution (optimal or best known) are available to the problem developer. Such a procedure can, therefore, be used to develop test problems to support the research effort in the area of general IP. (C) 2002 Elsevier Science B.V. All rights reserved.
The paper describes an objective function hyperplane search heuristic for solving the general all-integer linear programming problem (ILP). The algorithm searches a series of objective function hyperplanes and the sea...
详细信息
The paper describes an objective function hyperplane search heuristic for solving the general all-integer linear programming problem (ILP). The algorithm searches a series of objective function hyperplanes and the search over any given hyperplane is formulated as a bounded knapsack problem. Theory developed for combinations of the objective function and problem constraints is used to guide the search. We evaluate the algorithm's performance on a class of ILP problems to assess the areas of effectiveness.
暂无评论