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.
We extend the theoretical foundations of the branch-and-cut method using lift-and-project cuts for a broader class of disjunctive constraints, and also present a new, substantially improved disjunctive cut generator. ...
详细信息
ISBN:
(纸本)354064590X
We extend the theoretical foundations of the branch-and-cut method using lift-and-project cuts for a broader class of disjunctive constraints, and also present a new, substantially improved disjunctive cut generator. Employed together with an efficient commercial MIP solver, our code is a robust, general purpose method for solving mixed integer programs. We present extensive computational experience withthe most difficult problems in the MIPLIB library.
We start with definitions given by Plotkin, Shmoys, and Tardos [16]. Given A∈?m×n, b∈?m and a polytope P $
 \subseteq$
 \subseteq ? n , the fractional packing problem is to find an x ∈ P such t...
ISBN:
(纸本)3540660194
We start with definitions given by Plotkin, Shmoys, and Tardos [16]. Given A∈?m×n, b∈?m and a polytope P $
\subseteq$
\subseteq ? n , the fractional packing problem is to find an x ∈ P such that Ax ≤ b if such an x exists. An ∈-approximate solution to this problem is an x ∈ P such that Ax ≤ (1+∈)b. An ∈-relaxed decision procedure always finds an ∈-approximate solution if an exact solution exists.
We examine how sparse feasible solutions of integer programs are, on average. Average case here means that we fix the constraint matrix and vary the right-hand side vectors. For a problem in standard form with m equat...
详细信息
ISBN:
(纸本)9783030179533;9783030179526
We examine how sparse feasible solutions of integer programs are, on average. Average case here means that we fix the constraint matrix and vary the right-hand side vectors. For a problem in standard form with m equations, there exist LP feasible solutions with at most m many nonzero entries. We show that under relatively mild assumptions, integer programs in standard form have feasible solutions with O(m) many nonzero entries, on average. Our proof uses ideas from the theory of groups, lattices, and Ehrhart polynomials. From our main theorem we obtain the best known upper bounds on the integer Caratheodory number provided that the determinants in the data are small.
Software for mixed-integer linear programming can return incorrect results for a number of reasons, one being the use of inexact floating-point arithmetic. Even solvers that employ exact arithmetic may suffer from pro...
详细信息
ISBN:
(数字)9783319592503
ISBN:
(纸本)9783319592503;9783319592497
Software for mixed-integer linear programming can return incorrect results for a number of reasons, one being the use of inexact floating-point arithmetic. Even solvers that employ exact arithmetic may suffer from programming or algorithmic errors, motivating the desire for a way to produce independently verifiable certificates of claimed results. Due to the complex nature of state-of-the-art MIP solution algorithms, the ideal form of such a certificate is not entirely clear. this paper proposes such a certificate format designed with simplicity in mind, which is composed of a list of statements that can be sequentially verified using a limited number of inference rules. We present a supplementary verification tool for compressing and checking these certificates independently of how they were created. We report computational results on a selection of MIP instances from the literature. To this end, we have extended the exact rational version of the MIP solver SCIP to produce such certificates.
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.
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.
We consider online optimization problems in which certain goods have to be acquired in order to provide a service or infrastructure. Classically, decisions for such problems are considered as final: one buys the goods...
详细信息
We consider online optimization problems in which certain goods have to be acquired in order to provide a service or infrastructure. Classically, decisions for such problems are considered as final: one buys the goods. However, in many real world applications, there is a shift away from the idea of buying goods. Instead, leasing is often a more flexible and lucrative business model. Research has realized this shift and recently initiated the theoretical study of leasing models (Anthony and Gupta in Proceedings of the integerprogramming and combinatorialoptimization: 12thinternationalipcoconference, Ithaca, NY, USA, June 25-27, 2007;Meyerson in Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2005), 23-25 Oct 2005, Pittsburgh, PA, USA, 2005;Nagarajan and Williamson in Discret Optim 10(4):361-370, 2013) We extend this line of work and suggest a more systematic study of leasing aspects for a class of online optimization problems. We provide two major technical results. We introduce the leasing variant of online set multicover and give an -competitive algorithm (with n, m, and K being the number of elements, sets, and leases, respectively). Our results also imply improvements for the non-leasing variant of online set cover. Moreover, we extend results for the leasing variant of online facility location. Nagarajan and Williamson (Discret Optim 10(4):361-370, 2013) gave an -competitive algorithm for this problem (with n and K being the number of clients and leases, respectively). We remove the dependency on n (and, thereby, on time). In general, this leads to a bound of (withthe maximal lease length ). For many natural problem instances, the bound improves to .
Standard mixed-integerprogramming formulations for the stable set problem on n-node graphs require n integer variables. We prove that this is almost optimal: We give a family of n-node graphs for which every polynomi...
详细信息
ISBN:
(纸本)9783031598340;9783031598357
Standard mixed-integerprogramming formulations for the stable set problem on n-node graphs require n integer variables. We prove that this is almost optimal: We give a family of n-node graphs for which every polynomial-sizeMIP formulation requires Omega(n/ log(2) n) integer variables. By a polyhedral reduction we obtain an analogous result for n-item knapsack problems. In both cases, this improves the previously known bounds of Omega(root n/ log n) by Cevallos, Weltge & Zenklusen (SODA 2018). To this end, we show that there exists a family of n-node graphs whose stable set polytopes satisfy the following: any (1 + epsilon/n)-approximate extended formulation for these polytopes, for some constant epsilon > 0, has size 2(Omega(n / log n)). Our proof extends and simplifies the information-theoretic methods due to Goos, Jain & Watson (FOCS 2016, SIAM J. Comput. 2018) who showed the same result for the case of exact extended formulations (i.e. epsilon = 0).
暂无评论