基于分支割平面的一类无容量限制设施选址问题求解算法

无容量限制设施选址问题是经典的组合优化问题, 具有广泛的应用价值,然而该问题已被证明是NP难问题, 并且传统的分支定界方法求解速度较慢.研究以最大化总收益费用与总投建费用之差为目标的无容量限制设施选址问题,将其转化为节点包装问题,并根据模型的图形特点提出了新的合法不等式族------轴不等式族,经过严格的数学证明后得出轴不等式要强于原有的奇洞不等式. 同时,设计出切割不等式快速搜索算法嵌入到分支割平面方法中. 最后,通过实验验证了轴不等式族的强有效性, 以及分支割平面方法比分支定界方法求解速度快、节点数量少的优点.     

Valid inequalities and branch-and-cut for the clique pricing problem

Motivated by an application in highway pricing, we consider the problem that consists in setting profit-maximizing tolls on a clique subset of a multicommodity transportation network. We formulate the problem as a linear mixed integer program and propose strong valid inequalities, some of which define facets of the two-commodity polyhedron. The numerical efficiency of these inequalities is assessed by embedding them within a branch-and-cut framework.     

Efficient separation routines for the symmetric traveling salesman problem I: general tools and comb separation

This is the first of a series of two papers dedicated to efficient separation heuristics for violated inequalities in the context of solving to optimality instances of the Traveling Salesman Problem via branch-and-cut. In this paper we give the basic ideas behind these heuristics and design heuristics for comb separation. The second paper will deal with more complex inequalities such as Clique Tree, Star or Path and Ladder inequalities and give computational results. Received: September 1999 / Accepted: August 2001?Published online February 14, 2002     

A branch and cut approach to the cardinality constrained circuit problem

The Cardinality Constrained Circuit Problem (CCCP) is the problem of finding a minimum cost circuit in a graph where the circuit is constrained to have at most k edges. The CCCP is NP-Hard. We present classes of facet-inducing inequalities for the convex hull of feasible circuits, and a branch-and-cut solution approach using these inequalities. Received: April 1998 / Accepted: October 2000?Published online October 26, 2001     

A cutting plane algorithm for the Capacitated Connected Facility Location Problem

We consider a network design problem that arises in the cost-optimal design of last mile telecommunication networks. It extends the Connected Facility Location problem by introducing capacities on the facilities and links of the networks. It combines aspects of the capacitated network design problem and the single-source capacitated facility location problem. We refer to it as the Capacitated Connected Facility Location Problem. We develop a basic integer programming model based on single-commodity flows. Based on valid inequalities for the capacitated network design problem and the single-source capacitated facility location problem we derive several (new) classes of valid inequalities for the Capacitated Connected Facility Location Problem including cut set inequalities, cover inequalities and combinations thereof. We use them in a branch-and-cut framework and show their applicability and efficacy on a set of real-world instances.     

Optimal relay node placement in delay constrained wireless sensor network design

The Delay Constrained Relay Node Placement Problem (DCRNPP) frequently arises in the Wireless Sensor Network (WSN) design. In WSN, Sensor Nodes are placed across a target geographical region to detect relevant signals. These signals are communicated to a central location, known as the Base Station, for further processing. The DCRNPP aims to place the minimum number of additional Relay Nodes at a subset of Candidate Relay Node locations in such a manner that signals from various Sensor Nodes can be communicated to the Base Station within a pre-specified delay bound. In this paper, we study the structure of the projection polyhedron of the problem and develop valid inequalities in form of the node-cut inequalities. We also derive conditions under which these inequalities are facet defining for the projection polyhedron. We formulate a branch-and-cut algorithm, based upon the projection formulation, to solve DCRNPP optimally. A Lagrangian relaxation based heuristic is used to generate a good initial solution for the problem that is used as an initial incumbent solution in the branch-and-cut approach. Computational results are reported on several randomly generated instances to demonstrate the efficacy of the proposed algorithm.     

A polyhedral study of the cardinality constrained knapsack problem

 A cardinality constrained knapsack problem is a continuous knapsack problem in which no more than a specified number of nonnegative variables are allowed to be positive. This structure occurs, for example, in areas such as finance, location, and scheduling. Traditionally, cardinality constraints are modeled by introducing auxiliary 0-1 variables and additional constraints that relate the continuous and the 0-1 variables. We use an alternative approach, in which we keep in the model only the continuous variables, and we enforce the cardinality constraint through a specialized branching scheme and the use of strong inequalities valid for the convex hull of the feasible set in the space of the continuous variables. To derive the valid inequalities, we extend the concepts of cover and cover inequality, commonly used in 0-1 programming, to this class of problems, and we show how cover inequalities can be lifted to derive facet-defining inequalities. We present three families of non-trivial facet-defining inequalities that are lifted cover inequalities. Finally, we report computational results that demonstrate the effectiveness of lifted cover inequalities and the superiority of the approach of not introducing auxiliary 0-1 variables over the traditional MIP approach for this class of problems. Received: March 13, 2003 Published online: April 10, 2003 Key Words. mixed-integer programming – knapsack problem – cardinality constrained programming – branch-and-cut     

A polyhedral study of nonconvex quadratic programs with box constraints

By reformulating quadratic programs using necessary optimality conditions, we obtain a linear program with complementarity constraints. For the case where the only constraints are bounds on the variables, we study a relaxation based on a subset of the optimality conditions. By characterizing its convex hull, we obtain a large class of valid inequalities. These inequalities are used in a branch-and-cut scheme, see [13].Mathematics Subject Classification (2000): 90C26, 90C27, 90C20     

Lifting for conic mixed-integer programming

Lifting is a procedure for deriving valid inequalities for mixed-integer sets from valid inequalities for suitable restrictions of those sets. Lifting has been shown to be very effective in developing strong valid inequalities for linear integer programming and it has been successfully used to solve such problems with branch-and-cut algorithms. Here we generalize the theory of lifting to conic integer programming, i.e., integer programs with conic constraints. We show how to derive conic valid inequalities for a conic integer program from conic inequalities valid for its lower-dimensional restrictions. In order to simplify the computations, we also discuss sequence-independent lifting for conic integer programs. When the cones are restricted to nonnegative orthants, conic lifting reduces to the lifting for linear integer programming as one may expect.     

A branch-and-cut algorithm for capacitated network design problems

We present a branch-and-cut algorithm to solve capacitated network design problems. Given a capacitated network and point-to-point traffic demands, the objective is to install more capacity on the edges of the network and route traffic simultaneously, so that the overall cost is minimized. We study a mixed-integer programming formulation of the problem and identify some new facet defining inequalities. These inequalities, together with other known combinatorial and mixed-integer rounding inequalities, are used as cutting planes. To choose the branching variable, we use a new rule called “knapsack branching”. We also report on our computational experience using real-life data. Received April 29, 1997 / Revised version received January 9, 1999? Published online June 28, 1999     

A new branch-and-cut algorithm for the capacitated vehicle routing problem

We present a new branch-and-cut algorithm for the capacitated vehicle routing problem (CVRP). The algorithm uses a variety of cutting planes, including capacity, framed capacity, generalized capacity, strengthened comb, multistar, partial multistar, extended hypotour inequalities, and classical Gomory mixed-integer cuts. For each of these classes of inequalities we describe our separation algorithms in detail. Also we describe the other important ingredients of our branch-and-cut algorithm, such as the branching rules, the node selection strategy, and the cut pool management. Computational results, for a large number of instances, show that the new algorithm is competitive. In particular, we solve three instances (B-n50-k8, B-n66-k9 and B-n78-k10) of Augerat to optimality for the first time.     

A branch-and-cut algorithm for nonconvex quadratic programs with box constraints

We present the implementation of a branch-and-cut algorithm for bound constrained nonconvex quadratic programs. We use a class of inequalities developed in [12] as cutting planes. We present various branching strategies and compare the algorithm to several other methods to demonstrate its effectiveness.Mathematics Subject Classification (2000): 90C26, 90C27, 90C20     

Nonconvex, lower semicontinuous piecewise linear optimization

A branch-and-cut algorithm for solving linear problems with continuous separable piecewise linear cost functions was developed in 2005 by Keha et al. This algorithm is based on valid inequalities for an SOS2 based formulation of the problem. In this paper we study the extension of the algorithm to the case where the cost function is only lower semicontinuous. We extend the SOS2 based formulation to the lower semicontinuous case and show how the inequalities introduced by Keha et al. can also be used for this new formulation. We also introduce a simple generalization of one of the inequalities introduced by Keha et al. Furthermore, we study the discontinuities caused by fixed charge jumps and introduce two new valid inequalities by extending classical results for fixed charge linear problems. Finally, we report computational results showing how the addition of the developed inequalities can significantly improve the performance of CPLEX when solving these kinds of problems.     

The γ-connected assignment problem

Given a graph and costs of assigning to each vertex one of k different colors, we want to find a minimum cost assignment such that no color q induces a subgraph with more than a given number (γ_q) of connected components. This problem arose in the context of contiguity-constrained clustering, but also has a number of other possible applications. We show the problem to be NP-hard. Nevertheless, we derive a dynamic programming algorithm that proves the case where the underlying graph is a tree to be solvable in polynomial time. Next, we propose mixed-integer programming formulations for this problem that lead to branch-and-cut and branch-and-price algorithms. Finally, we introduce a new class of valid inequalities to obtain an enhanced branch-and-cut. Extensive computational experiments are reported.     

Capacitated Network Design using Bin-Packing

In this paper, we consider the Capacitated Network Design (CND) problem. We investigate the relationship between CND and the Bin-Packing problem. This is exploited for identifying new classes of valid inequalities for the CND problem and developing a branch-and-cut algorithm to solve it efficiently.     

Box-constrained quadratic programs with fixed charge variables

Recent work has demonstrated the potential for globally optimizing nonconvex quadratic programs using a reformulation based on the first order optimality conditions. We show how this reformulation may be generalized to account for fixed cost variables. We then extend some of the polyhedral work that has been done for bound constrained QPs to handle such fixed cost variables. We show how to lift known classes of inequalities for the case without fixed cost variables and propose several new classes. These inequalities are incorporated in a branch-and-cut algorithm.     

A branch-and-cut algorithm for a generalization of the Uncapacitated Facility Location Problem

Summary We introduce a generalization of the well-know Uncapacitated Facility Location Problem, in which clients can be served not only by single facilities but also by sets of facilitities. The problem, calledGaneralized Uncapacitated Facility Lacition Problem (GUFLP), was inspired by the Index Selection Problem in physical database design. We for mulate GUFLP as a Set Packing Problem, showing that our model contains all the clique inequalities (in polynomial number). Moreover, we describe and exact separation procedure for odd-hole inequalities, based on the particular structure of the problem. These results are used within a branch-and-cut algorithm for the exact solution of GUFLP. Computational results on two different classes of test problems are given.