Mathematical Programming

最新文章

• On generalizations of network design problems with degree bounds AI翻译
  作者：Bansal, Nikhil; Khandekar, Rohit; Koenemann, Jochen; Nagarajan, Viswanath; Peis, Britta
  作者单位：Eindhoven University of Technology; International Business Machines (IBM); IBM USA; University of Waterloo; Technical University of Berlin
  摘要：Iterative rounding and relaxation have arguably become the method of choice in dealing with unconstrained and constrained network design problems. In this paper we extend the scope of the iterative relaxation method in two directions: (1) by handling more complex degree constraints in the minimum spanning tree problem (namely laminar crossing spanning tree), and (2) by incorporating 'degree bounds' in other combinatorial optimization problems such as matroid intersection and lattice polyhedra....
• A simple LP relaxation for the asymmetric traveling salesman problem AI翻译
  作者：Thanh Nguyen
  作者单位：Northwestern University
  摘要：It is a long-standing open question in combinatorial optimization whether the integrality gap of the subtour linear program relaxation (subtour LP) for the asymmetric traveling salesman problem (ATSP) is a constant. The study on the structure of this linear program is important and extensive. In this paper, we give a new and simpler LP relaxation for the ATSP. Our linear program consists of a single type of constraints that combine both the subtour elimination and the degree constraints in the...
• Strong lift-and-project cutting planes for the stable set problem AI翻译
  作者：Giandomenico, Monia; Rossi, Fabrizio; Smriglio, Stefano
  作者单位：University of L'Aquila
  摘要：A great deal of research has been focusing, since the early seventies, on finding strong relaxations for the stable set problem. Polyhedral combinatorics techniques have been at first developed to strengthen the natural linear formulation. Afterward, strong semidefinite programming relaxations have been deeply investigated. Nevertheless, the resulting integer programming (IP) algorithms cannot be regarded as being quite successful in practice, as most of the relaxations give rise to one out of...
• Risk adjusted discounted cash flows in capacity expansion models AI翻译
  作者：Ehrenmann, Andreas; Smeers, Yves
  作者单位：Engie; Universite Catholique Louvain
  摘要：This paper addresses a problem that is typical of multi-period capacity expansion equilibrium models: plants or sectors have different risk exposures that may warrant different costs of capital. The paper examines modifications of a capacity expansion model interpreted in equilibrium terms to account for asset-specific costs of capital.
• A model and approach to the challenge posed by optimal power systems planning AI翻译
  作者：O'Neill, Richard P.; Krall, Eric A.; Hedman, Kory W.; Oren, Shmuel S.
  作者单位：Arizona State University; Arizona State University-Tempe; University of California System; University of California Berkeley
  摘要：Currently, there is a need to plan and analyze the electric power transmission system in greater detail and over larger geographic areas. Existing models approach the problem from different perspectives. Each model addresses different aspects of and has different approximations to the optimal planning process. In order to scope out the huge challenge of optimal transmission planning, this paper presents a new modeling approach for inter-regional planning and investment in a competitive environ...
• Enclosing ellipsoids and elliptic cylinders of semialgebraic sets and their application to error bounds in polynomial optimization AI翻译
  作者：Kojima, Masakazu; Yamashita, Makoto
  作者单位：Institute of Science Tokyo; Tokyo Institute of Technology
  摘要：This paper is concerned with a class of ellipsoidal sets (ellipsoids and elliptic cylinders) in which are determined by a freely chosen m x m positive semidefinite matrix. All ellipsoidal sets in this class are similar to each other through a parallel transformation and a scaling around their centers by a constant factor. Based on the basic idea of lifting, we first present a conceptual min-max problem to determine an ellipsoidal set with the smallest size in this class which encloses a given ...
• The tracial moment problem and trace-optimization of polynomials AI翻译
  作者：Burgdorf, Sabine; Cafuta, Kristijan; Klep, Igor; Povh, Janez
  作者单位：University of Neuchatel; University of Ljubljana; University of Maribor; University of Ljubljana
  摘要：The main topic addressed in this paper is trace-optimization of polynomials in noncommuting (nc) variables: given an nc polynomial f, what is the smallest trace can attain for a tuple of matrices ? A relaxation using semidefinite programming (SDP) based on sums of hermitian squares and commutators is proposed. While this relaxation is not always exact, it gives effectively computable bounds on the optima. To test for exactness, the solution of the dual SDP is investigated. If it satisfies a ce...
• Simple bounds for recovering low-complexity models AI翻译
  作者：Candes, Emmanuel; Recht, Benjamin
  作者单位：Stanford University; Stanford University; University of Wisconsin System; University of Wisconsin Madison
  摘要：This note presents a unified analysis of the recovery of simple objects from random linear measurements. When the linear functionals are Gaussian, we show that an s-sparse vector in can be efficiently recovered from 2s log n measurements with high probability and a rank r, n x n matrix can be efficiently recovered from r(6n - 5r) measurements with high probability. For sparse vectors, this is within an additive factor of the best known nonasymptotic bounds. For low-rank matrices, this matches ...
• A complementarity partition theorem for multifold conic systems AI翻译
  作者：Pena, Javier; Roshchina, Vera
  作者单位：Carnegie Mellon University; Federation University Australia; University of Evora
  摘要：Consider a homogeneous multifold convex conic system Ax = 0, x is an element of K-1 x ... x K-r and its alternative system A(T) y is an element of K-1* x ... x K-r*, where K-1, ... , K-r are regular closed convex cones. We show that there is a canonical partition of the index set {1, ... , r} determined by certain complementarity sets associated to the most interior solutions to the two systems. Our results are inspired by and extend the Goldman-Tucker Theorem for linear programming.
• Risk-averse feasible policies for large-scale multistage stochastic linear programs AI翻译
  作者：Guigues, Vincent; Sagastizabal, Claudia
  作者单位：Getulio Vargas Foundation; Universidade Federal do Rio de Janeiro
  摘要：We consider risk-averse formulations of stochastic linear programs having a structure that is common in real-life applications. Specifically, the optimization problem corresponds to controlling over a certain horizon a system whose dynamics is given by a transition equation depending affinely on an interstage dependent stochastic process. We put in place a rolling-horizon time consistent policy. For each time step, a risk-averse problem with constraints that are deterministic for the current t...