Sensitivity analysis to perturbations of the weight of a subset of items: The knapsack case study

In this paper, we study the sensitivity of the optimum to perturbations of the weight of a subset of items of both the knapsack problem (denoted KP) and knapsack sharing problem (denoted KSP). The sensitivity interval of the weight associated to an item is characterized by two limits, called lower and upper values, which guarantee the optimality of the solution at hand whenever the new weight’s value belongs to such an interval. For each perturbed weight, we try to establish approximate values of the sensitivity interval whenever the original problem is solved. We do it by applying a dynamic programming method where all established results require a negligible runtime. First, two cases are studied when considering an optimal solution of KP: (i) the case in which all perturbations are (non)negatives and (ii) the general case in which the set of the perturbed items is divided into two disjoint subsets (the first subset contains the nonnegative perturbations and the second one represents the subset of negative perturbations). Second, we show how we can adapt the results of KP to the KSP. All established results require a negligible runtime which grows the interest of such a study. Finally, for each of these problems, we will see the impact of the established results on an example while considering the various cases.     

Heuristic and Exact Algorithms for the Precedence-Constrained Knapsack Problem

The knapsack problem (KP) is generalized taking into account a precedence relation between items. Such a relation can be represented by means of a directed acyclic graph, where nodes correspond to items in a one-to-one way. As in ordinary KPs, each item is associated with profit and weight, the knapsack has a fixed capacity, and the problem is to determine the set of items to be included in the knapsack. However, each item can be adopted only when all of its predecessors have been included in the knapsack. The knapsack problem with such an additional set of constraints is referred to as the precedence-constrained knapsack problem (PCKP). We present some dynamic programming algorithms that can solve small PCKPs to optimality, as well as a preprocessing method to reduce the size of the problem. Combining these, we are able to solve PCKPs with up to 2000 items in less than a few minutes of CPU time.     

Highway games on weakly cyclic graphs

A highway problem is determined by a connected graph which provides all potential entry and exit vertices and all possible edges that can be constructed between vertices, a cost function on the edges of the graph and a set of players, each in need of constructing a connection between a specific entry and exit vertex. Mosquera (2007) introduce highway problems and the corresponding cooperative cost games called highway games to address the problem of fair allocation of the construction costs in case the underlying graph is a tree. In this paper, we study the concavity and the balancedness of highway games on weakly cyclic graphs. A graph G is called highway-game concave if for each highway problem in which G is the underlying graph the corresponding highway game is concave. We show that a graph is highway-game concave if and only if it is weakly triangular. Moreover, we prove that highway games on weakly cyclic graphs are balanced.     

An adaptive stochastic knapsack problem

We consider a stochastic knapsack problem in which the event of overflow results in the problem ending with zero return. We assume that there are n   types of items available where each type has infinite supply. An item has an exponentially distributed random weight with a known mean depending on its type and the item’s value is proportional to its weight with a given factor depending on the item’s type. We have to make a decision on each stage whether to stop, or continue to put an item of a selected type in the knapsack. An item’s weight is learned when placed to the knapsack. The objective of this problem is to find a policy that maximizes the expected total values. Using the framework of dynamic programming, the optimal policy is found when n=2$n=2$ and a heuristic policy is suggested for n>2$n>2$.     

On the maximum cardinality search lower bound for treewidth

The Maximum Cardinality Search (MCS) algorithm visits the vertices of a graph in some order, such that at each step, an unvisited vertex that has the largest number of visited neighbours becomes visited. A maximum cardinality search ordering (MCS-ordering) of a graph is an ordering of the vertices that can be generated by the MCS algorithm. The visited degree of a vertex v in an MCS-ordering is the number of neighbours of v that are before v in the ordering. The visited degree of an MCS-ordering ψ of G is the maximum visited degree over all vertices v in ψ. The maximum visited degree over all MCS-orderings of graph G is called its maximum visited degree. Lucena [A new lower bound for tree-width using maximum cardinality search, SIAM J. Discrete Math. 16 (2003) 345-353] showed that the treewidth of a graph G is at least its maximum visited degree.We show that the maximum visited degree is of size O(logn) for planar graphs, and give examples of planar graphs G with maximum visited degree k with O(k!) vertices, for all k∈N. Given a graph G, it is NP-complete to determine if its maximum visited degree is at least k, for any fixed k?7. Also, this problem does not have a polynomial time approximation algorithm with constant ratio, unless P=NP. Variants of the problem are also shown to be NP-complete.In this paper, we also propose some heuristics for the problem, and report on an experimental analysis of them. Several tiebreakers for the MCS algorithm are proposed and evaluated. We also give heuristics that give upper bounds on the value of the maximum visited degree of a graph, which appear to give results close to optimal on many graphs from real life applications.     

Revisiting surrogate relaxation for the multidimensional knapsack problem

The multidimensional knapsack problem (MKP) is a classic problem in combinatorial optimisation. Several authors have proposed to use surrogate relaxation to compute upper bounds for the MKP. In their papers, the surrogate dual is solved heuristically. We show that, using a modern dual simplex solver as a subroutine, one can solve the surrogate dual exactly in reasonable computing times. On the other hand, the resulting upper bound tends to be strong only for relatively small MKP instances.     

Secure sets and their expansion in cubic graphs

Consider a graph whose vertices play the role of members of the opposing groups. The edge between two vertices means that these vertices may defend or attack each other. At one time, any attacker may attack only one vertex. Similarly, any defender fights for itself or helps exactly one of its neighbours. If we have a set of defenders that can repel any attack, then we say that the set is secure. Moreover, it is strong if it is also prepared for a raid of one additional foe who can strike anywhere. We show that almost any cubic graph of order n has a minimum strong secure set of cardinality less or equal to n/2 + 1. Moreover, we examine the possibility of an expansion of secure sets and strong secure sets.     

A reactive local search-based algorithm for the disjunctively constrained knapsack problem

In this paper, we propose a reactive local search-based algorithm for the disjunctively constrained knapsack problem (DCKP). DCKP is a variant of the standard knapsack problem, an NP-hard combinatorial optimization problem, with special disjunctive constraints. A disjunctive constraint is a couple of items for which only one item is packed. The proposed algorithm is based upon a reactive local search, where an explicit check for the repetition of configurations is added to the search process. Initially, two complementary greedy procedures are applied in order to construct a starting solution. Second, a degrading procedure is introduced in order (i) to escape to local optima and (ii) to introduce a diversification in the search space. Finally, a memory list is added in order to forbid the repetition of configurations. The performance of two versions of the algorithm has been evaluated on several problem instances and compared to the results obtained by running the Cplex solver. Encouraging results have been obtained.     

Uniquely pairable graphs

The concept of a k-pairable graph was introduced by Z. Chen [On k-pairable graphs, Discrete Mathematics 287 (2004), 11-15] as an extension of hypercubes and graphs with an antipodal isomorphism. In the present paper we generalize further this concept of a k-pairable graph to the concept of a semi-pairable graph. We prove that a graph is semi-pairable if and only if its prime factor decomposition contains a semi-pairable prime factor or some repeated prime factors. We also introduce a special class of k-pairable graphs which are called uniquely k-pairable graphs. We show that a graph is uniquely pairable if and only if its prime factor decomposition has at least one pairable prime factor, each prime factor is either uniquely pairable or not semi-pairable, and all prime factors which are not semi-pairable are pairwise non-isomorphic. As a corollary we give a characterization of uniquely pairable Cartesian product graphs.     

Extending Dantzig's bound to the bounded multiple-class binary Knapsack problem

 The bounded multiple-class binary knapsack problem is a variant of the knapsack problem where the items are partitioned into classes and the item weights in each class are a multiple of a class weight. Thus, each item has an associated multiplicity. The constraints consists of an upper bound on the total item weight that can be selected and upper bounds on the total multiplicity of items that can be selected in each class. The objective is to maximize the sum of the profits associated with the selected items. This problem arises as a sub-problem in a column generation approach to the cutting stock problem. A special case of this model, where item profits are restricted to be multiples of a class profit, corresponds to the problem obtained by transforming an integer knapsack problem into a 0-1 form. However, the transformation proposed here does not involve a duplication of solutions as the standard transformation typically does. The paper shows that the LP-relaxation of this model can be solved by a greedy algorithm in linear time, a result that extends those of Dantzig (1957) and Balas and Zemel (1980) for the 0-1 knapsack problem. Hence, one can derive exact algorithms for the multi-class binary knapsack problem by adapting existing algorithms for the 0-1 knapsack problem. Computational results are reported that compare solving a bounded integer knapsack problem by transforming it into a standard binary knapsack problem versus using the multiple-class model as a 0-1 form. Received: May 1998 / Accepted: February 2002-09-04 Published online: December 9, 2002 Key Words. Knapsack problem – integer programming – linear programming relaxation     

A polyhedral study of the semi-continuous knapsack problem

We study the convex hull of the feasible set of the semi-continuous knapsack problem, in which the variables belong to the union of two intervals. Such structure arises in a wide variety of important problems, e.g. blending and portfolio selection. We show how strong inequalities valid for the semi-continuous knapsack polyhedron can be derived and used in a branch-and-cut scheme for problems with semi-continuous variables. To demonstrate the effectiveness of these inequalities, which we call collectively semi-continuous cuts, we present computational results on real instances of the unit commitment problem, as well as on a number of randomly generated instances of linear programming with semi-continuous variables.     

Vertex colorings without isolates

Call a vertex of a vertex-colored simple graph isolated if all its neighbors have colors other than its own. A. J. Goldman has asked: When is it possible to color b vertices of a graph black and the remaining w vertices white so that no vertex is isolated? We prove (1) if G is connected and has minimum degree 2, it is always possible unless b or w is 1; (2) if G is 2-connected, then for any pair (b, w) there is a coloring in which both monochromatic subgraphs are connected; (3) if G has vertices of degree 1, a necessary condition for a (b, w) coloring without isolates to exist is that there be a solution to a certain knapsack inequality. Next, statements generalizing (1) and (2) to n colors are presented, and current knowledge about their truth is discussed. Then various refinements of (1) and (3), more complicated to state and prove, are given. For instance, with the hypotheses of (1) at least one of the monochromatic subgraphs may be chosen to be connected. Also, the necessary knapsack inequality of (3) is, in most cases, sufficient. Throughout, some consideration is given to the algorithmic complexity of coloring (if possible) without isolates. For most graphs which might arise in practice there is an efficient algorithm for the 2-color problem. However, for arbitrary graphs the 2-(or more) color problem is NP-complete.     

Characterizations of 2-variegated graphs and of 3-variegated graphs

A graph is said to be k-variegated if its vertex set can be partitioned into k equal parts such that each vertex is adjacent to exactly one vertex from every other part not containing it. We prove that a graph G on 2n vertices is 2-variegated if and only if there exists a set S of n independent edges in G such that no cycle in G contains an odd number of edges from S. We also characterize 3-variegated graphs.     

Path factors and parallel knock-out schemes of almost claw-free graphs

An H₁,{H₂}-factor of a graph G is a spanning subgraph of G with exactly one component isomorphic to the graph H₁ and all other components (if there are any) isomorphic to the graph H₂. We completely characterise the class of connected almost claw-free graphs that have a P₇,{P₂}-factor, where P₇ and P₂ denote the paths on seven and two vertices, respectively. We apply this result to parallel knock-out schemes for almost claw-free graphs. These schemes proceed in rounds in each of which each surviving vertex eliminates one of its surviving neighbours. A graph is reducible if such a scheme eliminates every vertex in the graph. Using our characterisation, we are able to classify all reducible almost claw-free graphs, and we can show that every reducible almost claw-free graph is reducible in at most two rounds. This leads to a quadratic time algorithm for determining if an almost claw-free graph is reducible (which is a generalisation and improvement upon the previous strongest result that showed that there was a O(n^5.376) time algorithm for claw-free graphs on n vertices).     

Knapsack with variable weights satisfying linear constraints

We introduce a variant of the knapsack problem, in which the weights of items are also variables but must satisfy a system of linear constraints, and the capacity of knapsack is given and known. We discuss two models: (1) the value of each item is given; (2) the value-to-weight ratio of each item is given. The goal is to determine the weight of each item, and to find a subset of items such that the total weight is no more than the capacity and the total value is maximized. We provide several practical application scenarios that motivate our study, and then investigate the computational complexity and corresponding algorithms. In particular, we show that if the number of constraints is a fixed constant, then both problems can be solved in polynomial time. If the number of constraints is an input, then we show that the first problem is NP-Hard and cannot be approximated within any constant factor unless \(\mathrm{P}= \mathrm{NP}\), while the second problem is NP-Hard but admits a polynomial time approximation scheme. We further propose approximation algorithms for both problems, and extend the results to multiple knapsack cases with a fixed number of knapsacks and identical capacities.     

Greedy algorithm for the general multidimensional knapsack problem

In this paper, we propose a new greedy-like heuristic method, which is primarily intended for the general MDKP, but proves itself effective also for the 0-1 MDKP. Our heuristic differs from the existing greedy-like heuristics in two aspects. First, existing heuristics rely on each item’s aggregate consumption of resources to make item selection decisions, whereas our heuristic uses the effective capacity, defined as the maximum number of copies of an item that can be accepted if the entire knapsack were to be used for that item alone, as the criterion to make item selection decisions. Second, other methods increment the value of each decision variable only by one unit, whereas our heuristic adds decision variables to the solution in batches and consequently improves computational efficiency significantly for large-scale problems. We demonstrate that the new heuristic significantly improves computational efficiency of the existing methods and generates robust and near-optimal solutions. The new heuristic proves especially efficient for high dimensional knapsack problems with small-to-moderate numbers of decision variables, usually considered as “hard” MDKP and no computationally efficient heuristic is available to treat such problems. Supported in part by the NSF grant DMI 9812994.     

On Integral Sum Graphs

A graph G is said to be an integral sum graph if its nodes can be given a labeling f with distinct integers, so that for any two distinct nodes u and v of G, uv is an edge of G if and only if f(u)+f(v) = f(w) for some node w in G. A node of G is called a saturated node if it is adjacent to every other node of G. We show that any integral sum graph which is not K₃ has at most two saturated nodes. We determine the structure for all integral sum graphs with exactly two saturated nodes, and give an upper bound for the number of edges of a connected integral sum graph with no saturated nodes. We introduce a method of identification on constructing new connected integral sum graphs from given integral sum graphs with a saturated node. Moreover, we show that every graph is an induced subgraph of a connected integral sum graph. Miscellaneous relative results are also presented.     

A contribution to queens graphs: A substitution method

A graph G is a queens graph if the vertices of G can be mapped to queens on the chessboard such that two vertices are adjacent if and only if the corresponding queens attack each other, i.e. they are in horizontal, vertical or diagonal position.We prove a conjecture of Beineke, Broere and Henning that the Cartesian product of an odd cycle and a path is a queens graph. We show that the same does not hold for two odd cycles. The representation of the Cartesian product of an odd cycle and an even cycle remains an open problem.We also prove constructively that any finite subgraph of the rectangular grid or the hexagonal grid is a queens graph.Using a small computer search we solve another conjecture of the authors mentioned above, saying that K_3,4 minus an edge is a minimal non-queens graph.     

On integral sum graphs

A graph G is said to be an integral sum graph if its nodes can be given a labeling f with distinct integers, so that for any two distinct nodes u and v of G, uv is an edge of G if and only if f(u)+f(v)=f(w) for some node w in G. A node of G is called a saturated node if it is adjacent to every other node of G. We show that any integral sum graph which is not K₃ has at most two saturated nodes. We determine the structure for all integral sum graphs with exactly two saturated nodes, and give an upper bound for the number of edges of a connected integral sum graph with no saturated nodes. We introduce a method of identification on constructing new connected integral sum graphs from given integral sum graphs with a saturated node. Moreover, we show that every graph is an induced subgraph of a connected integral sum graph. Miscellaneous related results are also presented.     

On CCE graphs of doubly partial orders

Let D be a digraph. The competition-common enemy graph (CCE graph) of D has the same set of vertices as D and an edge between vertices u and v if and only if there are vertices w and x in D such that (w,u), (w,v), (u,x), and (v,x) are arcs of D. We call a graph a CCE graph if it is the CCE graph of some digraph. In this paper, we show that if the CCE graph of a doubly partial order does not contain C₄ as an induced subgraph, it is an interval graph. We also show that any interval graph together with enough isolated vertices is the CCE graph of some doubly partial order.