We present a unifying framework for generating extended formulations for the polyhedral outer approximations used in algorithms for mixed-integer convex programming (MICP). Extended formulations lead to fewer iteratio...
详细信息
ISBN:
(数字)9783319334615
ISBN:
(纸本)9783319334615;9783319334608
We present a unifying framework for generating extended formulations for the polyhedral outer approximations used in algorithms for mixed-integer convex programming (MICP). Extended formulations lead to fewer iterations of outer approximation algorithms and generally faster solution times. First, we observe that all MICP instances from the MINLPLIB2 benchmark library are conic representable with standard symmetric and nonsymmetric cones. Conic reformulations are shown to be effective extended formulations themselves because they encode separability structure. For mixed-integer conic-representable problems, we provide the first outer approximation algorithm with finite-time convergence guarantees, opening a path for the use of conic solvers for continuous relaxations. We then connect the popular modeling framework of disciplined convex programming (DCP) to the existence of extended formulations independent of conic representability. We present evidence that our approach can yield significant gains in practice, withthe solution of a number of open instances from the MINLPLIB2 benchmark library.
the exact solution of bilevel optimization problems is a very challenging task that received more and more attention in recent years, as witnessed by the flourishing recent literature on this topic. In this paper we p...
详细信息
ISBN:
(数字)9783319334615
ISBN:
(纸本)9783319334615;9783319334608
the exact solution of bilevel optimization problems is a very challenging task that received more and more attention in recent years, as witnessed by the flourishing recent literature on this topic. In this paper we present ideas and algorithms to solve to proven optimality generic Mixed-integer Bilevel Linear Programs (MIBLP's) where all constraints are linear, and some/all variables are required to take integer values. In doing so, we look for a general-purpose approach applicable to any MIBLP (under mild conditions), rather than ad-hoc methods for specific cases. Our approach concentrates on minimal additions required to convert an effective branch-and-cut MILP exact code into a valid MIBLP solver, thus inheriting the wide arsenal of MILP tools (cuts, branching rules, heuristics) available in modern solvers.
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 .
the problem of maximizing non-negative monotone submodular functions under a certain constraint has been intensively studied in the last decade. In this paper, we address the problem for functions defined over the int...
详细信息
ISBN:
(纸本)9783319334615;9783319334608
the problem of maximizing non-negative monotone submodular functions under a certain constraint has been intensively studied in the last decade. In this paper, we address the problem for functions defined over the integer lattice. Suppose that a non-negative monotone submodular function f : Z(+)(n) -> R+ is given via an evaluation oracle. Assume further that f satisfies the diminishing return property, which is not an immediate consequence of the submodularity when the domain is the integer lattice. then, we show polynomial-time (1 - 1/e - epsilon)-approximation algorithm for cardinality constraints, polymatroid constraints, and knapsack constraints. For a cardinality constraint, we also show a (1 - 1/e - epsilon)-approximation algorithm with slightly worse time complexity that does not rely on the diminishing return property. Our algorithms for a polymatroid constraint and a knapsack constraint first extend the domain of the objective function to the Euclidean space and then run the continuous greedy algorithm. We give two different kinds of continuous extensions, one is for polymatroid constraints and the other is for knapsack constraints, which might be of independent interest.
Sherali-Adams [25] and Lovasz-Schrijver [21] developed systematic procedures to strengthen a relaxation known as lift-and-project methods. they have been proven to be a strong tool for developing approximation algorit...
详细信息
ISBN:
(数字)9783319334615
ISBN:
(纸本)9783319334615;9783319334608
Sherali-Adams [25] and Lovasz-Schrijver [21] developed systematic procedures to strengthen a relaxation known as lift-and-project methods. they have been proven to be a strong tool for developing approximation algorithms, matching the best relaxations known for problems like Max-Cut and Sparsest-Cut. In this work we provide lower bounds for these hierarchies when applied over the configuration LP for the problem of scheduling identical machines to minimize the makespan. First we show that the configuration LP has an integrality gap of at least 1024/1023 by providing a family of instances with 15 different job sizes. then we show that for any integer n there is an instance with n jobs in this family such that after Omega(n) rounds of the Sherali-Adams (SA) or the Lovasz-Schrijver (LS+) hierarchy the integrality gap remains at least 1024/1023.
We study valid inequalities for a set relevant for optimization models that have both binary indicator variables, which indicate positivity of associated continuous variables, and separable concave constraints. Such m...
详细信息
ISBN:
(纸本)9783319334615;9783319334608
We study valid inequalities for a set relevant for optimization models that have both binary indicator variables, which indicate positivity of associated continuous variables, and separable concave constraints. Such models reduce to a mixed-integer linear program (MILP) when the concave constraints are ignored, and to a nonconvex global optimization problem when the binary restrictions are ignored. In algorithms to solve such problems to global optimality, relaxations are traditionally obtained by using valid inequalities for the MILP ignoring the concave constraints, and by independently relaxing each concave constraint using the secant obtained from the bounds of the associated variable. We propose a technique to obtain valid inequalities that are based on boththe MILP and the concave constraints. We begin by analyzing a low-dimensional set that contains a single binary indicator variable, a single concave constraint, and three continuous variables. Using this analysis, for the canonical Single Node Flow Set (SNFS), we demonstrate how to "tilt" a given valid inequality for the SNFS to obtain additional valid inequalities that account for separable concave functions of the arc flows. We present computational results demonstrating the utility of the new inequalities on a fixed plus concave cost transportation problem. To our knowledge, this is one of the first works that simultaneously convexifies both nonconvex functions and binary variables to strengthen the relaxations of practical mixed integer nonlinear programs.
the proceedings contain 33 papers. the topics discussed include: on the structure of reduced kernel lattice bases;all-or-nothing generalized assignment with application to scheduling advertising campaigns;intersection...
ISBN:
(纸本)9783642366932
the proceedings contain 33 papers. the topics discussed include: on the structure of reduced kernel lattice bases;all-or-nothing generalized assignment with application to scheduling advertising campaigns;intersection cuts for mixed integer conic quadratic sets;content placement via the exponential potential function method;a complexity and approximability study of the bilevel knapsack problem;matroid and knapsack center problems;cut-generating functions;on some generalizations of the split closure;packing interdiction and partial covering problems;on valid inequalities for quadratic programming with continuous variables and binary indicators;single commodity-flow algorithms for lifts of graphic and co-graphic matroids;a stochastic probing problem with applications;thrifty algorithms for multistage robust optimization;and two dimensional optimal mechanism design for a sequencing problem.
We present the first criterion space search algorithm, the triangle splitting method, for finding the efficient frontier of a biobjective mixed integer program. the algorithm is relatively easy to implement and conver...
详细信息
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 introduce the simple extension complexity of a polytope P as the smallest number of facets of any simple (i.e., non-degenerate in the sense of linear programming) polytope which can be projected onto P. We devise a...
详细信息
暂无评论