A branch-and-bound (BB) tree certifies a dual bound on the value of an integer program. In this work, we introduce the tree compression problem (TCP): Given a BB tree T that certifies a dual bound, can we obtain a sma...
详细信息
ISBN:
(纸本)9783031327254;9783031327261
A branch-and-bound (BB) tree certifies a dual bound on the value of an integer program. In this work, we introduce the tree compression problem (TCP): Given a BB tree T that certifies a dual bound, can we obtain a smaller tree withthe same (or stronger) bound by either (1) applying a different disjunction at some node in T or (2) removing leaves from T? We believe such post-hoc analysis of BB trees may assist in identifying helpful general disjunctions in BB algorithms. We initiate our study by considering computational complexity and limitations of TCP. We then conduct experiments to evaluate the compressibility of realistic branch-and-bound trees generated by commonly-used branching strategies, using both an exact and a heuristic compression algorithm.
Cutting plane methods are widely used for solving convex optimization problems and are of fundamental importance, e.g., to provide tight bounds for Mixed-integer Programs (MIPs). this is obtained by embedding a cut-se...
详细信息
ISBN:
(纸本)9783642135194
Cutting plane methods are widely used for solving convex optimization problems and are of fundamental importance, e.g., to provide tight bounds for Mixed-integer Programs (MIPs). this is obtained by embedding a cut-separation module within a search scheme. the importance of a sound search scheme is well known in the Constraint programming (CP) community. Unfortunately, the "standard" search scheme typically used for MIP problems, known as the Kelley method, is often quite unsatisfactory because of saturation issues. In this paper we address the so-called Lift-and-Project closure for 0-1 MIPs associated with all disjunctive cuts generated from a given set of elementary disjunction. We focus on the search scheme embedding the generated cuts. In particular, we analyze a general meta-scheme for cutting plane algorithms, called in-out search, that was recently proposed by Ben-Ameur and Neto [1]. Computational results on test instances from the literature are presented, showing that using a more clever meta-scheme on top of a black-box cut generator may lead to a significant improvement.
We present a class of problems that arise in the design of the Next Generation Access Networks. the main features of these networks are: to be based on fiber links of relatively long length with respect to traditional...
详细信息
ISBN:
(纸本)9783642135194
We present a class of problems that arise in the design of the Next Generation Access Networks. the main features of these networks are: to be based on fiber links of relatively long length with respect to traditional copper based networks, users may be reached directly by fibers, and the presence of few central offices managing a large number of users. We present an integerprogramming model that captures the technological constraints and the deployment costs. the model serves as a basis for a decision support tool in the design of the Next Generation Access Networks. Pure integerprogramming cannot handle real-life problem instances, giving rise to new challenges and opportunities for hybrid Constraint programming-Mathematical programming methods. In this paper, we compare a LP-based randomized rounding algorithm with a Constraint-based Local Search formulation. the use of an LP relaxation is twofold: it gives lower bounds to the optimal solution, and it is easily embedded into a randomized rounding algorithm. the Constraint-based Local Search algorithm is then exploited to explore the set of feasible solutions. Withthese algorithms we are able to solve real-life instances for one of the problems presented in this paper.
the perceptron algorithm for linear programming, arising from machine learning, has been around since the 1950s. While not a polynomial-time algorithm, it is useful in practice due to its simplicity and robustness. In...
详细信息
ISBN:
(纸本)9783319592503;9783319592497
the perceptron algorithm for linear programming, arising from machine learning, has been around since the 1950s. While not a polynomial-time algorithm, it is useful in practice due to its simplicity and robustness. In 2004, Dunagan and Vempala showed that a randomized rescaling turns the perceptron method into a polynomial time algorithm, and later Pena and Soheili gave a deterministic rescaling. In this paper, we give a deterministic rescaling for the perceptron algorithm that improves upon the previous rescaling methods by making it possible to rescale much earlier. this results in a faster running time for the rescaled perceptron algorithm. We will also demonstrate that the same rescaling methods yield a polynomial time algorithm based on the multiplicative weights update method. this draws a connection to an area that has received a lot of recent attention in theoretical computer science.
the 'exact subgraph' approach was recently introduced as a hierarchical scheme to get increasingly tight semidefinite programming relaxations of several NP-hard graph optimization problems. Solving these relax...
详细信息
ISBN:
(数字)9783030179533
ISBN:
(纸本)9783030179533;9783030179526
the 'exact subgraph' approach was recently introduced as a hierarchical scheme to get increasingly tight semidefinite programming relaxations of several NP-hard graph optimization problems. Solving these relaxations is a computational challenge because of the potentially large number of violated subgraph constraints. We introduce a computational framework for these relaxations designed to cope withthese difficulties. We suggest a partial Lagrangian dual, and exploit the fact that its evaluation decomposes into two independent subproblems. this opens the way to use the bundle method from non-smoothoptimization to minimize the dual function. Computational experiments on the Max-Cut, stable set and coloring problem show the efficiency of this approach.
the simplex algorithm is one of the most popular algorithms to solve linear programs (LPs). Starting at an extreme point solution of an LP, it performs a sequence of basis exchanges (called pivots) that allows one to ...
详细信息
ISBN:
(纸本)9783031598340;9783031598357
the simplex algorithm is one of the most popular algorithms to solve linear programs (LPs). Starting at an extreme point solution of an LP, it performs a sequence of basis exchanges (called pivots) that allows one to move to a better extreme point along an improving edge-direction of the underlying polyhedron. A key issue in the simplex algorithm's performance is degeneracy, which may lead to a (potentially long) sequence of basis exchanges which do not change the current extreme point solution. In this paper, we prove that it is always possible to limit the number of consecutive degenerate pivots that the simplex algorithm performs to n - m - 1, where n is the number of variables and m is the number of equality constraints of a given LP in standard equality form.
Mixed-integer Programs (MIP's) involving logical implications modelled through big-M coefficients, are notoriously among the hardest to solve. In this paper we propose and analyze computationally an automatic prob...
详细信息
ISBN:
(纸本)3540221131
Mixed-integer Programs (MIP's) involving logical implications modelled through big-M coefficients, are notoriously among the hardest to solve. In this paper we propose and analyze computationally an automatic problem reformulation of quite general applicability, aimed at removing the model dependency on the big-M coefficients. Our solution scheme defines a master integer Linear Problem (ILP) with no continuous variables, which contains combinatorial information on the integer-variable feasible combinations that can be "distilled" from the original MIP model. the master solutions are sent to a slave Linear Program (LP), which validates them and possibly returns combinatorial inequalities to be added to the current master ILP. the inequalities are associated to minimal (or irreducible) infeasible subsystems of a certain linear system, and can be separated efficiently in case the master solution is integer. this produces an LP relaxation of the master problem which can be considerably tighter than the one associated with original MIP formulation. Computational results on two specific classes of hard-to-solve MIP's indicate the new method produces a reformulation which can be solved some orders of magnitude faster than the original MIP model.
For a given set X ⊆ Z d of integer points, we investigate the smallest number of facets of any polyhedron whose set of integer points is conv(X) ∩ Z d . this quantity, which we call the relaxation complexity of X, co...
详细信息
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. Besides being important in its own right, the semi-continuous knapsack...
详细信息
ISBN:
(纸本)3540221131
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. Besides being important in its own right, the semi-continuous knapsack problem is a relaxation of general mixed-integerprogramming. We show how strong inequalities that are valid for the semi-continuous knapsack polyhedron can be derived and used as cuts in a branch-and-cut scheme for mixed-integerprogramming anal problems with semi-continuous variables. We present computational results that demonstrate the effectiveness of these inequalities, which we call collectively semi-continuous cuts. Our computational experience also shows that dealing with semi-continuous constraints directly in the branch-and-cut algorithm through a specialized branching scheme and semi-continuous cuts is considerably more practical than the "textbook" approach of modeling semi-continuous constraints through the introduction of auxiliary binary variables in the model.
暂无评论