We investigate the information complexity of mixed-integer convex optimization under different kinds of oracles. We establish new lower bounds for the standard first-order oracle, improving upon the previous best know...
详细信息
ISBN:
(数字)9783031327261
ISBN:
(纸本)9783031327254;9783031327261
We investigate the information complexity of mixed-integer convex optimization under different kinds of oracles. We establish new lower bounds for the standard first-order oracle, improving upon the previous best known lower bound. this leaves only a lower order linear term (in the dimension) as the gap between the lower and upper bounds. Further, we prove the first set of results in the literature (to the best of our knowledge) on information complexity with respect to oracles based on first-order information but restricted to binary queries, and discuss various special cases of interest thereof.
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).
In recent work binary decision diagrams (BDDs) were introduced as a technique for postoptimality analysis for integerprogramming. In this paper we show that much smaller BDDs can be used for the same analysis by empl...
详细信息
ISBN:
(纸本)9783540723967
In recent work binary decision diagrams (BDDs) were introduced as a technique for postoptimality analysis for integerprogramming. In this paper we show that much smaller BDDs can be used for the same analysis by employing cost bounding techniques in their construction.
We study the design of approximation algorithms for stochastic combinatorialoptimization problems. We formulate the problems in the framework of two-stage stochastic optimization, and provide nearly tight approximati...
详细信息
ISBN:
(纸本)3540221131
We study the design of approximation algorithms for stochastic combinatorialoptimization problems. We formulate the problems in the framework of two-stage stochastic optimization, and provide nearly tight approximations. Our problems range from the simple (shortest path, vertex cover, bin packing) to complex (facility location, set cover), and contain representatives with different approximation ratios. the approximation ratio of the stochastic variant of a typical problem is of the same order of magnitude as its deterministic counterpart. Furthermore, common techniques for designing approximation algorithms such as LP rounding, the primal-dual method, and the greedy algorithm, can be carefully adapted to obtain these results.
this book constitutes the proceedings of the 15thinternationalconference on integerprogramming and combinatorialoptimization, IPCO 2011, held in New York, USA in June 2011. the 33 papers presented were carefully r...
详细信息
ISBN:
(数字)9783642208072
ISBN:
(纸本)9783642208065
this book constitutes the proceedings of the 15thinternationalconference on integerprogramming and combinatorialoptimization, IPCO 2011, held in New York, USA in June 2011.
the 33 papers presented were carefully reviewed and selected from 110 submissions. the conference is a forum for researchers and practitioners working on various aspects of integerprogramming and combinatorialoptimization withthe aim to present recent developments in theory, computation, and applications. the scope of IPCO is viewed in a broad sense, to include algorithmic and structural results in integerprogramming and combinatorialoptimization as well as revealing computational studies and novel applications of discrete optimization to practical problems.
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.
We investigate cost propagation for solving combinatorialoptimization problems with finite domain variables, expressed as an additive component model. Cost propagation combines ideas from both constraint programming ...
详细信息
ISBN:
(数字)9783540681557
ISBN:
(纸本)9783540681540
We investigate cost propagation for solving combinatorialoptimization problems with finite domain variables, expressed as an additive component model. Cost propagation combines ideas from both constraint programming and integerprogramming into a single approach, where problems are iteratively solved by numerical propagation, with updates for single constraint terms in the component model. We outline a theory of propagation in terms of equivalent problems with notions of consistency, local optimality, convergence and bounds. We define several different updates and analyze their properties. Finally, we outline computational experiments on the simple assignment problem, the set partitioning problem, and a crossword puzzle. the experiments illustrate that even without a top level search, cost propagation can by itself solve non-trivial problems, and also be attractive compared to standard methods.
In this paper we generalize N-fold integer programs and two-stage integer programs with AT scenarios to N-fold 4-block decomposable integer programs. We show that for fixed blocks but variable N, these integer program...
详细信息
ISBN:
(纸本)9783642130359
In this paper we generalize N-fold integer programs and two-stage integer programs with AT scenarios to N-fold 4-block decomposable integer programs. We show that for fixed blocks but variable N, these integer programs are polynomial-time solvable for any linear objective. Moreover, we present a polynomial-time computable optimality certificate for the case of fixed blocks, variable N and any convex separable objective function. We conclude with two sample applications, stochastic integer programs with second-order dominance constraints and stochastic integer multi-commodity flows, which (for fixed blocks) can be solved in polynomial time in the number of scenarios and commodities and in the binary encoding length of the input data. In the proof of our main theorem we combine several non-trivial constructions from the theory of Graver bases. We are confident that our approach paves the way for further extensions.
We propose a general methodology based on robust optimization to address the problem of optimally controlling a supply chain subject to stochastic demand in discrete time. the attractive features of the proposed appro...
详细信息
ISBN:
(纸本)3540221131
We propose a general methodology based on robust optimization to address the problem of optimally controlling a supply chain subject to stochastic demand in discrete time. the attractive features of the proposed approach are: (a) It incorporates a wide variety of phenomena, including demands that are not identically distributed over time and capacity on the echelons and links;(b) it uses very little information on the demand distributions;(c) it leads to qualitatively similar optimal policies (basestock policies) as in dynamic programming;(d) it is numerically tractable for large scale supply chain problems even in networks, where dynamic programming methods face serious dimensionality problems;(e) in preliminary computational experiments, it often outperforms dynamic programming based solutions for a wide range of parameters.
暂无评论