Skip to Content.
Sympa Menu

cgal-discuss - [cgal-discuss] Extreme Points of Linear Programs

Subject: CGAL users discussion list

List archive

[cgal-discuss] Extreme Points of Linear Programs


Chronological Thread 
  • From: Shuxue Jiaoshou <>
  • To:
  • Subject: [cgal-discuss] Extreme Points of Linear Programs
  • Date: Wed, 19 Oct 2022 09:25:52 +1030
  • Authentication-results: mail2-smtp-roc.national.inria.fr; spf=None ; spf=Pass ; spf=None
  • Ironport-data: A9a23:Xi9cMK5+ewLsl8JTh0Ri6gxRtOnDchMFZxGqfqrLsTDasY5as4F+v moWWWyPPK3eNzD1LtEnbdvio08PupLVy94wGwY5/C88Zn8b8sCt6faxfh6hZXvKRiHgZBs6t JtGMoGowOQcFCK0SsKFa+C5xZVE/fjUAOC6UIYoAwgpLSd8UiAtlBl/rOAwh49skLCRDhiE0 T/Ii5S31GSNhnglbwr414rZ8Ek15ayr6GtC1rADTakjUGH2xyF94K03fvnZw0vQGuF8AuO8T uDf+7C1lkuxE8AFV7tJOp6iGqE7aua60Tqm0hK6aID+6vR2nRHe545gXBYqhei7vB3S9zx54 I0lWZVd0m7FNIWU8AgWe0Ew/y2TocSq9ZefSUVTv/B/wGX+VETQkrZUEXsaEo8n6MtdQkJwz 9sHfWVlghCr34pawZq+Q+how9kqdYzlYNpZtXZnwjXUS/0hRPgvQY2QvY4ejGp23JoUW6qHD yYaQWIHgBDoeB1SKkoaCpM3m/yogWTXfDhRqVbTrq0yi4TW5FIsgOK8aoSPEjCMbeFtpGPIq j3+xlTeJBA7JuKF6xOe8Vv504cjmguiAN5IfFGizdZhj1SXg2ASExYLTkCTuui8kkf4WtRFK kVS9DBGkEQp3EmiT924QhTh5XDY51gTXN1fF+B84waIokbJ3+qHLlAjcQIQK+Y7juMZRwM4+ 3XKvO3TIiM65dV5Vkmh3ruTqDqzPw0cImkDeTIIQGM5Dz/L8N9bYvXnHogLLUKlsjHmMWqvn G3S/UDSk51W3JFbjfzqlbzSq2v0/sChc+Ij2unAsouYAu5RYYekY8m14AGe46oZaomeSVaFs T4PnM32AAEy4XOlxHzlrAYlRunBCxO53Nv03AEH834JqmTFxpJbVdoMiAyS3W8wWir+RRfnY VXIpSRa74JJMX2hYMdfOtzvVZ1zkvi6S46+CZg4i+aihLAhK2drGwk+OiatM5zFzSDAbIlla MjBKJn8ZZrkIfg5lGbeqxghPU8Dn3hinws/tLj0yBOo1bf2WZJmYeZtDbd6VchgtPnsiFyNr b53bpLWoz0CDrCWSnSIqeY7cwpWRVBlXsueg5IMJoa+zv9OQj5J5wn5muN/JeSIXs19yo/1w 51Kch4DlQqh3COdQehIA1g6AI7SsV9EhSpTFUQR0ZyAghDPuK7+t/9NRIh9ZrQ96u1owNh9S vRPKY3KAe1CRn6Ds34RZIX05t4qPhm6pxO8Dwz8ahgGfrlkW1Po/P3gdVDR7yUgNHe8mvY/h LyC7TnlZ6Q/aT5sN+vsU8L3/WiN5SAcvMlQQ3r3JsJifRSw0YpydA30oPwFA+ANDhThwDGl+ R6cKkoar7OVoqse0trAtYabpaiHTsp8GUt7GTHAzLCUbCP1wEuq8bViYs2pIw/PdTrT07qwQ Mlo1NfACe0jsHcWlptjApBp4Lkb5dCyl4RFzw9hImrHX26rBpxkPHOC+8tF7Y9J+ZN0piq0X VCp6PBBGLDUJv7gLkEdFDAlYsuHy/sQvDvYttYxAUfi4R5I7Ki1alpTMzaMmR5iAuNMaq19+ tgYuekS9wCboTgpOIzfjilrqkK9HkZZWKAj7pwnEIvnjzQw8W57YLveNH7SwIqOYNByIEUVM meqpK7dtY99mGvGUVQOTEbo48QMq6gKih5wyH06G2+ogfvA3/8+4w1Q+284TyNT1RR27NhwM WlKaWxwKbm/wDNzoM1lQWqXOhpgASeB8Rfb0Go5l2z+TmipWFfSLWY7B/2/wUAB/09YfRlZ5 Lu9ylu5dRrPY+fKwXIUdWN+jv7sX/hd11fno9+2OdaBE70RQyvXsoX3aUUm8xLYUN4M3mvZr uxUzcNMQKzcNwtLhoYkCoOfhI8ieDrdKENsGfherb40R0fCczSP2B+LGUC7WuVJA9foqUaYK chfFvhjZiSE9hSlj24kXPYXArpOgvQWysIIeerrKU44orKvlGdVn6yKxBfupl0AYotIoZ4mJ 5LzZgCyNDWapUFpll/nqOhGPWuFYuc4WjDs4dDt8Ms1OsIClMpObXAN1qCFuiTJEQl/oDORk gDxR47X6O1A1bVTm5DIIptDIj7tLPXfefm6qlGtgY5eaffKF9nEjCIOi1zdJw8NF6Aga9d2s rWssdDMw0LOuogtYV3Zg5WsE6po5924efh+aObbDSB9s3OZecnO5xAjxTiJGaZRmokA2vj9F hqKVsSgUPU0BfFf/SRxQApDGU8/D6/XUP/RlRmlpa7RNilHgB31F/L5x3rHdmoBSzQpPaf5A QrKu/qDwNBUgYBPJR0cDcFdHJ5KDw7/aJQiauHOm2GUPkuwjnOGn4nSpx4qxDXIK3uDScjEu MOPAlC0cRmpo6jHwe1Iq4E47FVdEH95hvJ2ZU4HvcJ/jzehFmMdMOABKtM8B4pJljDpnoTND N0XgLDO1Q2mNdiFTfn93DgndgKWB+hLJ96gYzJ1pgWbbCC5AI7GC7xknsulD7GaZRO7pNxL6 /lHkpEzAvR16p5sTOcXoPe8hI+LA9vEk2kQ9xmVf9PaWn4j7HZj6JClNAVIXC3DVcrKkS0n4 ITzqX9sGCmGdKI6LSqsl7O51v3UUPMDAgjEtRuy/es=
  • Ironport-hdrordr: A9a23:5XQPk6yZvNa0+91L3vBJKrPwIb1zdoMgy1knxilNoH1uA6ulfq WV9sjzuiWE6wr5NEtBpTniAsi9qBHnhPxICOAqVN/IYOCMghrMEGgN1/qH/9QiIUHDHyxmuJ uIv5IQNDQ4NzZHsfo=
  • Ironport-phdr: A9a23:4uVBYRbulD4bvmWYiHwviuL/LTHT2oqcDmcuAnoPtbtCf+yZ8oj4O wSHvLMx1gSPBtSAoKsfw8Pt8InYEVQa5piAtH1QOLdtbDQizfssogo7HcSeAlf6JvO5JwYzH cBFSUM3tyrjaRsdF8nxfUDdrWOv5jAOBBr/KRB1JuPoEYLOksi7ze+/94PdbglSijewZb1/I BqroQjfq8IbnZZsJqEtxxXTv3BGYf5WxWRmJVKSmxbz+MK994N9/ipTpvws6ddOXb31cKokQ 7NYCi8mM30u683wqRbDVwqP6WACXWgQjxFFHhLK7BD+Xpf2ryv6qu9w0zSUMMHqUbw5Xymp4 qF2QxHqlSgHLSY0/27XhMJ+j6xVvQyvqABkzo7IfI2YLuZycr/Bcd4YQ2dKQ8ZfVzZGAoO5d 4YBEuoBPftXronguVQFsB+wBQi2C+Po0T9Ihnj23bAn2OkmCgHG3BEgHt0TsHvKrtX1Nb0dU eeuzKnIyjXDcuhb2Tj46IfScxAhpeuAUq53ccrU0EQiER7OgVqMp4L/JTyVyvgNvHaB7+pmT e+hi28qpg9vrzWg28shiInEi4ELxl7L+yh0wZo4KcO4RkJnf9OpDoVduzyUOYZ3XM4vQG9lt Scnx7ACpJO2YSkHxZI6zBDRbPyHdpKH4hPlVOuJPzh4mHJlebOlixmu8UitzPD3WMqs0FtSs CZJjt3BumoO2hHT8MSLVOVx8lm71TuAygze7PxPL1oumqrBMZEhx6Y9lpoNvkTHGS/7gED2g 7WXdkUg4+So9v7obqj/qp+SOIJ4lxvyMqspmsy4DuQ4NhYBU3KH9uS70b3v5Uz5QLNUgf0qi qTVrozWKMABqqO6AwJZyJgv5wihAzu839kUgGELLFdfdxKGi4jpNUvOIPf9DfqnmFSskCprx v/bPrL/AJXNL2LMkLD6fbZ97E5c1RE+zd9a551OC7EBJOj/VVP2tNzdFhM5NRe7zP79CNphz oMeRX6PAqiBPa/PqVOI/P4gI/GQZI8JvzbwM+Qq5/H0gn89gFMSYKip3YALZ3ClBfRmOF6UY WHsg9cECWcFpBAyTO3siF2YUD5cfWy+X6wm5mJzNIXzBojKQsWhgaeKwTygNpxQfGFPTF6WQ lnycIDRYPcReD+fau1gmzsfVb+8A9s61Qy+qQL4yrNgNerT5wUXsJvi0J5+4OiFxkJ6ziB9E 8nIizLFdGpzhG5dH1fevYh6qE15kBKY1LRgxuZfHppV7u9IVQEzMdjdyfZ7Apb8QFGJZc+HH XChRNjuGjQtVpQp2dZbeEZgC8ivjBHK2DGqBKI9mLmCBZhy+aXZjDDqP8go83/dz+E6ikU+B M5GNGmonKl6ohPTGp7UnkeYnqGxdaMB9CHI/WaHi2GJuRIQSxZ+BIPCW31XfU7KtZL560fFG qepEqgiOxBdxNSqL6JLbpj0hAwDSqu6ftvZZG21liG7AhPgKqqkSo3sdi1d2SzcDBJBiAUP5 TOcMgN4AC69omXYBTgoFFT1Ykqq//Ms4HW8BlQ5yQ2HdSgDn/K85wIViPqASvgSwqNMuSEvr C9xFUq82NSeAsSJpg5odqFRKd0n51IP2WXcvg17dpuuSsIqzkUebhRqskHv3hJsCoJduccvp XIuigF1LOPQ0V9McS+ZwYGlIqfeeQyQtFikb6/b3E2b0c7DoP9erqRl7Q+55kf1TxlHkT0vy dRe3nqC64+fCQMTVci0SUMr711goLqcZCAh5oTS3HkqMK+uszaE1ch6YYltghumYdpbN7uJU QHoFMhPTdOuNfw3llqoZxUfPOdP3KExNsKiMfCB3eT4WYQo1CLjlmlB7I1nhwiX9zdsV+PK3 p8C2PGfwyOIUj79iBGqtcW9yuUmLXkCW2G4zybjHotYYKZ/KJ0KBWmZKMqy3txihpTpVha07 XabDkgdkI+scBuWNRnm2BFIkF4QqjqhkDe5yDp9l3coqLCe1WrA2baqeB0CM29NDG5s6DWka ZO0ksAHUUqpZg8ylBy4zUn/zqlf4q94KiHfTFxJcC7/M2x5GvHo5/zSPogVsslu7XwfWf/ZA xjSUrPnphoGzy7vV3BTwjw2bXDiu5n0mQB7lHPIKX9yqHTDfsQjjRzb5dHaWbtQxm9cHHg+2 WSRXALmeYXwrrD239/Zv+uzVnysTMhWeCjvl8absTejoHdtClu5luyyndvuFU471zX63p9kT 3atzl60b4/12qC9Ke8icFNvAQq28MpnCpxzkIo5g4oQ3mUyiZCc/H5BmmD2e4Y+u+q2fD8WS DgHzsSAqhPlxV1+I3CIzoXiVnKA6sRkbti+JGgR32huiqICQLfR57tCkyxvp1O+pg+Eevlxk AAWzv424WIbieUE60I9iz+QCbcIEQxELDThwl6WusumovwdNwPNOfCgkVBzlte7APSerxFAD TznL4w6E3Y4790jYgmRliSisse+JIaWNZVJ6lWVi0uS0bQTcslq0KNU3Ww/fjus2B9tg+8j0 U4wg9fj5NLBcyM1u/jhSh9Aam+rOYVJpmCr3f4YxoHMh8iuBskzRW9NBceuFKPyVmpV7KSCV U7GESVg+CjHX+OFQEnHrh8h9iyHEoj3ZSjPdD9AkookFF/FYxYGyAEMAGdjwcV/T1H2gpSnK AAguFVzrhb5skcekLo5cUmiFD6F9EHwLW5rAJmHcEgMt18EuheTaJ3EqLo0RnAQ/4X9/lbUd CrBPFUOVjtPAgvdVjWBdvG47N3EuYB0H8KYKP3DKfWLoO1aDbKTwI63l5Fh9HCKP9mOOX9rC 7s63FBCVDZ3AZaRnTJHUCERmy/XCqzT7B6h5i16qNy++/X3SUru44WIEb5bLdRo/Vi/n66CM +eagCsxJyxf09sAwnrByb5X21B36Wkmbz62DbEJrjLAVorVk65TSgMSMmZ9aJIO4KU70Q1Af 8Xcj5K917J1iOI0F0YQVVHlnZLMB4RCKGW8OVXbQUeTYe7edHubnoetO/n6FeQD6Ycc/we9s juaDUL5azGKlj2zEguqLfkJliaQehpXpIC6dB9pT2nlVtPvLBOhY7oVxXU7x6M5gnTSOCsSK z95JglWrqCA8C5ag/x4AGxG81JqKOCFn2CS6OySefN0+bN7Rz95ke5X+iFw07xO8CRNX+B4g gPXp99q5kyvy6yBlmMhXx1JpTJGwomMuA8xXMeRvokFUnHC8hUX6GyWABlfvNppBOrkvKVIw 8TOnqb+QN+n293R9MoYQcPTLZDfWJLOGRXsET/QSgACSGzyXYk+r0lUkfXX63TM65Zm897jn 50BTrIdX1swRKtyNw==
  • Ironport-sdr: 634f2f05_l/QLLAykLTL8+L6Bkl/lHtGyZ3B7WgH0eJUnJAhEpm/s+th zLTtohfEhQsy5DBBqpG2HH+z1E2N6dwFnnV0knw==

For a Linear Program, I would like to enumerate all its extreme points.

I read the Masters thesis of Christian Helbling (ETH Zurich, 2010):
https://www.research-collection.ethz.ch/handle/20.500.11850/152398

Christian says that he has implemented a program within CGAL, to do
exactly this... However, when I searched CGAL yesterday, I was able to
find such a program ONLY for 2- and 3- dimensions.. I was unable to
find the program for higher dimensions.

Can someone please let me know if such a program exists in CGAL for
higher dimensions, and if so, where in CGAL? Thank you.

Shuxue Jiaoshou


  • [cgal-discuss] Extreme Points of Linear Programs, Shuxue Jiaoshou, 10/19/2022

Archive powered by MHonArc 2.6.19+.

Top of Page