the proceedings contain 32 papers. the topics discussed include: perspective relaxation of mixed integer nonlinear programs with indicator variables;disjunctive cuts for non-convex mixed integer quadratically constrai...
详细信息
ISBN:
(纸本)3540688862
the proceedings contain 32 papers. the topics discussed include: perspective relaxation of mixed integer nonlinear programs with indicator variables;disjunctive cuts for non-convex mixed integer quadratically constrained programs;the air traffic flow management problem: an integeroptimization approach;the induced disjoint paths problem;a new algorithm for the maximum weighted stable set problem in claw-free graphs;a polynomial algorithm for weighted abstract flow;a comparative study of linear and semidefinite branch-and-cut methods for solving the minimum graph bisection problem;binary positive semidefinite matrices and associated integer polytopes;vertex cover resists SDPs tightened by local hypermetric inequalities;tight bounds for permutation flow shop scheduling;the stochastic machine replenishment problem;a polynomial time approximation scheme for the square packing problem;and constraint orbital branching.
the volume contains the papers selected for presentation at ipco 2008, the 13thinternationalconference on integerprogramming and combinatorial - timization that was held in Bertinoro (Italy), May 26–28, 2008. the ...
详细信息
ISBN:
(数字)9783540688914
ISBN:
(纸本)9783540688860
the volume contains the papers selected for presentation at ipco 2008, the 13thinternationalconference on integerprogramming and combinatorial - timization that was held in Bertinoro (Italy), May 26–28, 2008. the ipco series of conferences, sponsored by the Mathematical Progr- ming Society, highlights recent developments in theory, computation, and app- cation of integerprogramming and combinatorialoptimization. the ?rst conf- ence took place in 1990; starting from ipco 1995, the proceedings are published in the Lecture Notes in Computer Science series. the 12 previous ipcoconferences were held in Waterloo (Canada) 1990, Pittsburgh (USA) 1992, Erice (Italy) 1993, Copenhagen (Denmark) 1995 [LNCS 920], Vancouver (Canada) 1996 [LNCS 1084], Houston (USA) 1998 [LNCS 1412], Graz (Austria) 1999 [LNCS 1610], Utrecht (the Netherlands) 2001 [LNCS 2081], Boston (USA) 2002 [LNCS 2337], New York (USA) 2004 [LNCS 2986], Berlin (Germany) 2005 [LNCS 3509], and Ithaca (USA) 2007 [LNCS 4168]. the c- ference is not held in the years when the international Symposium of the Ma- ematical programming Society takes place.
We consider a new semidefinite programming (SDP) relaxation of the symmetric traveling salesman problem (TSP) that may be obtained via an SDP relaxation of the more general quadratic assignment problem (QAP). We show ...
详细信息
We consider a new semidefinite programming (SDP) relaxation of the symmetric traveling salesman problem (TSP) that may be obtained via an SDP relaxation of the more general quadratic assignment problem (QAP). We show that the new relaxation dominates the one in [D. Cvetkovic, M. Cangalovic, and V. Kovacevic-Vujcic, Semidefinite programming methods for the symmetric traveling salesman problem, in Proceedings of the 7thinternationalipcoconference on integerprogramming and combinatorialoptimization, Springer-Verlag, London, UK, 1999, pp. 126-136]. Unlike the bound of Cvetkovic et al., the new SDP bound is not dominated by the Held-Karp linear programming bound, or vice versa.
We consider a robust formulation, introduced by Krause et al. (2008), of the classic cardinality constrained monotone submodular function maximization problem, and give the first constant factor approximation results....
详细信息
ISBN:
(纸本)9783319334615;9783319334608
We consider a robust formulation, introduced by Krause et al. (2008), of the classic cardinality constrained monotone submodular function maximization problem, and give the first constant factor approximation results. the robustness considered is w.r.t. adversarial removal of a given number of elements from the chosen set. In particular, for the fundamental case of single element removal, we show that one can approximate the problem up to a factor (1 - 1/e) - epsilon by making O(n(1/epsilon)) queries, for arbitrary epsilon > 0. the ideas are also extended to more general settings.
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.
Given rational numbers C-0,...,C-m and b(0),...,b(m), the mixing set with arbitrary capacities is the mixed-integer set defined by conditions s + C(t)z(t) >= b(t), 0 = 0, z(t) integer, 0 <= t <= m. Such a set...
详细信息
ISBN:
(纸本)9783540688860
Given rational numbers C-0,...,C-m and b(0),...,b(m), the mixing set with arbitrary capacities is the mixed-integer set defined by conditions s + C(t)z(t) >= b(t), 0 <= t <= m, s >= 0, z(t) integer, 0 <= t <= m. Such a set has applications in lot-sizing problems. We study the special case of divisible capacities, i.e. C-t/Ct-1 is a positive integer for 1 < t <= m. Under this assumption, we give an extended formulation for the convex hull of the above set that uses a quadratic number of variables and constraints.
We consider the line search problem in a submodular polyhedron P(f)subset of R-n : Given an arbitrary a is an element of R-n and x(0) is an element of P(f), compute max{delta : x(0) + delta a is an element of P(f)}. T...
详细信息
ISBN:
(数字)9783319592503
ISBN:
(纸本)9783319592503;9783319592497
We consider the line search problem in a submodular polyhedron P(f)subset of R-n : Given an arbitrary a is an element of R-n and x(0) is an element of P(f), compute max{delta : x(0) + delta a is an element of P(f)}. the use of the discrete Newton's algorithm for this line search problem is very natural, but no strongly polynomial bound on its number of iterations was known (Iwata 2008). We solve this open problem by providing a quadratic bound of n(2) + O(n log(2) n) on its number of iterations. Our result considerably improves upon the only other known strongly polynomial time algorithm, which is based on Megiddo's parametric search framework and which requires (O) over bar (n(8)) submodular function minimizations (Nagano 2007). As a by-product of our study, we prove (tight) bounds on the length of chains of ring families and geometrically increasing sequences of sets, which might be of independent interest.
We propose a Branch-and-Cut algorithm for the robust influence maximization problem. the influence maximization problem aims to identify, in a social network, a set of given cardinality comprising actors that are able...
详细信息
ISBN:
(纸本)9783030179533;9783030179526
We propose a Branch-and-Cut algorithm for the robust influence maximization problem. the influence maximization problem aims to identify, in a social network, a set of given cardinality comprising actors that are able to influence the maximum number of other actors. We assume that the social network is given in the form of a graph with node thresholds to indicate the resistance of an actor to influence, and arc weights to represent the strength of the influence between two actors. In the robust version of the problem that we study, the node thresholds are affected by uncertainty and we optimize over a worst-case scenario within a given robustness budget. Numerical experiments show that we are able to solve to optimality instances of size comparable to other exact approaches in the literature for the non-robust problem, but in addition to this we can also tackle the robust version with similar performance.
We consider the problem of designing a linear program that has diverse solutions as the right-hand side varies. this problem arises in video game settings where designers aim to have players use different "weapon...
详细信息
ISBN:
(数字)9783031327261
ISBN:
(纸本)9783031327254;9783031327261
We consider the problem of designing a linear program that has diverse solutions as the right-hand side varies. this problem arises in video game settings where designers aim to have players use different "weapons" or "tactics" as they progress. We model this design question as a choice over the constraint matrix A and cost vector c to maximize the number of possible supports of unique optimal solutions (what we call "loadouts") of Linear Programs max{c(inverted perpendicular) x vertical bar Ax <= b, x >= 0} with nonnegative data considered over all resource vectors b. We provide an upper bound on the optimal number of loadouts and provide a family of constructions that have an asymptotically optimal number of loadouts. the upper bound is based on a connection between our problem and the study of triangulations of point sets arising from polyhedral combinatorics, and specifically the combinatorics of the cyclic polytope. Our asymptotically optimal construction also draws inspiration from the properties of the cyclic polytope.
暂无评论