NDLI: Persistence in discrete optimization under data uncertainty

Content Provider	Springer Nature Link
Author	Bertsimas, Dimitris Natarajan, Karthik Teo, Chung Piaw
Copyright Year	2006
Abstract	An important question in discrete optimization under uncertainty is to understand the persistency of a decision variable, i.e., the probability that it is part of an optimal solution. For instance, in project management, when the task activity times are random, the challenge is to determine a set of critical activities that will potentially lie on the longest path. In the spanning tree and shortest path network problems, when the arc lengths are random, the challenge is to pre-process the network and determine a smaller set of arcs that will most probably be a part of the optimal solution under different realizations of the arc lengths. Building on a characterization of moment cones for single variate problems, and its associated semidefinite constraint representation, we develop a limited marginal moment model to compute the persistency of a decision variable. Under this model, we show that finding the persistency is tractable for zero-one optimization problems with a polynomial sized representation of the convex hull of the feasible region. Through extensive experiments, we show that the persistency computed under the limited marginal moment model is often close to the simulated persistency value under various distributions that satisfy the prescribed marginal moments and are generated independently.
Ending Page	274
Page Count	24
Starting Page	251
File Format	PDF
ISSN	00255610
e-ISSN	14364646
Journal	Mathematical Programming
Issue Number	2-3
Volume Number	108
Language	English
Publisher	Springer-Verlag
Publisher Date	2006-04-25
Publisher Place	Berlin, Heidelberg
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Persistence Semidefinite programming Mathematical Methods in Physics Mathematics of Computing Numerical Analysis Mathematical and Computational Physics Discrete optimization Calculus of Variations and Optimal Control Combinatorial optimization Combinatorics Optimization Stochastic programming
Content Type	Text
Resource Type	Article
Subject	Mathematics Software

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Semidefinite programming in combinatorial optimization

Generalized Gauss inequalities via semidefinite programming

Semidefinite programming

An improved semidefinite programming relaxation for the satisfiability problem

Selected topics in robust convex optimization

On approximating complex quadratic optimization problems via semidefinite programming relaxations

Phase recovery, MaxCut and complex semidefinite programming

Recognizing underlying sparsity in optimization

Dynamic bundle methods

Persistence in discrete optimization under data uncertainty

Similar Documents

Semidefinite programming in combinatorial optimization

Generalized Gauss inequalities via semidefinite programming

Semidefinite programming

An improved semidefinite programming relaxation for the satisfiability problem

Selected topics in robust convex optimization

On approximating complex quadratic optimization problems via semidefinite programming relaxations

Phase recovery, MaxCut and complex semidefinite programming

Recognizing underlying sparsity in optimization

Dynamic bundle methods

Persistence in discrete optimization under data uncertainty