-
作者：Yu, Xian; Shen, Siqian
作者单位：University of Michigan System; University of Michigan
摘要：We study multistage distributionally robust mixed-integer programs under endogenous uncertainty, where the probability distribution of stage-wise uncertainty depends on the decisions made in previous stages. We first consider two ambiguity sets defined by decision-dependent bounds on the first and second moments of uncertain parameters and by mean and covariance matrix that exactly match decision-dependent empirical ones, respectively. For both sets, we show that the subproblem in each stage c...
-
作者：Harks, Tobias; Tan-Timmermans, Veerle
作者单位：RWTH Aachen University
-
作者：Fuellner, Christian; Rebennack, Steffen
作者单位：Helmholtz Association; Karlsruhe Institute of Technology
摘要：We propose a new decomposition method to solve multistage non-convex mixedinteger (stochastic) nonlinear programming problems (MINLPs). We call this algorithm non-convex nested Benders decomposition (NC-NBD). NC-NBD is based on solving dynamically improved mixed-integer linear outer approximations of the MINLP, obtained by piecewise linear relaxations of nonlinear functions. Those MILPs are solved to global optimality using an enhancement of nested Benders decomposition, in which regularizatio...
-
作者：Barman, Siddharth; Fawzi, Omar; Ghoshal, Suprovat; Gurpinar, Emirhan
作者单位：Indian Institute of Science (IISC) - Bangalore; Ecole Normale Superieure de Lyon (ENS de LYON); Inria; Centre National de la Recherche Scientifique (CNRS)
摘要：In the classic maximum coverage problem, we are given subsets T-1,..., T-m of a universe [n] along with an integer k and the objective is to find a subset S subset of [m] of size k that maximizes C(S) := vertical bar boolean OR(i is an element of S) T-i vertical bar. It is well-known that the greedy algorithm for this problem achieves an approximation ratio of (1- e(-1)) and there is a matching inapproximability result. We note that in themaximum coverage problem if an element e is an element ...
-
作者：Paat, Joseph; Schloeter, Miriam; Weismantel, Robert
作者单位：University of British Columbia; Swiss Federal Institutes of Technology Domain; ETH Zurich
摘要：We introduce the integrality number of an integer program (IP). Roughly speaking, the integrality number is the smallest number of integer constraints needed to solve an IP via a mixed integer (MIP) relaxation. One notable property of this number is its invariance under unimodular transformations of the constraint matrix. Considering the largest minor Delta of the constraint matrix, our analysis allows us to make statements of the following form: there exists a number tau(Delta) such that an I...
-
作者：Dahl, Joachim; Andersen, Erling D.
摘要：A new primal-dual interior-point algorithm applicable to nonsymmetric conic optimization is proposed. It is a generalization of the famous algorithm suggested by Nesterov and Todd for the symmetric conic case, and uses primal-dual scalings for nonsymmetric cones proposed by Tuncel. We specialize Tuncel's primal-dual scalings for the important case of 3 dimensional exponential-cones, resulting in a practical algorithm with good numerical performance, on level with standard symmetric cone (e.g.,...
-
作者：Homem-de-Mello, Tito; Kopa, Milos; Morton, David P.
作者单位：Universidad Adolfo Ibanez; Charles University Prague; Northwestern University
-
作者：Gupta, Anupam; Kumar, Amit; Nagarajan, Viswanath; Shen, Xiangkun
作者单位：Carnegie Mellon University; Indian Institute of Technology System (IIT System); Indian Institute of Technology (IIT) - Delhi; University of Michigan System; University of Michigan; Yahoo! Inc
摘要：We study stochastic combinatorial optimization problems where the objective is to minimize the expected maximum load (a.k.a. the makespan). In this framework, we have a set of n tasks and m resources, where each task j uses some subset of the resources. Tasks have random sizes X-j, and our goal is to non-adaptively select t tasks to minimize the expected maximum load over all resources, where the load on any resource i is the total size of all selected tasks that use i. For example, when resou...
-
作者：Frank, Andras; Murota, Kazuo
作者单位：Eotvos Lorand University; Tokyo Metropolitan University; Research Organization of Information & Systems (ROIS); Institute of Statistical Mathematics (ISM) - Japan
摘要：This paper is concerned with algorithms and applications of decreasing minimization on an M-convex set, which is the set of integral elements of an integral base-polyhedron. Based on a recent characterization of decreasingly minimal (dec-min) elements, we develop a strongly polynomial algorithm for computing a dec-min element of an M-convex set. The matroidal feature of the set of dec-min elements makes it possible to compute a minimum cost dec-min element, as well. Our second goal is to exhib...
-
作者：Laiu, M. Paul; Tits, Andre L.
作者单位：United States Department of Energy (DOE); Oak Ridge National Laboratory; University System of Maryland; University of Maryland College Park; University System of Maryland; University of Maryland College Park
摘要：A framework is proposed for solving general convex quadratic programs (CQPs) from an infeasible starting point by invoking an existing feasible-start algorithm tailored for inequality-constrained CQPs. The central tool is an exact penalty function scheme equipped with a penalty-parameter updating rule. The feasible-start algorithm merely has to satisfy certain general requirements, and so is the updating rule. Under mild assumptions, the framework is proved to converge on CQPs with both inequa...
