Searching extreme points of polyhedron





.everyoneloves__top-leaderboard:empty,.everyoneloves__mid-leaderboard:empty,.everyoneloves__bot-mid-leaderboard:empty{ margin-bottom:0;
}







3












$begingroup$


In my Uni, my scientific professor asked me to make some researches about the extreme points of polyhedrals. And I did them. I found that there is still no code in public for searching extreme points for polyhedral with n dimensions (n - x's), but polyhedrons are everywhere (CV, game theories, etc.). I wrote a function for this task and made a python library (also there are matrix and array combination maker functions).



All I want is to make this code more optimal and compatible for all python versions (I have some troubles that some times happen when I install it by "pip install lin", but other times no). I want to make the life of people easier and make it more comfortable.



I am asking for you to test this function on your computer and write if you have any bugs, fails or thoughts on how to make it better. I am open to constructive criticism and non-constructive too (it will help to understand if somebody needs it or that is just a waste of time).



All the examples, instructions and code on my GitHub: https://github.com/r4ndompuff/polyhedral_set



import numpy as np
import itertools as it
import math
import re

def permutation(m,n):
return math.factorial(n)/(math.factorial(n-m)*math.factorial(m))

def matrix_combinations(matr,n):
timed = list(map(list, it.combinations(matr, n)))
for i in range(n):
timed[i][i][i] = np.asscalar(timed[i][i][i])
all = np.array(list(timed))
return all

def array_combinations(arr,n):
timed = list(map(list, it.combinations(arr, n)))
for i in range(n):
timed[i][i] = np.asscalar(timed[i][i])
all = np.array(list(timed))
return all

def check_extreme(matr, arr, x, sym_comb, m):
sym_comb = sym_comb.replace(']', '')
sym_comb = sym_comb.replace('[', '')
sym_comb = re.split("[ ,]", sym_comb)
for i in range(m):
td_answer = sum(matr[i]*x)
if sym_comb[i] == '>':
if td_answer <= arr[i]:
return 0
elif sym_comb[i] == '>=':
if td_answer < arr[i]:
return 0
elif sym_comb[i] == '<':
if td_answer >= arr[i]:
return 0
elif sym_comb[i] == '<=':
if td_answer > arr[i]:
return 0
elif sym_comb[i] == '=':
if td_answer != arr[i]:
return 0
elif sym_comb[i] == '!=':
if td_answer == arr[i]:
return 0
else:
return 0
return 1

def extreme_points(m,n,A,b,sym_comb):
# Input
A = np.array(A).reshape(m,n)
b = np.array(b).reshape(m,1)
# Proccess
ans_comb = np.zeros((1,n))
arr_comb = array_combinations(b,n)
matr_comb = matrix_combinations(A,n)
for i in range(int(permutation(n,m))):
if np.linalg.det(matr_comb[i]) != 0:
x = np.linalg.solve(matr_comb[i],arr_comb[i])
ans_comb = np.vstack([ans_comb,x])
ans_comb = np.delete(ans_comb, (0), axis=0)
j = 0
for i in range(len(ans_comb)):
if check_extreme(A, b, ans_comb[j], sym_comb, m):
ans_comb = ans_comb
j = j + 1
else:
ans_comb = np.delete(ans_comb, (j), axis=0)
# Output
return ans_comb


And I am uploading some more tests. https://imgur.com/mjweDyy










share|improve this question









New contributor




Andrey Lovyagin is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.







$endgroup$












  • $begingroup$
    Can you provide some more information on what exactly is going on, from a math standpoint? Is this actually a polyhedron, or a polytope? In how many dimensions? By "extreme", what do you mean? Euclidean norm from (the origin, an arbitrary point)?
    $endgroup$
    – Reinderien
    4 hours ago










  • $begingroup$
    "there is still no code in public for searching extreme points for polyhedral with n dimensions" - I can nearly guarantee that that isn't the case.
    $endgroup$
    – Reinderien
    4 hours ago






  • 1




    $begingroup$
    @Reinderien I am still in the process of deciphering the question. I have a math background, and I share the mother tongue with OP. My impression is that by extremal points OP means the vertices of a simplex where a certain linear form (defined by A, b, and the condition) achieves an extremum. I could be wrong.
    $endgroup$
    – vnp
    2 hours ago










  • $begingroup$
    @vnp That's kind of what I guessed, and if that's the case, linear programming is a quite well-established field already - with some stuff built right into scipy.
    $endgroup$
    – Reinderien
    2 hours ago










  • $begingroup$
    @Reinderien Agreed. Still deciphering.
    $endgroup$
    – vnp
    2 hours ago


















3












$begingroup$


In my Uni, my scientific professor asked me to make some researches about the extreme points of polyhedrals. And I did them. I found that there is still no code in public for searching extreme points for polyhedral with n dimensions (n - x's), but polyhedrons are everywhere (CV, game theories, etc.). I wrote a function for this task and made a python library (also there are matrix and array combination maker functions).



All I want is to make this code more optimal and compatible for all python versions (I have some troubles that some times happen when I install it by "pip install lin", but other times no). I want to make the life of people easier and make it more comfortable.



I am asking for you to test this function on your computer and write if you have any bugs, fails or thoughts on how to make it better. I am open to constructive criticism and non-constructive too (it will help to understand if somebody needs it or that is just a waste of time).



All the examples, instructions and code on my GitHub: https://github.com/r4ndompuff/polyhedral_set



import numpy as np
import itertools as it
import math
import re

def permutation(m,n):
return math.factorial(n)/(math.factorial(n-m)*math.factorial(m))

def matrix_combinations(matr,n):
timed = list(map(list, it.combinations(matr, n)))
for i in range(n):
timed[i][i][i] = np.asscalar(timed[i][i][i])
all = np.array(list(timed))
return all

def array_combinations(arr,n):
timed = list(map(list, it.combinations(arr, n)))
for i in range(n):
timed[i][i] = np.asscalar(timed[i][i])
all = np.array(list(timed))
return all

def check_extreme(matr, arr, x, sym_comb, m):
sym_comb = sym_comb.replace(']', '')
sym_comb = sym_comb.replace('[', '')
sym_comb = re.split("[ ,]", sym_comb)
for i in range(m):
td_answer = sum(matr[i]*x)
if sym_comb[i] == '>':
if td_answer <= arr[i]:
return 0
elif sym_comb[i] == '>=':
if td_answer < arr[i]:
return 0
elif sym_comb[i] == '<':
if td_answer >= arr[i]:
return 0
elif sym_comb[i] == '<=':
if td_answer > arr[i]:
return 0
elif sym_comb[i] == '=':
if td_answer != arr[i]:
return 0
elif sym_comb[i] == '!=':
if td_answer == arr[i]:
return 0
else:
return 0
return 1

def extreme_points(m,n,A,b,sym_comb):
# Input
A = np.array(A).reshape(m,n)
b = np.array(b).reshape(m,1)
# Proccess
ans_comb = np.zeros((1,n))
arr_comb = array_combinations(b,n)
matr_comb = matrix_combinations(A,n)
for i in range(int(permutation(n,m))):
if np.linalg.det(matr_comb[i]) != 0:
x = np.linalg.solve(matr_comb[i],arr_comb[i])
ans_comb = np.vstack([ans_comb,x])
ans_comb = np.delete(ans_comb, (0), axis=0)
j = 0
for i in range(len(ans_comb)):
if check_extreme(A, b, ans_comb[j], sym_comb, m):
ans_comb = ans_comb
j = j + 1
else:
ans_comb = np.delete(ans_comb, (j), axis=0)
# Output
return ans_comb


And I am uploading some more tests. https://imgur.com/mjweDyy










share|improve this question









New contributor




Andrey Lovyagin is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.







$endgroup$












  • $begingroup$
    Can you provide some more information on what exactly is going on, from a math standpoint? Is this actually a polyhedron, or a polytope? In how many dimensions? By "extreme", what do you mean? Euclidean norm from (the origin, an arbitrary point)?
    $endgroup$
    – Reinderien
    4 hours ago










  • $begingroup$
    "there is still no code in public for searching extreme points for polyhedral with n dimensions" - I can nearly guarantee that that isn't the case.
    $endgroup$
    – Reinderien
    4 hours ago






  • 1




    $begingroup$
    @Reinderien I am still in the process of deciphering the question. I have a math background, and I share the mother tongue with OP. My impression is that by extremal points OP means the vertices of a simplex where a certain linear form (defined by A, b, and the condition) achieves an extremum. I could be wrong.
    $endgroup$
    – vnp
    2 hours ago










  • $begingroup$
    @vnp That's kind of what I guessed, and if that's the case, linear programming is a quite well-established field already - with some stuff built right into scipy.
    $endgroup$
    – Reinderien
    2 hours ago










  • $begingroup$
    @Reinderien Agreed. Still deciphering.
    $endgroup$
    – vnp
    2 hours ago














3












3








3





$begingroup$


In my Uni, my scientific professor asked me to make some researches about the extreme points of polyhedrals. And I did them. I found that there is still no code in public for searching extreme points for polyhedral with n dimensions (n - x's), but polyhedrons are everywhere (CV, game theories, etc.). I wrote a function for this task and made a python library (also there are matrix and array combination maker functions).



All I want is to make this code more optimal and compatible for all python versions (I have some troubles that some times happen when I install it by "pip install lin", but other times no). I want to make the life of people easier and make it more comfortable.



I am asking for you to test this function on your computer and write if you have any bugs, fails or thoughts on how to make it better. I am open to constructive criticism and non-constructive too (it will help to understand if somebody needs it or that is just a waste of time).



All the examples, instructions and code on my GitHub: https://github.com/r4ndompuff/polyhedral_set



import numpy as np
import itertools as it
import math
import re

def permutation(m,n):
return math.factorial(n)/(math.factorial(n-m)*math.factorial(m))

def matrix_combinations(matr,n):
timed = list(map(list, it.combinations(matr, n)))
for i in range(n):
timed[i][i][i] = np.asscalar(timed[i][i][i])
all = np.array(list(timed))
return all

def array_combinations(arr,n):
timed = list(map(list, it.combinations(arr, n)))
for i in range(n):
timed[i][i] = np.asscalar(timed[i][i])
all = np.array(list(timed))
return all

def check_extreme(matr, arr, x, sym_comb, m):
sym_comb = sym_comb.replace(']', '')
sym_comb = sym_comb.replace('[', '')
sym_comb = re.split("[ ,]", sym_comb)
for i in range(m):
td_answer = sum(matr[i]*x)
if sym_comb[i] == '>':
if td_answer <= arr[i]:
return 0
elif sym_comb[i] == '>=':
if td_answer < arr[i]:
return 0
elif sym_comb[i] == '<':
if td_answer >= arr[i]:
return 0
elif sym_comb[i] == '<=':
if td_answer > arr[i]:
return 0
elif sym_comb[i] == '=':
if td_answer != arr[i]:
return 0
elif sym_comb[i] == '!=':
if td_answer == arr[i]:
return 0
else:
return 0
return 1

def extreme_points(m,n,A,b,sym_comb):
# Input
A = np.array(A).reshape(m,n)
b = np.array(b).reshape(m,1)
# Proccess
ans_comb = np.zeros((1,n))
arr_comb = array_combinations(b,n)
matr_comb = matrix_combinations(A,n)
for i in range(int(permutation(n,m))):
if np.linalg.det(matr_comb[i]) != 0:
x = np.linalg.solve(matr_comb[i],arr_comb[i])
ans_comb = np.vstack([ans_comb,x])
ans_comb = np.delete(ans_comb, (0), axis=0)
j = 0
for i in range(len(ans_comb)):
if check_extreme(A, b, ans_comb[j], sym_comb, m):
ans_comb = ans_comb
j = j + 1
else:
ans_comb = np.delete(ans_comb, (j), axis=0)
# Output
return ans_comb


And I am uploading some more tests. https://imgur.com/mjweDyy










share|improve this question









New contributor




Andrey Lovyagin is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.







$endgroup$




In my Uni, my scientific professor asked me to make some researches about the extreme points of polyhedrals. And I did them. I found that there is still no code in public for searching extreme points for polyhedral with n dimensions (n - x's), but polyhedrons are everywhere (CV, game theories, etc.). I wrote a function for this task and made a python library (also there are matrix and array combination maker functions).



All I want is to make this code more optimal and compatible for all python versions (I have some troubles that some times happen when I install it by "pip install lin", but other times no). I want to make the life of people easier and make it more comfortable.



I am asking for you to test this function on your computer and write if you have any bugs, fails or thoughts on how to make it better. I am open to constructive criticism and non-constructive too (it will help to understand if somebody needs it or that is just a waste of time).



All the examples, instructions and code on my GitHub: https://github.com/r4ndompuff/polyhedral_set



import numpy as np
import itertools as it
import math
import re

def permutation(m,n):
return math.factorial(n)/(math.factorial(n-m)*math.factorial(m))

def matrix_combinations(matr,n):
timed = list(map(list, it.combinations(matr, n)))
for i in range(n):
timed[i][i][i] = np.asscalar(timed[i][i][i])
all = np.array(list(timed))
return all

def array_combinations(arr,n):
timed = list(map(list, it.combinations(arr, n)))
for i in range(n):
timed[i][i] = np.asscalar(timed[i][i])
all = np.array(list(timed))
return all

def check_extreme(matr, arr, x, sym_comb, m):
sym_comb = sym_comb.replace(']', '')
sym_comb = sym_comb.replace('[', '')
sym_comb = re.split("[ ,]", sym_comb)
for i in range(m):
td_answer = sum(matr[i]*x)
if sym_comb[i] == '>':
if td_answer <= arr[i]:
return 0
elif sym_comb[i] == '>=':
if td_answer < arr[i]:
return 0
elif sym_comb[i] == '<':
if td_answer >= arr[i]:
return 0
elif sym_comb[i] == '<=':
if td_answer > arr[i]:
return 0
elif sym_comb[i] == '=':
if td_answer != arr[i]:
return 0
elif sym_comb[i] == '!=':
if td_answer == arr[i]:
return 0
else:
return 0
return 1

def extreme_points(m,n,A,b,sym_comb):
# Input
A = np.array(A).reshape(m,n)
b = np.array(b).reshape(m,1)
# Proccess
ans_comb = np.zeros((1,n))
arr_comb = array_combinations(b,n)
matr_comb = matrix_combinations(A,n)
for i in range(int(permutation(n,m))):
if np.linalg.det(matr_comb[i]) != 0:
x = np.linalg.solve(matr_comb[i],arr_comb[i])
ans_comb = np.vstack([ans_comb,x])
ans_comb = np.delete(ans_comb, (0), axis=0)
j = 0
for i in range(len(ans_comb)):
if check_extreme(A, b, ans_comb[j], sym_comb, m):
ans_comb = ans_comb
j = j + 1
else:
ans_comb = np.delete(ans_comb, (j), axis=0)
# Output
return ans_comb


And I am uploading some more tests. https://imgur.com/mjweDyy







python algorithm numpy homework computational-geometry






share|improve this question









New contributor




Andrey Lovyagin is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.











share|improve this question









New contributor




Andrey Lovyagin is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.









share|improve this question




share|improve this question








edited 8 mins ago









200_success

131k17157422




131k17157422






New contributor




Andrey Lovyagin is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.









asked 4 hours ago









Andrey LovyaginAndrey Lovyagin

161




161




New contributor




Andrey Lovyagin is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.





New contributor





Andrey Lovyagin is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.






Andrey Lovyagin is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.












  • $begingroup$
    Can you provide some more information on what exactly is going on, from a math standpoint? Is this actually a polyhedron, or a polytope? In how many dimensions? By "extreme", what do you mean? Euclidean norm from (the origin, an arbitrary point)?
    $endgroup$
    – Reinderien
    4 hours ago










  • $begingroup$
    "there is still no code in public for searching extreme points for polyhedral with n dimensions" - I can nearly guarantee that that isn't the case.
    $endgroup$
    – Reinderien
    4 hours ago






  • 1




    $begingroup$
    @Reinderien I am still in the process of deciphering the question. I have a math background, and I share the mother tongue with OP. My impression is that by extremal points OP means the vertices of a simplex where a certain linear form (defined by A, b, and the condition) achieves an extremum. I could be wrong.
    $endgroup$
    – vnp
    2 hours ago










  • $begingroup$
    @vnp That's kind of what I guessed, and if that's the case, linear programming is a quite well-established field already - with some stuff built right into scipy.
    $endgroup$
    – Reinderien
    2 hours ago










  • $begingroup$
    @Reinderien Agreed. Still deciphering.
    $endgroup$
    – vnp
    2 hours ago


















  • $begingroup$
    Can you provide some more information on what exactly is going on, from a math standpoint? Is this actually a polyhedron, or a polytope? In how many dimensions? By "extreme", what do you mean? Euclidean norm from (the origin, an arbitrary point)?
    $endgroup$
    – Reinderien
    4 hours ago










  • $begingroup$
    "there is still no code in public for searching extreme points for polyhedral with n dimensions" - I can nearly guarantee that that isn't the case.
    $endgroup$
    – Reinderien
    4 hours ago






  • 1




    $begingroup$
    @Reinderien I am still in the process of deciphering the question. I have a math background, and I share the mother tongue with OP. My impression is that by extremal points OP means the vertices of a simplex where a certain linear form (defined by A, b, and the condition) achieves an extremum. I could be wrong.
    $endgroup$
    – vnp
    2 hours ago










  • $begingroup$
    @vnp That's kind of what I guessed, and if that's the case, linear programming is a quite well-established field already - with some stuff built right into scipy.
    $endgroup$
    – Reinderien
    2 hours ago










  • $begingroup$
    @Reinderien Agreed. Still deciphering.
    $endgroup$
    – vnp
    2 hours ago
















$begingroup$
Can you provide some more information on what exactly is going on, from a math standpoint? Is this actually a polyhedron, or a polytope? In how many dimensions? By "extreme", what do you mean? Euclidean norm from (the origin, an arbitrary point)?
$endgroup$
– Reinderien
4 hours ago




$begingroup$
Can you provide some more information on what exactly is going on, from a math standpoint? Is this actually a polyhedron, or a polytope? In how many dimensions? By "extreme", what do you mean? Euclidean norm from (the origin, an arbitrary point)?
$endgroup$
– Reinderien
4 hours ago












$begingroup$
"there is still no code in public for searching extreme points for polyhedral with n dimensions" - I can nearly guarantee that that isn't the case.
$endgroup$
– Reinderien
4 hours ago




$begingroup$
"there is still no code in public for searching extreme points for polyhedral with n dimensions" - I can nearly guarantee that that isn't the case.
$endgroup$
– Reinderien
4 hours ago




1




1




$begingroup$
@Reinderien I am still in the process of deciphering the question. I have a math background, and I share the mother tongue with OP. My impression is that by extremal points OP means the vertices of a simplex where a certain linear form (defined by A, b, and the condition) achieves an extremum. I could be wrong.
$endgroup$
– vnp
2 hours ago




$begingroup$
@Reinderien I am still in the process of deciphering the question. I have a math background, and I share the mother tongue with OP. My impression is that by extremal points OP means the vertices of a simplex where a certain linear form (defined by A, b, and the condition) achieves an extremum. I could be wrong.
$endgroup$
– vnp
2 hours ago












$begingroup$
@vnp That's kind of what I guessed, and if that's the case, linear programming is a quite well-established field already - with some stuff built right into scipy.
$endgroup$
– Reinderien
2 hours ago




$begingroup$
@vnp That's kind of what I guessed, and if that's the case, linear programming is a quite well-established field already - with some stuff built right into scipy.
$endgroup$
– Reinderien
2 hours ago












$begingroup$
@Reinderien Agreed. Still deciphering.
$endgroup$
– vnp
2 hours ago




$begingroup$
@Reinderien Agreed. Still deciphering.
$endgroup$
– vnp
2 hours ago










1 Answer
1






active

oldest

votes


















1












$begingroup$

I created a rudimentary pull request to your GitHub repo. I won't show all of the content here except for the main file:



import numpy as np
import itertools as it
import math
import re


def permutation(m, n):
return math.factorial(n) / (math.factorial(n - m) * math.factorial(m))


def matrix_combinations(matr, n):
timed = list(map(list, it.combinations(matr, n)))
for i in range(n):
timed[i][i][i] = np.asscalar(timed[i][i][i])
return np.array(list(timed))


def array_combinations(arr, n):
timed = list(map(list, it.combinations(arr, n)))
for i in range(n):
timed[i][i] = np.asscalar(timed[i][i])
return np.array(list(timed))


def check_extreme(matr, arr, x, sym_comb, m):
sym_comb = sym_comb.replace(']', '')
sym_comb = sym_comb.replace('[', '')
sym_comb = re.split("[ ,]", sym_comb)
for i in range(m):
td_answer = sum(matr[i] * x)
if sym_comb[i] == '>':
if td_answer <= arr[i]:
return 0
elif sym_comb[i] == '>=':
if td_answer < arr[i]:
return 0
elif sym_comb[i] == '<':
if td_answer >= arr[i]:
return 0
elif sym_comb[i] == '<=':
if td_answer > arr[i]:
return 0
elif sym_comb[i] == '=':
if td_answer != arr[i]:
return 0
elif sym_comb[i] == '!=':
if td_answer == arr[i]:
return 0
else:
return 0
return 1


def extreme_points(m, n, A, b, sym_comb):
# Input
A = np.array(A).reshape(m, n)
b = np.array(b).reshape(m, 1)
# Process
ans_comb = np.zeros((1, n))
arr_comb = array_combinations(b, n)
matr_comb = matrix_combinations(A, n)
for i in range(int(permutation(n, m))):
if np.linalg.det(matr_comb[i]) != 0:
x = np.linalg.solve(matr_comb[i], arr_comb[i])
ans_comb = np.vstack([ans_comb, x])
ans_comb = np.delete(ans_comb, 0, axis=0)
j = 0
for i in range(len(ans_comb)):
if check_extreme(A, b, ans_comb[j], sym_comb, m):
ans_comb = ans_comb
j = j + 1
else:
ans_comb = np.delete(ans_comb, j, axis=0)
# Output
return ans_comb


This is a first cut mainly for PEP8 compliance, and doesn't solve the bigger issue that you should replace 99% of this with a call to scipy. I'll do that separately (I suspect that @vnp is, as well).






share|improve this answer









$endgroup$














    Your Answer






    StackExchange.ifUsing("editor", function () {
    StackExchange.using("externalEditor", function () {
    StackExchange.using("snippets", function () {
    StackExchange.snippets.init();
    });
    });
    }, "code-snippets");

    StackExchange.ready(function() {
    var channelOptions = {
    tags: "".split(" "),
    id: "196"
    };
    initTagRenderer("".split(" "), "".split(" "), channelOptions);

    StackExchange.using("externalEditor", function() {
    // Have to fire editor after snippets, if snippets enabled
    if (StackExchange.settings.snippets.snippetsEnabled) {
    StackExchange.using("snippets", function() {
    createEditor();
    });
    }
    else {
    createEditor();
    }
    });

    function createEditor() {
    StackExchange.prepareEditor({
    heartbeatType: 'answer',
    autoActivateHeartbeat: false,
    convertImagesToLinks: false,
    noModals: true,
    showLowRepImageUploadWarning: true,
    reputationToPostImages: null,
    bindNavPrevention: true,
    postfix: "",
    imageUploader: {
    brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
    contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
    allowUrls: true
    },
    onDemand: true,
    discardSelector: ".discard-answer"
    ,immediatelyShowMarkdownHelp:true
    });


    }
    });






    Andrey Lovyagin is a new contributor. Be nice, and check out our Code of Conduct.










    draft saved

    draft discarded


















    StackExchange.ready(
    function () {
    StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodereview.stackexchange.com%2fquestions%2f217855%2fsearching-extreme-points-of-polyhedron%23new-answer', 'question_page');
    }
    );

    Post as a guest















    Required, but never shown

























    1 Answer
    1






    active

    oldest

    votes








    1 Answer
    1






    active

    oldest

    votes









    active

    oldest

    votes






    active

    oldest

    votes









    1












    $begingroup$

    I created a rudimentary pull request to your GitHub repo. I won't show all of the content here except for the main file:



    import numpy as np
    import itertools as it
    import math
    import re


    def permutation(m, n):
    return math.factorial(n) / (math.factorial(n - m) * math.factorial(m))


    def matrix_combinations(matr, n):
    timed = list(map(list, it.combinations(matr, n)))
    for i in range(n):
    timed[i][i][i] = np.asscalar(timed[i][i][i])
    return np.array(list(timed))


    def array_combinations(arr, n):
    timed = list(map(list, it.combinations(arr, n)))
    for i in range(n):
    timed[i][i] = np.asscalar(timed[i][i])
    return np.array(list(timed))


    def check_extreme(matr, arr, x, sym_comb, m):
    sym_comb = sym_comb.replace(']', '')
    sym_comb = sym_comb.replace('[', '')
    sym_comb = re.split("[ ,]", sym_comb)
    for i in range(m):
    td_answer = sum(matr[i] * x)
    if sym_comb[i] == '>':
    if td_answer <= arr[i]:
    return 0
    elif sym_comb[i] == '>=':
    if td_answer < arr[i]:
    return 0
    elif sym_comb[i] == '<':
    if td_answer >= arr[i]:
    return 0
    elif sym_comb[i] == '<=':
    if td_answer > arr[i]:
    return 0
    elif sym_comb[i] == '=':
    if td_answer != arr[i]:
    return 0
    elif sym_comb[i] == '!=':
    if td_answer == arr[i]:
    return 0
    else:
    return 0
    return 1


    def extreme_points(m, n, A, b, sym_comb):
    # Input
    A = np.array(A).reshape(m, n)
    b = np.array(b).reshape(m, 1)
    # Process
    ans_comb = np.zeros((1, n))
    arr_comb = array_combinations(b, n)
    matr_comb = matrix_combinations(A, n)
    for i in range(int(permutation(n, m))):
    if np.linalg.det(matr_comb[i]) != 0:
    x = np.linalg.solve(matr_comb[i], arr_comb[i])
    ans_comb = np.vstack([ans_comb, x])
    ans_comb = np.delete(ans_comb, 0, axis=0)
    j = 0
    for i in range(len(ans_comb)):
    if check_extreme(A, b, ans_comb[j], sym_comb, m):
    ans_comb = ans_comb
    j = j + 1
    else:
    ans_comb = np.delete(ans_comb, j, axis=0)
    # Output
    return ans_comb


    This is a first cut mainly for PEP8 compliance, and doesn't solve the bigger issue that you should replace 99% of this with a call to scipy. I'll do that separately (I suspect that @vnp is, as well).






    share|improve this answer









    $endgroup$


















      1












      $begingroup$

      I created a rudimentary pull request to your GitHub repo. I won't show all of the content here except for the main file:



      import numpy as np
      import itertools as it
      import math
      import re


      def permutation(m, n):
      return math.factorial(n) / (math.factorial(n - m) * math.factorial(m))


      def matrix_combinations(matr, n):
      timed = list(map(list, it.combinations(matr, n)))
      for i in range(n):
      timed[i][i][i] = np.asscalar(timed[i][i][i])
      return np.array(list(timed))


      def array_combinations(arr, n):
      timed = list(map(list, it.combinations(arr, n)))
      for i in range(n):
      timed[i][i] = np.asscalar(timed[i][i])
      return np.array(list(timed))


      def check_extreme(matr, arr, x, sym_comb, m):
      sym_comb = sym_comb.replace(']', '')
      sym_comb = sym_comb.replace('[', '')
      sym_comb = re.split("[ ,]", sym_comb)
      for i in range(m):
      td_answer = sum(matr[i] * x)
      if sym_comb[i] == '>':
      if td_answer <= arr[i]:
      return 0
      elif sym_comb[i] == '>=':
      if td_answer < arr[i]:
      return 0
      elif sym_comb[i] == '<':
      if td_answer >= arr[i]:
      return 0
      elif sym_comb[i] == '<=':
      if td_answer > arr[i]:
      return 0
      elif sym_comb[i] == '=':
      if td_answer != arr[i]:
      return 0
      elif sym_comb[i] == '!=':
      if td_answer == arr[i]:
      return 0
      else:
      return 0
      return 1


      def extreme_points(m, n, A, b, sym_comb):
      # Input
      A = np.array(A).reshape(m, n)
      b = np.array(b).reshape(m, 1)
      # Process
      ans_comb = np.zeros((1, n))
      arr_comb = array_combinations(b, n)
      matr_comb = matrix_combinations(A, n)
      for i in range(int(permutation(n, m))):
      if np.linalg.det(matr_comb[i]) != 0:
      x = np.linalg.solve(matr_comb[i], arr_comb[i])
      ans_comb = np.vstack([ans_comb, x])
      ans_comb = np.delete(ans_comb, 0, axis=0)
      j = 0
      for i in range(len(ans_comb)):
      if check_extreme(A, b, ans_comb[j], sym_comb, m):
      ans_comb = ans_comb
      j = j + 1
      else:
      ans_comb = np.delete(ans_comb, j, axis=0)
      # Output
      return ans_comb


      This is a first cut mainly for PEP8 compliance, and doesn't solve the bigger issue that you should replace 99% of this with a call to scipy. I'll do that separately (I suspect that @vnp is, as well).






      share|improve this answer









      $endgroup$
















        1












        1








        1





        $begingroup$

        I created a rudimentary pull request to your GitHub repo. I won't show all of the content here except for the main file:



        import numpy as np
        import itertools as it
        import math
        import re


        def permutation(m, n):
        return math.factorial(n) / (math.factorial(n - m) * math.factorial(m))


        def matrix_combinations(matr, n):
        timed = list(map(list, it.combinations(matr, n)))
        for i in range(n):
        timed[i][i][i] = np.asscalar(timed[i][i][i])
        return np.array(list(timed))


        def array_combinations(arr, n):
        timed = list(map(list, it.combinations(arr, n)))
        for i in range(n):
        timed[i][i] = np.asscalar(timed[i][i])
        return np.array(list(timed))


        def check_extreme(matr, arr, x, sym_comb, m):
        sym_comb = sym_comb.replace(']', '')
        sym_comb = sym_comb.replace('[', '')
        sym_comb = re.split("[ ,]", sym_comb)
        for i in range(m):
        td_answer = sum(matr[i] * x)
        if sym_comb[i] == '>':
        if td_answer <= arr[i]:
        return 0
        elif sym_comb[i] == '>=':
        if td_answer < arr[i]:
        return 0
        elif sym_comb[i] == '<':
        if td_answer >= arr[i]:
        return 0
        elif sym_comb[i] == '<=':
        if td_answer > arr[i]:
        return 0
        elif sym_comb[i] == '=':
        if td_answer != arr[i]:
        return 0
        elif sym_comb[i] == '!=':
        if td_answer == arr[i]:
        return 0
        else:
        return 0
        return 1


        def extreme_points(m, n, A, b, sym_comb):
        # Input
        A = np.array(A).reshape(m, n)
        b = np.array(b).reshape(m, 1)
        # Process
        ans_comb = np.zeros((1, n))
        arr_comb = array_combinations(b, n)
        matr_comb = matrix_combinations(A, n)
        for i in range(int(permutation(n, m))):
        if np.linalg.det(matr_comb[i]) != 0:
        x = np.linalg.solve(matr_comb[i], arr_comb[i])
        ans_comb = np.vstack([ans_comb, x])
        ans_comb = np.delete(ans_comb, 0, axis=0)
        j = 0
        for i in range(len(ans_comb)):
        if check_extreme(A, b, ans_comb[j], sym_comb, m):
        ans_comb = ans_comb
        j = j + 1
        else:
        ans_comb = np.delete(ans_comb, j, axis=0)
        # Output
        return ans_comb


        This is a first cut mainly for PEP8 compliance, and doesn't solve the bigger issue that you should replace 99% of this with a call to scipy. I'll do that separately (I suspect that @vnp is, as well).






        share|improve this answer









        $endgroup$



        I created a rudimentary pull request to your GitHub repo. I won't show all of the content here except for the main file:



        import numpy as np
        import itertools as it
        import math
        import re


        def permutation(m, n):
        return math.factorial(n) / (math.factorial(n - m) * math.factorial(m))


        def matrix_combinations(matr, n):
        timed = list(map(list, it.combinations(matr, n)))
        for i in range(n):
        timed[i][i][i] = np.asscalar(timed[i][i][i])
        return np.array(list(timed))


        def array_combinations(arr, n):
        timed = list(map(list, it.combinations(arr, n)))
        for i in range(n):
        timed[i][i] = np.asscalar(timed[i][i])
        return np.array(list(timed))


        def check_extreme(matr, arr, x, sym_comb, m):
        sym_comb = sym_comb.replace(']', '')
        sym_comb = sym_comb.replace('[', '')
        sym_comb = re.split("[ ,]", sym_comb)
        for i in range(m):
        td_answer = sum(matr[i] * x)
        if sym_comb[i] == '>':
        if td_answer <= arr[i]:
        return 0
        elif sym_comb[i] == '>=':
        if td_answer < arr[i]:
        return 0
        elif sym_comb[i] == '<':
        if td_answer >= arr[i]:
        return 0
        elif sym_comb[i] == '<=':
        if td_answer > arr[i]:
        return 0
        elif sym_comb[i] == '=':
        if td_answer != arr[i]:
        return 0
        elif sym_comb[i] == '!=':
        if td_answer == arr[i]:
        return 0
        else:
        return 0
        return 1


        def extreme_points(m, n, A, b, sym_comb):
        # Input
        A = np.array(A).reshape(m, n)
        b = np.array(b).reshape(m, 1)
        # Process
        ans_comb = np.zeros((1, n))
        arr_comb = array_combinations(b, n)
        matr_comb = matrix_combinations(A, n)
        for i in range(int(permutation(n, m))):
        if np.linalg.det(matr_comb[i]) != 0:
        x = np.linalg.solve(matr_comb[i], arr_comb[i])
        ans_comb = np.vstack([ans_comb, x])
        ans_comb = np.delete(ans_comb, 0, axis=0)
        j = 0
        for i in range(len(ans_comb)):
        if check_extreme(A, b, ans_comb[j], sym_comb, m):
        ans_comb = ans_comb
        j = j + 1
        else:
        ans_comb = np.delete(ans_comb, j, axis=0)
        # Output
        return ans_comb


        This is a first cut mainly for PEP8 compliance, and doesn't solve the bigger issue that you should replace 99% of this with a call to scipy. I'll do that separately (I suspect that @vnp is, as well).







        share|improve this answer












        share|improve this answer



        share|improve this answer










        answered 2 hours ago









        ReinderienReinderien

        5,474928




        5,474928






















            Andrey Lovyagin is a new contributor. Be nice, and check out our Code of Conduct.










            draft saved

            draft discarded


















            Andrey Lovyagin is a new contributor. Be nice, and check out our Code of Conduct.













            Andrey Lovyagin is a new contributor. Be nice, and check out our Code of Conduct.












            Andrey Lovyagin is a new contributor. Be nice, and check out our Code of Conduct.
















            Thanks for contributing an answer to Code Review Stack Exchange!


            • Please be sure to answer the question. Provide details and share your research!

            But avoid



            • Asking for help, clarification, or responding to other answers.

            • Making statements based on opinion; back them up with references or personal experience.


            Use MathJax to format equations. MathJax reference.


            To learn more, see our tips on writing great answers.




            draft saved


            draft discarded














            StackExchange.ready(
            function () {
            StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodereview.stackexchange.com%2fquestions%2f217855%2fsearching-extreme-points-of-polyhedron%23new-answer', 'question_page');
            }
            );

            Post as a guest















            Required, but never shown





















































            Required, but never shown














            Required, but never shown












            Required, but never shown







            Required, but never shown

































            Required, but never shown














            Required, but never shown












            Required, but never shown







            Required, but never shown







            Popular posts from this blog

            Liste der Baudenkmale in Friedland (Mecklenburg)

            Single-Malt-Whisky

            Czorneboh