0 like 0 dislike
0 like 0 dislike
Bachelor Thesis

1 Answer

0 like 0 dislike
0 like 0 dislike
Arnon Boneh's PREDUCE. The tl;dr is you have some polytope in n-dimensional euclidean space that represents a linear optimization problem. The polytope is overdefined (as is wont in linear optimization, you sometimes have several unnecessary constraints on the polytope becaue of the nature of the problem) and so PREDUCE is a way to determine which constraints are redundant and which are necessary in a probablistic manner. The way it works is you generate points at random inside of the euclidean space and determine which constraints it satisfies and fails. Using that information and some computation you can eliminate some of the constraints.

In low dimensional (<5 variables or so) or low complexity (<20 constraints or so) polytopes you don't generally see much benefit from this, but in high dimensional or high complexity polytopes you can sometimes reduce computation time solving the optimization problem significantly.

Related questions

0 like 0 dislike
0 like 0 dislike
79 answers
coL_Punisher asked Jun 21
Regretting majoring in math
coL_Punisher asked Jun 21
0 like 0 dislike
0 like 0 dislike
61 answers
_spunkki asked Jun 21
Just ordered a Klein Bottle from Cliff Stoll. He sent me about 2 dozen pictures of him packing it up. Why is he so cute :)
_spunkki asked Jun 21
0 like 0 dislike
0 like 0 dislike
21 answers
Brands_Hatch asked Jun 21
Is set theory dying?
Brands_Hatch asked Jun 21
0 like 0 dislike
0 like 0 dislike
2 answers
a_dalgleish asked Jun 21
Contributing to the right math area, If all areas are equally curious
a_dalgleish asked Jun 21
0 like 0 dislike
0 like 0 dislike
5 answers
BrianDenver7 asked Jun 21
Is there a nice way to recast riemannian geometry in terms of principal bundles?
BrianDenver7 asked Jun 21

24.8k questions

103k answers

0 comments

33.7k users

OhhAskMe is a math solving hub where high school and university students ask and answer loads of math questions, discuss the latest in math, and share their knowledge. It’s 100% free!