Multiperiod blending has a number of important applications in a range of industrial sectors. It is typically formulated as a nonconvex mixed integer nonlinear program (MINLP), which involves binary variables and bili...
详细信息
Multiperiod blending has a number of important applications in a range of industrial sectors. It is typically formulated as a nonconvex mixed integer nonlinear program (MINLP), which involves binary variables and bilinear terms. In this study, we first propose a reformulation of the constraints involving bilinear terms using lifting. We introduce a method for calculating tight bounds on the lifted variables calculated by aggregating multiple constraints. We propose valid constraints derived from the reformulation-linearization technique (RLT) that use the bounds on the lifted variables to further tighten the formulation. Computational results indicate our method can substantially reduce the solution time and optimality gap.
The quadratic assignment problem (QAP) is perhaps the most widely studied nonlinear combinatorial optimization problem. It has many applications in various fields, yet has proven to be extremely difficult to solve. Th...
详细信息
The quadratic assignment problem (QAP) is perhaps the most widely studied nonlinear combinatorial optimization problem. It has many applications in various fields, yet has proven to be extremely difficult to solve. This difficulty has motivated researchers to identify special objective function structures that permit an optimal solution to be found efficiently. Previous work has shown that certain such structures can be explained in terms of a mixed 0-1 linear reformulation of the QAP known as the level-1 reformulation-linearization-technique (RLT) form. Specifically, the objective function structures were shown to ensure that a binary optimal extreme point solution exists to the continuous relaxation. This paper extends that work by considering classes of solvable cases in which the objective function coefficients have special chess-board and graded structures, and similarly characterizing them in terms of the level-1 RLT form. As part of this characterization, we develop a new relaxed version of the level-1 RLT form, the structure of which can be readily exploited to study the special instances under consideration.
作者：
Balma, AliMrad, MehdiLadhari, TalelUniv Tunis
Tunis Business Sch Business Analyt & Decis Making POB 65 Tunis 2059 Tunisia Univ Tunis
Ecole Natl Super Ingenieurs Tunis Ave Taha Hussein Tunis 1008 Tunisia Univ Tunis
Ecole Super Sci Econ & Commerciales Tunis 4 Rue Abou Zakaria El Hafsi Montfleury 1089 Tunisia Umm Al Qura Univ
Coll Business Adm Mecca Saudi Arabia King Saud Univ
Coll Engn Dept Ind Engn Riyadh 11421 Saudi Arabia
In the present paper, we consider the Traveling Salesman Problem with Draft Limits (TSPDL), which is a variant of the Traveling Salesman Problem (TSP) arising in maritime transportation. We provide compact formulation...
详细信息
In the present paper, we consider the Traveling Salesman Problem with Draft Limits (TSPDL), which is a variant of the Traveling Salesman Problem (TSP) arising in maritime transportation. We provide compact formulations of polynomial size developed by using the reformulation-linearization technique (RLT) with one and two levels. In doing so, we recover time-dependent formulations of TSP and provide their factorization into products involving the decision variables and their complements. This factorization affords further RLT-lifting to the model of TSPDL by combining time-dependent and flow variables that lead to very tight linear relaxation. Computational results conducted on benchmark instances confirm the tightness of the lower bounds.
We investigate the Steiner tree problem with revenues, budget and hop constraints (STPRBH) on graph, which is a generalization of the well-known Steiner tree problem. Given a root node, edge costs, nodes revenues, as ...
详细信息
ISBN:
(纸本)9781467358125
We investigate the Steiner tree problem with revenues, budget and hop constraints (STPRBH) on graph, which is a generalization of the well-known Steiner tree problem. Given a root node, edge costs, nodes revenues, as well as a preset budget and hop, the STPRBH seeks to find a subtree that includes the root node and maximizes the sum of the total edge revenues respecting the budget and hop constraints. These constraints impose limits on the total cost of the network and the number of edges between any vertex and the root. Not surprisingly, the STPRBH is NP-hard. For this challenging network design problem that arises in telecommunication settings and multicast routing, we present several polynomial size formulations. We propose an enhanced formulation based on the classical work of Miller, Tucker, and Zemlin by using additional set of variables representing the rank-order of visiting the nodes. Also, we investigate a new formulation for the STPRBH by tailoring a partial rank-1 of the reformulation-linearization technique. Extensive results are exhibited using a set of benchmark instances to compare the proposed formulations by using a general purpose MIP solver.
暂无评论