Weighted Inverse Minimum Spanning Tree Problems Under Hamming Distance

In this paper, we consider weighted inverse minimum spanning tree problems under Hamming distance. Three models are considered: unbounded case, unbounded case with forbidden edges, and general bounded case. In terms of the method for minimum-weight node cover problem on bipartite graph, we present their respective strongly polynomial algorithms.This research is supported by TRAPOYT, National Natural Science Foundation of China (10271110, 60021201)     

Recoverable robust spanning tree problem under interval uncertainty representations

This paper deals with the recoverable robust spanning tree problem under interval uncertainty representations. A strongly polynomial time, combinatorial algorithm for the recoverable spanning tree problem is first constructed. This problem generalizes the incremental spanning tree problem, previously discussed in literature. The algorithm built is then applied to solve the recoverable robust spanning tree problem, under the traditional interval uncertainty representation, in polynomial time. Moreover, the algorithm allows to obtain several approximation results for the recoverable robust spanning tree problem under the Bertsimas and Sim interval uncertainty representation and the interval uncertainty representation with a budget constraint.     

Some inverse min-max network problems under weighted l1 and l∞ norms with bound constraints on changes

We consider some inverse min-max (or max-min) network problems. Such an inverse problem is to modify the weights with bound constraints so that a given feasible solution becomes an optimal solution of a min-max (or max-min) network problem, and the deviation of the weights, measured by the weighted l ₁ norm or weighted l _∞ norm, is minimum. In this paper, we present strongly polynomial time algorithms to solve the inverse min-max spanning tree problem and the inverse maximum capacity path problem.     

Approximation of knapsack problems with conflict and forcing graphs

We study the classical 0–1 knapsack problem with additional restrictions on pairs of items. A conflict constraint states that from a certain pair of items at most one item can be contained in a feasible solution. Reversing this condition, we obtain a forcing constraint stating that at least one of the two items must be included in the knapsack. A natural way for representing these constraints is the use of conflict (resp. forcing) graphs. By modifying a recent result of Lokstanov et al. (Proceedings of the 25th annual ACM-SIAM symposium on discrete algorithms, SODA, pp 570–581, 2014) we derive a fairly complicated FPTAS for the knapsack problem on weakly chordal conflict graphs. Next, we show that the techniques of modular decompositions and clique separators, widely used in the literature for solving the independent set problem on special graph classes, can be applied to the knapsack problem with conflict graphs. In particular, we can show that every positive approximation result for the atoms of prime graphs arising from such a decomposition carries over to the original graph. We point out a number of structural results from the literature which can be used to show the existence of an FPTAS for several graph classes characterized by the exclusion of certain induced subgraphs. Finally, a PTAS for the knapsack problem with H-minor free conflict graph is derived. This includes planar graphs and, more general, graphs of bounded genus. The PTAS is obtained by expanding a general result of Demaine et al. (Proceedings of 46th annual IEEE symposium on foundations of computer science, FOCS 2005, pp 637–646, 2005). The knapsack problem with forcing graphs can be transformed into a minimization knapsack problem with conflict graphs. It follows immediately that all our FPTAS results of the current and a previous paper carry over from conflict graphs to forcing graphs. In contrast, the forcing graph variant is already inapproximable on planar graphs.     

Reduced costs propagation in an efficient implicit enumeration for the 01 multidimensional knapsack problem

In a previous work we proposed a variable fixing heuristics for the 0-1 Multidimensional knapsack problem (01MDK). This approach uses fractional optima calculated in hyperplanes which contain the binary optimum. This algorithm obtained best lower bounds on the OR-Library benchmarks. Although it is very attractive in terms of results, this method does not prove the optimality of the solutions found and may fix variables to a non-optimal value. In this paper, we propose an implicit enumeration based on a reduced costs analysis which tends to fix non-basic variables to their exact values. The combination of two specific constraint propagations based on reduced costs and an efficient enumeration framework enable us to fix variables on the one hand and to prune significantly the search tree on the other hand. Experimentally, our work provides two main contributions: (1) we obtain several new optimal solutions on hard instances of the OR-Library and (2) we reduce the bounds of the number of items at the optimum on several harder instances.     

The min-up/min-down unit commitment polytope

The min-up/min-down unit commitment problem (MUCP) is to find a minimum-cost production plan on a discrete time horizon for a set of fossil-fuel units for electricity production. At each time period, the total production has to meet a forecast demand. Each unit must satisfy minimum up-time and down-time constraints besides featuring production and start-up costs. A full polyhedral characterization of the MUCP with only one production unit is provided by Rajan and Takriti (Minimum up/down polytopes of the unit commitment problem with start-up costs. IBM Research Report, 2005). In this article, we analyze polyhedral aspects of the MUCP with n production units. We first translate the classical extended cover inequalities of the knapsack polytope to obtain the so-called up-set inequalities for the MUCP polytope. We introduce the interval up-set inequalities as a new class of valid inequalities, which generalizes both up-set inequalities and minimum up-time inequalities. We provide a characterization of the cases when interval up-set inequalities are valid and not dominated by other inequalities. We devise an efficient Branch and Cut algorithm, using up-set and interval up-set inequalities.     

A Semidefinite Programming Approach to the Quadratic Knapsack Problem

In order to gain insight into the quality of semidefinite relaxations of constrained quadratic 0/1 programming problems we study the quadratic knapsack problem. We investigate several basic semidefinite relaxations of this problem and compare their strength in theory and in practice. Various possibilities to improve these basic relaxations by cutting planes are discussed. The cutting planes either arise from quadratic representations of linear inequalities or from linear inequalities in the quadratic model. In particular, a large family of combinatorial cuts is introduced for the linear formulation of the knapsack problem in quadratic space. Computational results on a small class of practical problems illustrate the quality of these relaxations and cutting planes.     

The Knapsack Sharing Problem: An Exact Algorithm

In this paper, we propose an exact algorithm for the knapsack sharing problem. The proposed algorithm seems quite efficient in the sense that it solves quickly some large problem instances. The problem is decomposed into a series of single constraint knapsack problems; and by applying the dynamic programming and another strategy, we solve optimally the original problem. The performance of the exact algorithm is evaluated on a set of medium and large problem instances (a total of 240 problem instances). This algorithm is parallelizable and this is one of its important feature.     

ILP formulation of the degree-constrained minimum spanning hierarchy problem

Given a connected edge-weighted graph G and a positive integer B, the degree-constrained minimum spanning tree problem (DCMST) consists in finding a minimum cost spanning tree of G such that the degree of each vertex in the tree is less than or equal to B. This problem, which has been extensively studied over the last few decades, has several practical applications, mainly in networks. However, some applications do not especially impose a subgraph as a solution. For this purpose, a more flexible so-called hierarchy structure has been proposed. Hierarchy, which can be seen as a generalization of trees, is defined as a homomorphism of a tree in a graph. In this paper, we discuss the degree-constrained minimum spanning hierarchy (DCMSH) problem which is NP-hard. An integer linear program (ILP) formulation of this new problem is given. Properties of the solution are analysed, which allows us to add valid inequalities to the ILP. To evaluate the difference of cost between trees and hierarchies, the exact solution of DCMST and z problems are compared. It appears that, in sparse random graphs, the average percentage of improvement of the cost varies from 20 to 36% when the maximal authorized degree of vertices B is equal to 2, and from 11 to 31% when B is equal to 3. The improvement increases as the graph size increases.     

Solution Structure of Some Inverse Combinatorial Optimization Problems

In this paper we consider some inverse combinatorial optimization problems, that is, for a given set of feasible solutions of an optimization problem, we wish to know: under what weight vectors (or capacity vectors) will these feasible solutions become optimal solutions? We analysed shortest path problem, minimum cut problem, minimum spanning tree problem and maximum-weight matching problem, and found that in each of these cases, the solution set of the inverse problem is charaterized by solving another combinatorial optimization problem. The main tool in our approach is Fulkerson's theory of blocking and anti-blocking polyhedra with some necessary revisions.     

On some geometric problems of color-spanning sets

In this paper we study several geometric problems of color-spanning sets: given n points with m colors in the plane, selecting m points with m distinct colors such that some geometric properties of the m selected points are minimized or maximized. The geometric properties studied in this paper are the maximum diameter, the largest closest pair, the planar smallest minimum spanning tree, the planar largest minimum spanning tree and the planar smallest perimeter convex hull. We propose an O(n ^1+ε ) time algorithm for the maximum diameter color-spanning set problem where ε could be an arbitrarily small positive constant. Then, we present hardness proofs for the other problems and propose two efficient constant factor approximation algorithms for the planar smallest perimeter color-spanning convex hull problem.     

On the minimum routing cost clustered tree problem

For an edge-weighted graph \(G=(V,E,w)\), in which the vertices are partitioned into k clusters \(\mathcal {R}=\{R_1,R_2,\ldots ,R_k\}\), a spanning tree T of G is a clustered spanning tree if T can be cut into k subtrees by removing \(k-1\) edges such that each subtree is a spanning tree for one cluster. In this paper, we show the inapproximability of finding a clustered spanning tree with minimum routing cost, where the routing cost is the total distance summed over all pairs of vertices. We present a 2-approximation for the case that the input is a complete weighted graph whose edge weights obey the triangle inequality. We also study a variant in which the objective function is the total distance summed over all pairs of vertices of different clusters. We show that the problem is polynomial-time solvable when the number of clusters k is 2 and NP-hard for \(k=3\). Finally, we propose a polynomial-time 2-approximation algorithm for the case of three clusters.     

Heuristics for the network design problem with connectivity requirements

We consider the NP-complete problem of finding a spanning \(k\)-tree of minimum weight in a complete weighted graph. This problem has a number of applications in designing reliable backbone telecommunication networks. We propose effective algorithms based on a greedy strategy and several variable neighborhood search metaheuristics. We also develop an integer linear programming model for calculating a lower bound. Preliminary numerical experiments using random and real-word data sets are reported to show the effectiveness of our approach. In addition, we compare our approach with known metaheuristics.     

Approximation Algorithms for the Multiple Knapsack Problem with Assignment Restrictions

Motivated by a real world application, we study the multiple knapsack problem with assignment restrictions (MKAR). We are given a set of items, each with a positive real weight, and a set of knapsacks, each with a positive real capacity. In addition, for each item a set of knapsacks that can hold that item is specified. In a feasible assignment of items to knapsacks, each item is assigned to at most one knapsack, assignment restrictions are satisfied, and knapsack capacities are not exceeded. We consider the objectives of maximizing assigned weight and minimizing utilized capacity.We focus on obtaining approximate solutions in polynomial computational time. We show that simple greedy approaches yield 1/3-approximation algorithms for the objective of maximizing assigned weight. We give two different 1/2-approximation algorithms: the first one solves single knapsack problems successively and the second one is based on rounding the LP relaxation solution. For the bicriteria problem of minimizing utilized capacity subject to a minimum requirement on assigned weight, we give an (1/3,2)-approximation algorithm.     

The QAP-polytope and the graph isomorphism problem

In this paper we propose a geometric approach to solve the Graph Isomorphism (GI in short) problem. Given two graphs \(G_1, G_2\), the GI problem is to decide if the given graphs are isomorphic i.e., there exists an edge preserving bijection between the vertices of the two graphs. We propose an Integer Linear Program (ILP) that has a non-empty solution if and only if the given graphs are isomorphic. The convex hull of all possible solutions of the ILP has been studied in literature as the Quadratic Assignment Problem (QAP) polytope. We study the feasible region of the linear programming relaxation of the ILP and show that the given graphs are isomorphic if and only if this region intersects with the QAP-polytope. As a consequence, if the graphs are not isomorphic, the feasible region must lie entirely outside the QAP-polytope. We study the facial structure of the QAP-polytope with the intention of using the facet defining inequalities to eliminate the feasible region outside the polytope. We determine two new families of facet defining inequalities of the QAP-polytope and show that all the known facet defining inequalities are special instances of a general inequality. Further we define a partial ordering on each exponential sized family of facet defining inequalities and show that if there exists a common minimal violated inequality for all points in the feasible region outside the QAP-polytope, then we can solve the GI problem in polynomial time. We also study the general case when there are k such inequalities and give an algorithm for the GI problem that runs in time exponential in k.     

A successive approximation algorithm for the multiple knapsack problem

It is well-known that the multiple knapsack problem is NP-hard, and does not admit an FPTAS even for the case of two identical knapsacks. Whereas the 0-1 knapsack problem with only one knapsack has been intensively studied, and some effective exact or approximation algorithms exist. A natural approach for the multiple knapsack problem is to pack the knapsacks successively by using an effective algorithm for the 0-1 knapsack problem. This paper considers such an approximation algorithm that packs the knapsacks in the nondecreasing order of their capacities. We analyze this algorithm for 2 and 3 knapsack problems by the worst-case analysis method and give all their error bounds.     

A Combined D.C. Optimization—Ellipsoidal Branch-and-Bound Algorithm for Solving Nonconvex Quadratic Programming Problems

In this paper we propose a new branch-and-bound algorithm by using an ellipsoidal partition for minimizing an indefinite quadratic function over a bounded polyhedral convex set which is not necessarily given explicitly by a system of linear inequalities and/or equalities. It is required that for this set there exists an efficient algorithm to verify whether a point is feasible, and to find a violated constraint if this point is not feasible. The algorithm is based upon the fact that the problem of minimizing an indefinite quadratic form over an ellipsoid can be efficiently solved by some available (polynomial and nonpolynomial time) algorithms. In particular, the d.c. (difference of convex functions) algorithm (DCA) with restarting procedure recently introduced by Pham Dinh Tao and L.T. Hoai An is applied to globally solving this problem. DCA is also used for locally solving the nonconvex quadratic program. It is restarted with current best feasible points in the branch-and-bound scheme, and improved them in its turn. The combined DCA-ellipsoidal branch-and-bound algorithm then enhances the convergence: it reduces considerably the upper bound and thereby a lot of ellipsoids can be eliminated from further consideration. Several numerical experiments are given.     

On threshold BDDs and the optimal variable ordering problem

Many combinatorial optimization problems can be formulated as 0/1 integer programs (0/1 IPs). The investigation of the structure of these problems raises the following tasks: count or enumerate the feasible solutions and find an optimal solution according to a given linear objective function. All these tasks can be accomplished using binary decision diagrams (BDDs), a very popular and effective datastructure in computational logics and hardware verification. We present a novel approach for these tasks which consists of an output-sensitive algorithm for building a BDD for a linear constraint (a so-called threshold BDD) and a parallel AND operation on threshold BDDs. In particular our algorithm is capable of solving knapsack problems, subset sum problems and multidimensional knapsack problems. BDDs are represented as a directed acyclic graph. The size of a BDD is the number of nodes of its graph. It heavily depends on the chosen variable ordering. Finding the optimal variable ordering is an NP-hard problem. We derive a 0/1 IP for finding an optimal variable ordering of a threshold BDD. This 0/1 IP formulation provides the basis for the computation of the variable ordering spectrum of a threshold function. We introduce our new tool azove 2.0 as an enhancement to azove 1.1 which is a tool for counting and enumerating 0/1 points. Computational results on benchmarks from the literature show the strength of our new method.     

LLL-reduction for integer knapsacks

Given a matrix A∈? ^m×n satisfying certain regularity assumptions, a well-known integer programming problem asks to find an integer point in the associated knapsack polytope or determine that no such point exists. We obtain an LLL-based polynomial time algorithm that solves the problem subject to a constraint on the location of the vector b.     

Subset sum problems with digraph constraints

We introduce and study optimization problems which are related to the well-known Subset Sum problem. In each new problem, a node-weighted digraph is given and one has to select a subset of vertices whose total weight does not exceed a given budget. Some additional constraints called digraph constraints and maximality need to be satisfied. The digraph constraint imposes that a node must belong to the solution if at least one of its predecessors is in the solution. An alternative of this constraint says that a node must belong to the solution if all its predecessors are in the solution. The maximality constraint ensures that no superset of a feasible solution is also feasible. The combination of these constraints provides four problems. We study their complexity and present some approximation results according to the type of input digraph, such as directed acyclic graphs and oriented trees.