Performance is far from satisfying

[WalterMadelim]

The performance of the utility functions are not satisfying (they don't give results in reasonable time).
Especially the in function, which should has be very easy to give results (If use Gurobi to write a simple convex-combination program, this should be verified in a second).

I conduct the experiment in Euclidean-16 space. The poly is defined by 32 points defined in the 16-by-32 matrix yM.
A test point (in the 16-dim space) is defined in the vector y.
Please check out the code, it just doesn't give results.

import Polyhedra
import Gurobi
function m2vov(mat) return [Vector(c) for c in eachcol(mat)] end
yM = [24.46879703394664 2.616114091880524 2.4715185809304274 2.1396187950919554 2.174059532246913 2.19917201685415 2.3456480253453456 3.1445161566848703 2.0940064396589553 2.620015012823288 2.546388339946783 2.476192287013689 2.034122904925076 2.9006777162073196 2.4378442607921924 2.2501508126527257 0.0 1.667897184448773 1.6159109682973325 3.0759173066528156 2.4439892067127738 2.301326508581662 2.4969339341011727 1.7617818667462155 2.5218026526965542 1.6423808178251933 2.1409668026456985 1.9950352639386895 2.0196361398727856 1.6585134269440789 2.1359418837184143 2.784909279614445; 2.5402917160039116 25.77333322828717 1.90134848722727 2.528663424634159 2.805822501169715 2.313456498322179 2.3903788690256293 1.8611241982142337 2.198177100434352 2.2516164134797783 1.8895526894410994 2.2266199802427753 2.7347012112426667 2.3475699725927126 2.402573680091464 1.6058749874696356 2.088297102610564 0.0 2.7650148331043987 1.7735200450503765 1.5726364014575052 2.257643507849035 1.7817474439622578 1.3629385740274143 2.356721679666441 1.9543066036370536 2.8295146338254216 2.4716914708486244 1.715931176888029 2.9684249753599894 2.3831906391086903 3.2074000552224784; 2.1805325502239885 1.6861848323974435 26.1911579369055 2.3462751464608522 0.7078452281244294 2.322697282767246 2.206375064167377 2.956814574699886 1.9235144021312605 2.36010111451448 2.329268948524775 2.335586232987129 1.7484310459805685 2.1828201910382847 1.6747505459380199 2.0781187063692466 2.0322214126013702 2.3208414265591486 0.0 1.8110585291319679 3.4077462083038226 2.025205368971515 1.3193371501119944 1.2505818484823985 3.083141715549766 1.3815539204906573 2.0637868671266495 1.6871995384071834 2.1473055171714828 1.8822407002022314 2.4971835777488467 2.133474622372291; 1.9128039934989958 2.377670998917811 2.4104463755743315 28.61127852323967 2.06742854649278 2.87074982707165 2.3141799082565377 2.192627675028608 2.592091279176202 1.8673780860783564 2.266917717648885 2.6622905011152302 2.398353368726963 1.9658131184221825 1.6803305528960926 0.6155905008752687 2.382519663227918 2.027779569354112 1.8358369846378675 0.0 2.1921300296238906 1.3618519277375332 2.0954675458825536 1.6287886007478771 1.5023878453611568 2.561393373125879 2.4729219001407072 1.7024688754559145 2.031878289407704 2.199646777827622 2.4275104029368664 3.6271552772898867; 2.094611185941017 2.8021965307404324 0.9193829125249725 2.214795001779845 28.954640722880548 1.9713107731682806 2.125607932833218 2.1350957114879594 2.745738139100508 1.9328599586044524 2.215487388193955 1.8876398702511683 2.427472932375576 1.8752115765965518 2.4490907931788657 2.0593735306220013 2.053258115175874 1.8114024036111667 3.3044117915002094 2.7688311084923454 0.0 2.699919051437521 3.204257418177694 2.5086652869076627 2.2425882317868804 2.63036842063185 2.1681555648850352 2.6402535453772344 2.0534714279580517 2.369608306063273 1.291052181305684 2.51183274847302; 2.1039529101756598 2.294059767520302 2.5184642067951954 3.0023455219861193 1.9555400127956877 26.34922575839723 2.9796143724749107 1.7701555593719889 1.3964717726376432 2.407807075481056 2.9469359370523294 2.863174089498839 2.555820509557353 2.446276176970783 1.802049779597186 1.944649401349618 2.342187074374172 1.9113775974681877 2.1076319016008713 1.461643266868386 2.9634579531379552 0.0 1.1194864555363484 2.392396876922496 3.1366731692306438 2.110708350651228 1.475389164772464 1.4360259657006254 2.19126388948825 1.5824546925191378 2.7129042426017635 2.466036158105427; 2.254002560074045 2.3745557796309424 2.4057156296025157 2.449349244578196 2.113410813867813 2.9831880138821005 24.04357367738752 2.0980367478740356 1.8964416144238607 2.3269100986755835 2.131810621718956 2.3531741173032263 2.078872748226011 2.6704474715365416 2.1068019980417647 2.263490429833156 1.8621579051124906 2.375477733946526 2.6687401263047428 1.9024319078255438 2.5629222788336192 1.7185617582207757 0.0 2.6361691443339508 2.38139801559271 1.50484370815399 1.9394941817068432 2.015609298264674 2.6348999158093847 1.8859554782356966 2.5118314703062947 2.237877123372016; 2.898736171502773 1.6911665889087502 3.0020206202242274 2.1736624914394707 1.9687640726117577 1.6195946808683814 1.9439022279632387 28.72969685422756 1.2602161156134692 2.05516783938274 2.1044049301008347 1.9152487658432384 1.7561113160230233 1.7843530811425135 2.0483643547967585 1.8673613015213006 1.0521385771013585 2.6616336916346017 0.4450894695535121 2.839681616674711 2.0430967153567314 3.404474344709164 2.778712365172625 0.0 3.0691803386758 2.1567815855728467 2.5648017355024257 2.038926927760925 2.9407620656905245 2.2524754592842675 2.719581657942814 1.9387848620217674; 1.7703451927259746 1.9503382293779847 1.8908391859047202 2.4952448338361815 2.5015252384734237 1.1680296323831536 1.664425832762181 1.1823348538625875 24.91877770367074 1.8322590865596118 1.8143336830252748 0.8491991365961374 2.6734429250189855 1.982834427472362 1.7665949531418257 1.8998356534736007 2.3394628819259835 1.955250861132444 2.6852398754583 1.848931156081585 1.2545709048011007 2.837780050832832 2.3386498331808903 3.18640135128203 0.0 2.081507500596683 2.5498361596356385 2.643476619630957 1.758543306972774 1.928226464919106 2.1186570791610984 1.6502767988515474; 2.3109829952107295 2.0184067717438325 2.3420551276083605 1.785160870058758 1.70327628729779 2.1939941645469876 2.109523546334325 1.9919158069522789 1.846888315880032 25.916012588042015 2.2447112071584234 2.2539584732552322 2.0652906108887845 2.2028834398499653 1.522808506487769 1.879291269323549 2.1230973126685306 2.342840667254813 1.9347729672343743 2.1851889476393085 2.8011442375983733 1.8476338427878145 1.8740031316595873 2.134107516423211 1.7808100020507023 0.0 1.5307066121840645 1.4324395498874471 2.0481455889612667 2.0938865998999856 2.15985033184296 1.8875746035679364; 2.363780670262002 1.7827673956329313 2.437647309546433 2.3111248495570638 2.1123280648150695 2.8595473740460386 2.040848417305476 2.167577245598151 1.955387260273473 2.3711355550862008 23.78382670836272 2.753412517745913 1.3057464246763875 1.8565194824226017 2.1359306430353726 1.8295890775709562 0.8989541914940385 2.3374382244487113 1.9814043371765009 2.041106240727646 2.112621586177074 1.1864999020711906 2.206251741044022 2.492769728596206 2.49629778691924 1.5852612792576715 0.0 2.2060485484301284 3.416891558802725 3.2085290175518097 1.9911912042246185 1.7221254010705804; 2.334793607011518 2.1610436761172176 2.4851735836913975 2.7477066227060196 1.8256895365548929 2.8169945161751584 2.303420902572356 2.019630071023166 1.0314617035269458 2.4215918108656194 2.7946215074285234 24.499036285957636 1.4471919930307964 2.380651051268325 2.44803841298941 1.945345768906293 2.02626839775254 2.0995381425884188 1.8785624618424592 1.6585635540887769 3.2793268165868983 1.9924921925873669 1.987377755321707 2.301562513905481 3.557869123443761 2.058212196959744 1.6479057857531179 0.0 2.740474399490953 2.040373613387037 2.3616667411036905 2.5784671778303165; 1.683170517433554 2.4595711996277583 1.6884646891954864 2.274215782828401 2.1559688911899504 2.3000872287443217 1.8195658260057899 1.6509389137135997 2.646151784460443 2.0233702410098218 1.1374017068696478 1.2376382855414456 25.759105486030887 2.2081313944270664 1.695339406230303 2.4778804538262715 2.4195788546231873 2.2583208673056245 2.288223054573641 2.133390766052656 2.113707644410414 1.9211675838872893 2.1916601043688946 2.3592827318290817 1.8704831897800802 1.8668042090698613 3.098958515117322 2.8998232996587188 0.0 1.2945334154335588 2.305395823734276 1.6341209042144331; 2.5429367129482165 2.0656513452102248 2.1160652184856232 1.8348869167560407 1.5969189196433464 2.1837542803901715 2.40435193354874 1.6723920630655096 1.9487546711462396 2.154174454203423 1.681386148848282 2.1643087280113944 2.2013427786594866 26.655805570490543 1.6799363287441271 2.1571789599771924 1.1287494348842033 1.3730091780336349 1.9512263713269575 1.5905548531650144 2.421545552989113 1.7468603992505054 1.3438921115453646 2.329318165776871 1.5669758289681102 1.6711571238175458 2.1136447190265906 1.2627314229160125 2.2488929601767627 0.0 2.1826031964967583 1.7687748338050844; 2.2390512255685198 2.2796030207444042 1.7669435414207864 1.7083523192653804 2.329746104261089 1.6984758510520035 1.9996544280893933 2.0953513047551837 1.8914631648511324 1.633047488876655 2.1197452774964813 2.3906440577679082 1.8474987584981521 1.8388842967795562 23.698895709160123 2.154095383069975 1.967172421071858 1.990464079233279 2.0765284035107814 2.2539286268387917 1.361050257070218 2.8340294755191713 2.238639792647835 2.0160094529845534 1.9486517593084134 2.5542247006696166 2.0909810129814432 1.6290283153478742 2.616066307310768 1.8652636985554734 0.0 2.49434483081084; 1.8391134466074388 1.2706599973009627 1.9580673710303997 0.4313679364229429 1.727784510882612 1.6288311419828216 1.9440985290591701 1.7021039206581121 1.8124595343612935 1.7772859208908216 1.6011593812104523 1.6757070828631775 2.4177954752725066 2.103882597191008 1.9418510522483616 25.2048806230229 2.3169501162571797 2.1981245468465236 1.987924648188344 3.239526015917086 2.237082180243411 1.9290237836974877 1.4004575138200244 2.613909339743923 1.9266805848477344 2.172947403998948 2.2897387334805397 2.194486960760201 1.276428428595403 1.6947394740557458 1.6187583272220483 0.0]
y = [2.213942268387555, 2.24840822001899, 2.0761192498440577, 2.1006090176636554, 2.159991089284715, 2.2444441525587444, 2.215193174509882, 2.0794736136606295, 2.0619575537781043, 1.9267183916544581, 2.094740438570332, 2.15580982236171, 1.9790865851844102, 1.975552982004878, 2.1671040201646368, 2.009795928246596]

v = Polyhedra.vrep(m2vov(yM));
poly = Polyhedra.polyhedron(v);
Polyhedra.hrep(poly)#  way too slow
Polyhedra.in(y, poly) #  way too slow
Polyhedra.ininterior(y, poly) #  way too slow
Polyhedra.volume(poly) #  way too slow

Could you give any method to address this issue?

[blegat]

The default implementation has not be thoroughly optimized, you should try using QHull or CDDLib by using, e.g, poly = Polyhedra.polyhedron(v, QHull.Library())

[WalterMadelim]

But it seems doesn't work. The response is very slow, and it cannot give the correct result. (It reports an error)

julia> poly = Polyhedra.polyhedron(v, CDDLib.Library());

julia> Polyhedra.in(y, poly) #  way too slow
ERROR: ddf_DDMatrix2Poly : Numerically inconsistent
Stacktrace:
  [1] error(::String, ::String, ::String)
    @ Base .\error.jl:44
  [2] myerror
    @ K:\judepot1102\packages\CDDLib\OpQiu\src\error.jl:25 [inlined]
  [3] myerror
    @ K:\judepot1102\packages\CDDLib\OpQiu\src\error.jl:29 [inlined]
  [4] macro expansion
    @ K:\judepot1102\packages\CDDLib\OpQiu\src\ccall.jl:30 [inlined]
  [5] dd_matrix2poly(matrix::Ptr{CDDLib.Cdd_MatrixData{Float64}})
    @ CDDLib K:\judepot1102\packages\CDDLib\OpQiu\src\polyhedra.jl:51
  [6] CDDPolyhedra
    @ K:\judepot1102\packages\CDDLib\OpQiu\src\polyhedra.jl:72 [inlined]
  [7] CDDLib.CDDPolyhedra(matrix::CDDLib.CDDGeneratorMatrix{Float64, Float64})
    @ CDDLib K:\judepot1102\packages\CDDLib\OpQiu\src\polyhedra.jl:87
  [8] getpoly(p::CDDLib.Polyhedron{Float64}, inepriority::Bool)
    @ CDDLib K:\judepot1102\packages\CDDLib\OpQiu\src\polyhedron.jl:63
  [9] getpoly
    @ K:\judepot1102\packages\CDDLib\OpQiu\src\polyhedron.jl:57 [inlined]
 [10] getine(p::CDDLib.Polyhedron{Float64})
    @ CDDLib K:\judepot1102\packages\CDDLib\OpQiu\src\polyhedron.jl:46
 [11] hrep
    @ K:\judepot1102\packages\CDDLib\OpQiu\src\polyhedron.jl:150 [inlined]
 [12] hyperplanetype(p::CDDLib.Polyhedron{Float64})
    @ Polyhedra K:\judepot1102\packages\Polyhedra\2LLjF\src\iterators.jl:175
 [13] _broadcast_getindex_evalf
    @ .\broadcast.jl:709 [inlined]
 [14] _broadcast_getindex
    @ .\broadcast.jl:682 [inlined]
 [15] #31
    @ .\broadcast.jl:1118 [inlined]
 [16] ntuple
    @ .\ntuple.jl:48 [inlined]
 [17] copy
    @ .\broadcast.jl:1118 [inlined]
 [18] materialize
    @ .\broadcast.jl:903 [inlined]
 [19] hyperplanes
    @ K:\judepot1102\packages\Polyhedra\2LLjF\src\iterators.jl:183 [inlined]
 [20] hreps
    @ K:\judepot1102\packages\Polyhedra\2LLjF\src\iterators.jl:356 [inlined]
 [21] _vinh(v::Vector{Float64}, hr::CDDLib.Polyhedron{Float64}, infun::Function)
    @ Polyhedra K:\judepot1102\packages\Polyhedra\2LLjF\src\repelemop.jl:73
 [22] in(v::Vector{Float64}, hr::CDDLib.Polyhedron{Float64})
    @ Polyhedra K:\judepot1102\packages\Polyhedra\2LLjF\src\repelemop.jl:92
 [23] top-level scope
    @ REPL[10]:1

But the y is actually contained in the convex hull of those 32 points in yM. This could be verified in a second by Gurobi and returns the correct convex combination vector.

The convex combination coefficient vector is

coeff_vector = [0.043901908463998135, 0.009383080458039943, 0.0019659622876165143, 0.0, 0.0, 0.0010766715940339843, 0.004546357113973881, 0.004219574124540232, 0.0, 0.0, 0.008897391678412287, 0.0, 0.012389289363110581, 0.013938483117636598, 0.0007807186713566161, 0.0, 0.4264848350991656, 0.0, 0.0, 0.05146837567758367, 0.0, 0.0, 0.0, 0.0, 0.02086821068261842, 0.06927183311122961, 0.0, 0.0501483710506711, 0.26147224196738755, 0.0, 0.019186695538625183, 0.0]

which is generated by the following code, which is in moderate size

import Polyhedra
import Gurobi
import JuMP
import LinearAlgebra

GRB_ENV = Gurobi.Env()
function ip(x, y) return LinearAlgebra.dot(x, y) end
function m2vov(mat) return [Vector(c) for c in eachcol(mat)] end
function JumpModel() return ø = JuMP.Model(() -> Gurobi.Optimizer(GRB_ENV)) end
function is_in(y, yM)
    N, S = size(yM)
    ø = JumpModel()
    JuMP.@variable(ø, c[1:S] >= 0.)
    JuMP.@constraint(ø, sum(c) == 1.)
    JuMP.@constraint(ø, [i = 1:N], y[i] == ip(yM[i, :], c))
    JuMP.unset_silent(ø)
    (_, status) = (JuMP.optimize!(ø), JuMP.termination_status(ø))
    if status == JuMP.OPTIMAL
        return JuMP.value.(c)
    end
end

coeff_vector = is_in(y, yM)

[blegat]

We have the LP implemented in Polyhedra and it's used to remove the redundant points in a V-representation:

Polyhedra.jl/src/redundancy.jl

Lines 191 to 226 in 460b4f0

	function _redundant_indices(rep::Representation, model::MOI.ModelLike, T::Type,
	hull, indices, clean)
	red_indices = Int[]
	isempty(indices) && return red_indices
	λ, cλ, sum_one = _hull(model, T, hull, rep, indices)
	hull_con = MOI.add_constraint.(model, hull, MOI.EqualTo(zero(T)))
	for (i, idx) in enumerate(indices)
	if cλ === nothing
	fix_con = MOI.add_constraint(model, λ[i], MOI.EqualTo(zero(T)))
	else
	fix_con = MOI.transform(model, cλ[i], MOI.EqualTo(zero(T)))
	end
	element = get(rep, idx)
	for (ci, ai) in zip(hull_con, _coord_for_hull(element))
	MOI.set(model, MOI.ConstraintSet(), ci, MOI.EqualTo{T}(ai))
	end
	#if !isone(length(indices)) &&
	if is_feasible(model, _RedundantMessage(element, idx))
	MOI.delete(model, λ[i])
	push!(red_indices, i)
	else
	if cλ === nothing
	MOI.delete(model, fix_con)
	else
	cλ[i] = MOI.transform(model, fix_con, MOI.GreaterThan(zero(T)))
	end
	end
	end
	if clean
	MOI.delete(model, hull_con)
	if !isempty(red_indices)
	rm = Set(λ[red_indices])
	hull = map(h -> MOI.Utilities.filter_variables(vi -> !(vi in rm), h), hull)
	end
	end
	return red_indices

Unfortunately, at the moment, it's only used to check which points are redundant inside a representation, and no check if a point is redundant wrt a given representation, but it should be easy to hook it up.