-
作者：Cox, Bruce; Juditsky, Anatoli; Nemirovski, Arkadi
作者单位：United States Department of Defense; United States Air Force; Communaute Universite Grenoble Alpes; Universite Grenoble Alpes (UGA); University System of Georgia; Georgia Institute of Technology
摘要：Classical First Order (FO) algorithms of convex optimization, such as Mirror Descent algorithm or Nesterov's optimal algorithm of smooth convex optimization, are well known to have optimal (theoretical) complexity estimates which do not depend on the problem dimension. However, to attain the optimality, the domain of the problem should admit a good proximal setup. The latter essentially means that (1) the problem domain should satisfy certain geometric conditions of favorable geometry, and (2)...
-
作者：Bonato, Thorsten; Juenger, Michael; Reinelt, Gerhard; Rinaldi, Giovanni
作者单位：Ruprecht Karls University Heidelberg; University of Cologne; Consiglio Nazionale delle Ricerche (CNR)
摘要：The max-cut problem and the associated cut polytope on complete graphs have been extensively studied over the last 25 years. However, in comparison, only little research has been conducted for the cut polytope on arbitrary graphs, in particular separation algorithms have received only little attention. In this study we describe new separation and lifting procedures for the cut polytope on general graphs. These procedures exploit algorithmic and structural results known for the cut polytope on ...
-
作者：Chung, Kwanghun; Richard, Jean-Philippe P.; Tawarmalani, Mohit
作者单位：Hongik University; State University System of Florida; University of Florida; Purdue University System; Purdue University
摘要：In this paper, we study mixed-integer bilinear covering sets. We derive several families of facet-defining inequalities via sequence-independent lifting techniques. We then show that these sets have a polyhedral structure that is similar to that of a certain fixed-charge single-node flow set. As a result, we also obtain new facet-defining inequalities for the single-node flow set that generalize well-known lifted flow cover inequalities from the integer programming literature.
-
作者：Dey, Santanu S.; Pokutta, Sebastian
作者单位：University System of Georgia; Georgia Institute of Technology
摘要：A cutting-plane procedure for integer programming (IP) problems usually involves invoking a black-box procedure (such as the Gomory-Chvatal procedure) to compute a cutting-plane. In this paper, we describe an alternative paradigm of using the same cutting-plane black-box. This involves two steps. In the first step, we design an inequality where and are integral, independent of the cutting-plane black-box. In the second step, we verify that the designed inequality is a valid inequality by verif...
-
作者：Sullivan, Kelly M.; Smith, J. Cole; Morton, David P.
作者单位：University of Arkansas System; University of Arkansas Fayetteville; State University System of Florida; University of Florida; University of Texas System; University of Texas Austin
摘要：We consider a version of the stochastic network interdiction problem modeled by Morton et al. (IIE Trans 39:3-14, 2007) in which an interdictor attempts to minimize a potential smuggler's chance of evasion via discrete deployment of sensors on arcs in a bipartite network. The smuggler reacts to sensor deployments by solving a maximum-reliability path problem on the resulting network. In this paper, we develop the (minimal) convex hull representation for the polytope linking the interdictor's d...
-
作者：Chen, Xiaojun; Ge, Dongdong; Wang, Zizhuo; Ye, Yinyu
作者单位：Hong Kong Polytechnic University; Shanghai Jiao Tong University; University of Minnesota System; University of Minnesota Twin Cities; Stanford University
摘要：We consider the unconstrained - minimization: find a minimizer of for given , and parameters , and . This problem has been studied extensively in many areas. Especially, for the case when , this problem is known as the minimization problem and has found its applications in variable selection problems and sparse least squares fitting for high dimensional data. Theoretical results show that the minimizers of the - problem have various attractive features due to the concavity and non-Lipschitzian...
-
作者：Luna, Juan Pablo; Sagastizabal, Claudia; Solodov, Mikhail
作者单位：Instituto Nacional de Matematica Pura e Aplicada (IMPA)
摘要：We consider a class of decomposition methods for variational inequalities, which is related to the classical Dantzig-Wolfe decomposition of linear programs. Our approach is rather general, in that it can be used with certain types of set-valued or nonmonotone operators, as well as with various kinds of approximations in the subproblems of the functions and derivatives in the single-valued case. Also, subproblems may be solved approximately. Convergence is established under reasonable assumptio...
-
作者：Dyer, M.; Kannan, R.; Stougie, L.
作者单位：University of Leeds; Microsoft; Microsoft India; Vrije Universiteit Amsterdam; Centrum Wiskunde & Informatica (CWI)
摘要：We consider maximising a concave function over a convex set by a simple randomised algorithm. The strength of the algorithm is that it requires only approximate function evaluations for the concave function and a weak membership oracle for the convex set. Under smoothness conditions on the function and the feasible set, we show that our algorithm computes a near-optimal point in a number of operations which is bounded by a polynomial function of all relevant input parameters and the reciprocal...
-
作者：Angulo, Gustavo; Ahmed, Shabbir; Dey, Santanu S.
作者单位：University System of Georgia; Georgia Institute of Technology
摘要：We consider semi-continuous network flow problems, that is, a class of network flow problems where some of the variables are restricted to be semi-continuous. We introduce the semi-continuous inflow set with variable upper bounds as a relaxation of general semi-continuous network flow problems. Two particular cases of this set are considered, for which we present complete descriptions of the convex hull in terms of linear inequalities and extended formulations. We consider a class of semi-cont...
-
作者：Van Vyve, Mathieu; Wolsey, Laurence A.; Yaman, Hande
作者单位：Ihsan Dogramaci Bilkent University
摘要：We consider several variants of the two-level lot-sizing problem with one item at the upper level facing dependent demand, and multiple items or clients at the lower level, facing independent demands. We first show that under a natural cost assumption, it is sufficient to optimize over a stock-dominant relaxation. We further study the polyhedral structure of a strong relaxation of this problem involving only initial inventory variables and setup variables. We consider several variants: uncapac...
