We consider a class of random knapsack instances described by Chvátal, who showed that with probability going to 1, such instances require an exponential number of branch-and-bound nodes. We show that even with the use of simple lifted cover inequalities, an exponential number of nodes is required with probability going to 1.
DOI : 10.1016/j.disopt.2005.06.003 Anahtar Kelimeler :
Integer programming, Branch and bound, Average case, Cover inequality, Knapsack, Lifting
ISSN: 1572-5286 Sayı: 3 Cilt: 2 Sayfa: 219-228
Given a clustered graph (G,V), that is, a graph G=(V,E) together with a partition V of its vertex set, the selective coloring problem consists in choosing one vertex per cluster such that the chromatic number of the subgraph induced by the chosen vertices is minimum. This problem can be formulated as a covering problem with a 0–1 matrix M(G,V). Nevertheless, we observe that, given (G,V), it is NP-hard to check if M(G,V) is conformal (resp. perfect). We will give a sufficient condition, checkable in polynomial time, for M(G,V) to be conformal that becomes also necessary if conformality is required to be hereditary. Finally, we show that M(G,V) is perfect for every partition V if and only if G belongs to a superclass of threshold graphs defined with a complex function instead of a real one.
This note is meant to elucidate the difference between intersection cuts as originally defined, and intersection cuts as defined in the more recent literature. It also states a basic property of intersection cuts under their original definition.
Given a digraph D=(V,A) and a positive integer k, a subset B⊆A is called a k-arborescence, if it is the disjoint union of k spanning arborescences. When also arc-costs c:A→R are given, minimizing the cost of a k-arborescence is well-known to be tractable. In this paper we take on the following problem: what is the minimum cardinality of a set of arcs the removal of which destroys every minimum c-cost k-arborescence. Actually, the more general weighted problem is also considered, that is, arc weights w:A→R+ (unrelated to c) are also given, and the goal is to find a minimum weight set of arcs the removal of which destroys every minimum c-cost k-arborescence. An equivalent version of this problem is where the roots of the arborescences are fixed in advance. In an earlier paper (Bernáth and Pap, 2013) we solved this problem for k=1. This work reports on other partial results on the problem. We solve the case when both c and w are uniform—that is, find a minimum size set of arcs that covers all k-arborescences. Our algorithm runs in polynomial time for this problem. The solution uses a result of Bárász et al. (2005) saying that the family of so-called in-solid sets (sets with the property that every proper subset has a larger in-degree) satisfies the Helly-property, and thus can be (efficiently) represented as a subtree hypergraph. We also give an algorithm for the case when only c is uniform but w is not. This algorithm is only polynomial if k is not part of the input.
This work considers the graph partitioning problem known as maximum k-cut. It focuses on investigating features of a branch-and-bound method to obtain global solutions. An exhaustive experimental study is carried out for the two main components of a branch-and-bound algorithm: Computing bounds and branching strategies. In particular, we propose the use of a variable neighborhood search metaheuristic to compute good feasible solutions, the k-chotomic strategy to split the problem, and a branching rule based on edge weights to select variables. Moreover, we analyze a linear relaxation strengthened by semidefinite-based constraints, a cutting plane algorithm, and node selection strategies. Computational results show that the resulting method outperforms the state-of-the-art approach and discovers the solution of several instances, especially for problems with k≥5.
The two-dimensional bin packing problem is a generalization of the classical bin packing problem and is defined as follows. Given a collection of rectangles specified by their width and height, pack these into a minimum number of square bins of unit size. Recently, the problem was proved to be APX-hard even in the asymptotic case, i.e. when the optimum solutions require a large number of bins [N. Bansal, J. Correa, C. Kenyon, M. Sviridenko, Bin packing in multiple dimensions: Inapproximability results and approximation schemes, Math. Oper. Res. 31 (1) (2006) 31–49]. On the positive side, there exists a polynomial time algorithm that uses OPT bins whose sides have length (1+ϵ), where OPT denotes the number of unit sized bins used by the optimum solution [N. Bansal, J. Correa, C. Kenyon, M. Sviridenko, Bin packing in multiple dimensions: Inapproximability results and approximation schemes, Math. Oper. Res. 31 (1) (2006) 31–49]. A natural question that remains is the approximability of the problem when we are allowed to relax the size of the unit bins in only one dimension. In this paper, we show that there exists an asymptotic polynomial time approximation scheme for packing rectangles into bins of size 1×(1+ϵ).
DOI : 10.1016/j.disopt.2006.09.001 Anahtar Kelimeler :
Bin packing, Approximation scheme
ISSN: 1572-5286 Sayı: 2 Cilt: 4 Sayfa: 143-153
In this paper, we explore some basic questions on the complexity of training neural networks with ReLU activation function. We show that it is NP-hard to train a two-hidden layer feedforward ReLU neural network. If dimension of the input data and the network topology is fixed, then we show that there exists a polynomial time algorithm for the same training problem. We also show that if sufficient over-parameterization is provided in the first hidden layer of ReLU neural network, then there is a polynomial time algorithm which finds weights such that output of the over-parameterized ReLU neural network matches with the output of the given data.
A k-club is a distance-based graph-theoretic generalization of a clique, originally introduced to model cohesive social subgroups in social network analysis. The k-clubs represent low diameter clusters in graphs and are appropriate for various graph-based data mining applications. Unlike cliques, the k-club model is nonhereditary, meaning every subset of a k-club is not necessarily a k-club. In this article, we settle an open problem establishing the intractability of testing inclusion-wise maximality of k-clubs. This result is in contrast to polynomial-time verifiability of maximal cliques, and is a direct consequence of its nonhereditary nature. We also identify a class of graphs for which this problem is polynomial-time solvable. We propose a distance coloring based upper-bounding scheme and a bounded enumeration based lower-bounding routine and employ them in a combinatorial branch-and-bound algorithm for finding maximum cardinality k-clubs. Computational results from using the proposed algorithms on 200-vertex graphs are also provided.
DOI : 10.1016/j.disopt.2012.02.002 Anahtar Kelimeler :
Clique, k-club, Exact combinatorial algorithms, Graph-based data mining, Social network analysis
ISSN: 1572-5286 Sayı: 2 Cilt: 9 Sayfa: 84-97
This paper deals with the problem of locating an extensive facility of restricted length within a given tree network. Topologically, the selected extensive facility is a subtree. The nestedness property means that a solution of a problem with a shorter length constraint is part of a solution of the same problem with a longer length constraint. We prove the existence of a nestedness property for a common family of convex ordered median (COM) objective functions. We start with the proof of the nestedness property for a rooted tree problem, where the extended facility is a subtree of some tree network rooted at a specified node, and proceed to prove the nestedness property for the general location model on a tree.
We describe an effective method for doing binary-encoded modeling, in the context of 0/1 linear programming, when the number of feasible configurations is not a power of two. Our motivation comes from modeling all-different restrictions.
DOI : 10.1016/j.disopt.2005.06.001 Anahtar Kelimeler :
Polytope, Integer programming, Coloring, All different
ISSN: 1572-5286 Sayı: 3 Cilt: 2 Sayfa: 190-200
We consider the resource-constrained scheduling problem when each job’s resource requirements remain constant over its processing time. We study a time-indexed formulation of the problem, providing facet-defining inequalities for a projection of the resulting polyhedron that exploit the resource limitations inherent in the problem. Lifting procedures are then provided for obtaining strong valid inequalities for the original polyhedron. Computational results are presented to demonstrate the strength of these inequalities.
This paper addresses an Electric Vehicle Relocation Problem (E-VReP), in one-way carsharing systems, based on operators who use folding bicycles to facilitate vehicle relocation. In order to calculate the economic sustainability of this relocation approach, a revenue associated with each relocation request satisfied and a cost associated with each operator used are introduced. The new optimization objective maximizes the total profit. To overcome the drawback of the high CPU time required by the Mixed Integer Linear Programming formulation of the E-VReP, two heuristic algorithms, based on the general properties of the feasible solutions, are designed. Their effectiveness is tested on two sets of realistic instances. In the first, all the requests have the same revenue, while, in the second, the revenue of each request has a variable component related to the user’s rent-time and a fixed part related to customer satisfaction. Finally, a sensitivity analysis is carried out on both the number of requests and the fixed revenue component.
DOI : 10.1016/j.disopt.2016.12.001 Anahtar Kelimeler :
Carsharing, Operator based relocation, Economic sustainability, Pick-up and delivery problem with time windows, Mixed integer linear programming, Ruin and Recreate metaheuristic
ISSN: 1572-5286 Cilt: 23 Sayfa: 56-80
Stable multi-sets are an integer extension of stable sets in graphs. In this paper, we continue our investigations started by Koster and Zymolka [Stable multi-sets, Math. Methods Oper. Res. 56(1) (2002) 45–65]. We present further results on the stable multi-set polytope and discuss their computational impact. The polyhedral investigations focus on the cycle inequalities. We strengthen their facet characterization and show that chords need not weaken the cycle inequality strength in the multi-set case. This also helps to derive a valid right hand side for clique inequalities. The practical importance of the cycle inequalities is evaluated in a computational study. For this, we revisit existing polynomial time separation algorithms. The results show that the performance of state-of-the-art integer programming solvers can be improved by exploiting this general structure.
This paper investigates the polytope associated with the classical standard linearization technique for the unconstrained optimization of multilinear polynomials in 0–1 variables. A new class of valid inequalities, called 2-links, is introduced to strengthen the LP relaxation of the standard linearization. The addition of the 2-links to the standard linearization inequalities provides a complete description of the convex hull of integer solutions for the case of functions consisting of at most two nonlinear monomials. For the general case, various computational experiments show that the 2-links improve both the standard linearization bound and the computational performance of exact branch & cut methods. The improvements are especially significant for a class of instances inspired from the image restoration problem in computer vision. The magnitude of this effect is rather surprising in that the 2-links are in relatively small number (quadratic in the number of terms of the objective function).
Conflict analysis for infeasible subproblems is one of the key ingredients in modern SAT solvers. In contrast, it is common practice for today’s mixed integer programming solvers to discard infeasible subproblems and the information they reveal. In this paper, we try to remedy this situation by generalizing SAT infeasibility analysis to mixed integer programming. We present heuristics for branch-and-cut solvers to generate valid inequalities from the current infeasible subproblem and the associated branching information. SAT techniques can then be used to strengthen the resulting constraints. Extensive computational experiments show the potential of our method. Conflict analysis greatly improves the performance on particular models, while it does not interfere with the solving process on the other instances. In total, the number of required branching nodes on general MIP instances was reduced by 18% in the geometric mean, and the solving time was reduced by 11%. On infeasible MIPs arising in the context of chip verification and on a model for a particular combinatorial game, the number of nodes was reduced by 80%, thereby reducing the solving time by 50%.
We introduce a general technique for creating an extended formulation of a mixed-integer program. We classify the integer variables into blocks, each of which generates a finite set of vector values. The extended formulation is constructed by creating a new binary variable for each generated value. Initial experiments show that the extended formulation can have a more compact complete description than the original formulation. We prove that, using this reformulation technique, the facet description decomposes into one “linking polyhedron” per block and the “aggregated polyhedron”. Each of these polyhedra can be analyzed separately. For the case of identical coefficients in a block, we provide a complete description of the linking polyhedron and a polynomial-time separation algorithm. Applied to the knapsack with a fixed number of distinct coefficients, this theorem provides a complete description in an extended space with a polynomial number of variables. On the basis of this theory, we propose a new branching scheme that analyzes the problem structure. It is designed to be applied in those subproblems of hard integer programs where LP-based techniques do not provide good branching decisions. Preliminary computational experiments show that it is successful for some benchmark problems of multi-knapsack type.
Semidefinite relaxations of certain combinatorial optimization problems lead to approximation algorithms with performance guarantees. For large-scale problems, it may not be computationally feasible to solve the semidefinite relaxations to optimality. In this paper, we investigate the effect on the performance guarantees of an approximate solution to the semidefinite relaxation for MaxCut, Max2Sat, and Max3Sat. We show that it is possible to make simple modifications to the approximate solutions and obtain performance guarantees that depend linearly on the most negative eigenvalue of the approximate solution, the size of the problem, and the duality gap. In every case, we recover the original performance guarantees in the limit as the solution approaches the optimal solution to the semidefinite relaxation.
The simple graph partitioning problem is to partition an edge-weighted graph into mutually node-disjoint subgraphs, each containing at most b nodes, such that the sum of the weights of all edges in the subgraphs is maximal. In this paper we provide several classes of facet-defining inequalities for the associated simple graph partitioning polytope.
An important problem that commonly arises in areas such as internet traffic-flow analysis, phylogenetics and electrical circuit design, is to find a representation of any given metric D on a finite set by an edge-weighted graph, such that the total edge length of the graph is minimum over all such graphs. Such a graph is called an optimal realization and finding such realizations is known to be NP-hard. Recently Varone presented a heuristic greedy algorithm for computing optimal realizations. Here we present an alternative heuristic that exploits the relationship between realizations of the metric D and its so-called tight span TD. The tight span TD is a canonical polytopal complex that can be associated to D, and our approach explores parts of TD for realizations in a way that is similar to the classical simplex algorithm. We also provide computational results illustrating the performance of our approach for different types of metrics, including l1-distances and two-decomposable metrics for which it is provably possible to find optimal realizations in their tight spans.
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.
The longest and Hamiltonian path problems are well-known NP-hard problems in graph theory. Despite many applications of these problems, they are still open for many classes of graphs, including solid grid graphs and grid graphs with some holes. We consider the longest and Hamiltonian (s,t)-path problems in C-shaped grid graphs. A (s,t)-path is a path between two given vertices s and t of the graph. A C-shaped grid graph is a rectangular grid graph such that a rectangular grid subgraph is removed from it to make a C-liked shape. In this paper, we first give the necessary conditions for the existence of Hamiltonian cycles and Hamiltonian (s,t)-paths in such graphs. Then by given a linear-time algorithm for finding Hamiltonian cycles and Hamiltonian (s,t)-paths, we show that these necessary conditions are also sufficient. Finally, we give a linear-time algorithm for finding the longest (s,t)-path in these graphs.
A prevailing feature of mobile telephony systems is that the location of a mobile user may be unknown. Therefore, when the system has to establish a call between users, it may need to search (or page) all the cells that it suspects the users may be located in, in order to find the cells where the users currently reside. The searching process consumes expensive wireless links which motivate search techniques that page as few cells as possible. We consider cellular systems with n cells and m mobile users roaming among the cells. The location of the users is uncertain and is given by m probability distribution vectors. Whenever the system needs to find the users, it conducts a search operation lasting at most d rounds. In each round the system may check an arbitrary subset of cells to see which users are located there. The problem of finding a single user (that is, the case m=1) is known to be polynomially solvable, whereas the problem of finding any other constant number of users ( m≥2) in any fixed (constant) number of rounds (at least two rounds) is known to be NP-hard. In this paper we present a polynomial-time approximation scheme for this problem with a constant number of rounds and a constant number of users. This result improves an earlier ee−1∼1.581977-approximation of Bar-Noy and Malewicz (that applies to any number of users and rounds).
DOI : 10.1016/j.disopt.2007.11.004 Anahtar Kelimeler :
Polynomial-time approximation scheme, Mobile telephony networks
ISSN: 1572-5286 Sayı: 1 Cilt: 5 Sayfa: 88-96
Pivot and Shift is an extension to general mixed integer programming of Pivot and Complement, the well-known 1980s heuristic for pure 0–1 programs. It is essentially a sophisticated rounding procedure, amended with two variants of a neighborhood search. The rounding takes the form of several pivot types meant to eliminate from the basis all integer-constrained variables while keeping the objective function value close to the LP optimum, followed by up and down shifts in the value of the nonbasic integer variables. The neighborhood search is akin to the local branching procedure proposed by Fischetti and Lodi. When Pivot and Shift is joined to an efficient MIP solver, the combined procedure finds better solutions faster than the MIP solver alone. The procedure has been tested on a multitude of test problems available from the literature or the web.
DOI : 10.1016/j.disopt.2004.03.001 Anahtar Kelimeler :
Heuristics, Mixed integer programming, Pivot and complement, Neighborhood search, Local branching
ISSN: 1572-5286 Sayı: 1 Cilt: 1 Sayfa: 3-12