Bsrgvty

Initialising a variable of unknown type via overloaded constructors in C++

Postdoc Fellowships Collision

Was I wrong to rebutt unjustified rewiewer comments in the review?

Is there a difference between LASSO regularisation and LASSO penalisation?

Understanding of big-O massively improved when I began thinking of orders as sets. How to apply the same approach to big-Theta?

Can I rescind my offer of working on weekends after last day?

Find elements of array with largest absolute value

How to practice simple syncopation?

Generic circular doubly linked list

Approximation of homeomorphism by diffeomorphism

The use of ''riddle' in this context

Where do "magic" hashing constants like 0x9e3779b9 and 0x9e3779b1 come from?

Does Magic Stone require an action or a bonus action for attacking with it?

How do I change the return/enter key functionality without breaking enter to select?

How Much Efficiency is Lost in a Gear Train

How exactly did the separation between Saturn V stage 3 and the Command / Lunar Module work?

5yrs old being bossy... Is this too much or tolerable at this age?

How to choose between high number of binary variables or fewer number of integer (not only 0 and 1) variables in a IP formulation?

Why was LEGO reluctant to use additional colours for regular bricks in former times?

pull-ups between logic gates

"Government transplant" been tried? At what scale, and what were the results?

Why can't I shoot with a fast shutter speed?

Why has Trump refused to recognize the Armenian Genocide?

What would have been the typical drinks for a US farmer in the late 18th/early 19th century?

Finding the linear functions defining a polyhedron through integer data?

Working with absolute values in constraint in a LP or MILPProve that these linear programming problems are bounded by $O(k^1/2)$Formulation of a constraint in a MIP for an element in different SetsGenerating all extreme raysLinear and Integer programming materialsTrouble with scheduling problem assumptionsShould I factor in time as a parameter or a variable in a scheduling problem with MILP?A heuristic approach to solve a MILP problem?MIP: If integer variable $>0$ it should be equal to other integer variables $>0$

9

1

$begingroup$

Let's say I have a bunch of linear functions $f_1,cdots,f_n$ in $k$ variables; then $f_1,cdots, f_nle0$ defines a polyhedron $P$ in the $k$-dimensional space.

What I'm looking for is going the other way: given data points inside a polyhedron $P$, is there an efficient/fast way to find the functions $f_1,cdots,f_n$ cutting the polyhedron? Those data points are finitely many integer points (i.e. points whose all coordinates are integers) and $P$ is "the smallest" polyhedron containing them. Basically I require two things:

1. $P$ does not contain any other integer points.




2. The linear functions themselves have integer coefficients.

A naive way would be to loop over all possible candidate functions (their integer coefficients) in a certain range but there should be a much better/faster/efficient way of doing it.

I am not specifically looking for an answer to this problem, rather a reference or direction for where I should be looking at. Has this been studied at all? I understand that this is not exactly what linear/integer programming is about, so apologies if the question is not appropriate for this site.

linear-programming reference-request integer-programming polyhedra

share|improve this question

edited Oct 4 at 0:23

LarrySnyder610♦

8,6811616 silver badges7272 bronze badges

asked Oct 2 at 4:13

user12005284user12005284

9344 bronze badges

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  It might be pretty hard to ensure that $mathbfP$ contains no other integer points. Consider for example the data points $(1,1),(3,1),(1,3),(3,3)$ with the description $mathbfP=xinmathbbR^2:1leq x_1leq 3, 1leq x_2leq 3$. Here the point $(2,2,)$ is contained in $mathbfP$ but not in the list of data points.
  $endgroup$
  – Sune
  Oct 2 at 8:33
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  @Sune My data points are generated through a process that can guarantee I have them all. I am effectively trying to find patterns in that process, that for reasons I won't get to now, I am almost certain will be linear in nature.
  $endgroup$
  – user12005284
  Oct 2 at 14:55
  

  
  
  
  

add a comment
 | 

9

1

$begingroup$

Let's say I have a bunch of linear functions $f_1,cdots,f_n$ in $k$ variables; then $f_1,cdots, f_nle0$ defines a polyhedron $P$ in the $k$-dimensional space.

What I'm looking for is going the other way: given data points inside a polyhedron $P$, is there an efficient/fast way to find the functions $f_1,cdots,f_n$ cutting the polyhedron? Those data points are finitely many integer points (i.e. points whose all coordinates are integers) and $P$ is "the smallest" polyhedron containing them. Basically I require two things:

1. $P$ does not contain any other integer points.




2. The linear functions themselves have integer coefficients.

A naive way would be to loop over all possible candidate functions (their integer coefficients) in a certain range but there should be a much better/faster/efficient way of doing it.

I am not specifically looking for an answer to this problem, rather a reference or direction for where I should be looking at. Has this been studied at all? I understand that this is not exactly what linear/integer programming is about, so apologies if the question is not appropriate for this site.

linear-programming reference-request integer-programming polyhedra

share|improve this question

edited Oct 4 at 0:23

LarrySnyder610♦

8,6811616 silver badges7272 bronze badges

asked Oct 2 at 4:13

user12005284user12005284

9344 bronze badges

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  It might be pretty hard to ensure that $mathbfP$ contains no other integer points. Consider for example the data points $(1,1),(3,1),(1,3),(3,3)$ with the description $mathbfP=xinmathbbR^2:1leq x_1leq 3, 1leq x_2leq 3$. Here the point $(2,2,)$ is contained in $mathbfP$ but not in the list of data points.
  $endgroup$
  – Sune
  Oct 2 at 8:33
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  @Sune My data points are generated through a process that can guarantee I have them all. I am effectively trying to find patterns in that process, that for reasons I won't get to now, I am almost certain will be linear in nature.
  $endgroup$
  – user12005284
  Oct 2 at 14:55
  

  
  
  
  

add a comment
 | 

$begingroup$

Let's say I have a bunch of linear functions $f_1,cdots,f_n$ in $k$ variables; then $f_1,cdots, f_nle0$ defines a polyhedron $P$ in the $k$-dimensional space.

What I'm looking for is going the other way: given data points inside a polyhedron $P$, is there an efficient/fast way to find the functions $f_1,cdots,f_n$ cutting the polyhedron? Those data points are finitely many integer points (i.e. points whose all coordinates are integers) and $P$ is "the smallest" polyhedron containing them. Basically I require two things:

1. $P$ does not contain any other integer points.




2. The linear functions themselves have integer coefficients.

A naive way would be to loop over all possible candidate functions (their integer coefficients) in a certain range but there should be a much better/faster/efficient way of doing it.

I am not specifically looking for an answer to this problem, rather a reference or direction for where I should be looking at. Has this been studied at all? I understand that this is not exactly what linear/integer programming is about, so apologies if the question is not appropriate for this site.

linear-programming reference-request integer-programming polyhedra

share|improve this question

edited Oct 4 at 0:23

LarrySnyder610♦

8,6811616 silver badges7272 bronze badges

asked Oct 2 at 4:13

user12005284user12005284

9344 bronze badges

$endgroup$

share|improve this question

edited Oct 4 at 0:23

LarrySnyder610♦

8,6811616 silver badges7272 bronze badges

asked Oct 2 at 4:13

user12005284user12005284

9344 bronze badges

share|improve this question

edited Oct 4 at 0:23

LarrySnyder610♦

8,6811616 silver badges7272 bronze badges

asked Oct 2 at 4:13

user12005284user12005284

9344 bronze badges

edited Oct 4 at 0:23

LarrySnyder610♦

8,6811616 silver badges7272 bronze badges

edited Oct 4 at 0:23

LarrySnyder610♦

8,6811616 silver badges7272 bronze badges

asked Oct 2 at 4:13

user12005284user12005284

9344 bronze badges

asked Oct 2 at 4:13

user12005284user12005284

9344 bronze badges

1 Answer
1

active

oldest

votes

10

$begingroup$

You are looking for algorithms to find the integer convex hull of a polytope. Unfortunately, there is no easy way to do it efficiently and I am not sure the 2. point (the functions have integer coefficients) is even possible.

I used to do this for studying cutting planes (for small toy problems) using PORTA (http://porta.zib.de/), which is not under development anymore. But there are more modern software packages listed on the PORTA webpage that might be able to do this more efficiently and with more modern algorithms.

If I remember correctly, one algorithm to do this is the double description method, i.e. an algorithm that converts an extreme point and ray representation of a polyhedron into an matrix (inequalities) representation of a polyhedron. That this is possible goes back to the Minkowski-Weyl theorem. Here you can find a paper about that algorithm, there is probably a lot more out there.

share|improve this answer

answered Oct 2 at 8:26

Philipp ChristophelPhilipp Christophel

83611 silver badge1111 bronze badges

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  as the points have integer (in particular rational) data, the functions will have rational (and thus via scaling) integer data.
  $endgroup$
  – Marco Lübbecke
  Oct 2 at 14:32
  

  
  
  
  


• 
  
  
  

  
  2
  

  
  
  
  
  
  

  
  $begingroup$
  Thanks so much for this answer, especially the PORTA software and the DD method. They look to be very close to what I need. Also I can "guarantee" these functions can be chosen to have integer coefficients, the data is random but the process generating it is quite complicated. I will leave this question open for a bit to see if anyone has any other ideas, but otherwise I will accept this answer.
  $endgroup$
  – user12005284
  Oct 2 at 15:00
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  My comment above reads "the data is random but..." but that's a typo and the opposite is true: The data is very much not random, but it is generated in a very complicated process.
  $endgroup$
  – user12005284
  Oct 3 at 4:39
  
  

  
  
  
  

add a comment
 | 

Your Answer

StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "700"
;
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/4.0/"u003ecc by-sa 4.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
);



);

draft saved

draft discarded

Sign up or log in

StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name

Email

Required, but never shown

StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2for.stackexchange.com%2fquestions%2f2711%2ffinding-the-linear-functions-defining-a-polyhedron-through-integer-data%23new-answer', 'question_page');

);

Post as a guest

Name

Email

Required, but never shown

10

$begingroup$

You are looking for algorithms to find the integer convex hull of a polytope. Unfortunately, there is no easy way to do it efficiently and I am not sure the 2. point (the functions have integer coefficients) is even possible.

I used to do this for studying cutting planes (for small toy problems) using PORTA (http://porta.zib.de/), which is not under development anymore. But there are more modern software packages listed on the PORTA webpage that might be able to do this more efficiently and with more modern algorithms.

If I remember correctly, one algorithm to do this is the double description method, i.e. an algorithm that converts an extreme point and ray representation of a polyhedron into an matrix (inequalities) representation of a polyhedron. That this is possible goes back to the Minkowski-Weyl theorem. Here you can find a paper about that algorithm, there is probably a lot more out there.

share|improve this answer

answered Oct 2 at 8:26

Philipp ChristophelPhilipp Christophel

83611 silver badge1111 bronze badges

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  as the points have integer (in particular rational) data, the functions will have rational (and thus via scaling) integer data.
  $endgroup$
  – Marco Lübbecke
  Oct 2 at 14:32
  

  
  
  
  


• 
  
  
  

  
  2
  

  
  
  
  
  
  

  
  $begingroup$
  Thanks so much for this answer, especially the PORTA software and the DD method. They look to be very close to what I need. Also I can "guarantee" these functions can be chosen to have integer coefficients, the data is random but the process generating it is quite complicated. I will leave this question open for a bit to see if anyone has any other ideas, but otherwise I will accept this answer.
  $endgroup$
  – user12005284
  Oct 2 at 15:00
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  My comment above reads "the data is random but..." but that's a typo and the opposite is true: The data is very much not random, but it is generated in a very complicated process.
  $endgroup$
  – user12005284
  Oct 3 at 4:39
  
  

  
  
  
  

add a comment
 | 

10

$begingroup$

You are looking for algorithms to find the integer convex hull of a polytope. Unfortunately, there is no easy way to do it efficiently and I am not sure the 2. point (the functions have integer coefficients) is even possible.

I used to do this for studying cutting planes (for small toy problems) using PORTA (http://porta.zib.de/), which is not under development anymore. But there are more modern software packages listed on the PORTA webpage that might be able to do this more efficiently and with more modern algorithms.

If I remember correctly, one algorithm to do this is the double description method, i.e. an algorithm that converts an extreme point and ray representation of a polyhedron into an matrix (inequalities) representation of a polyhedron. That this is possible goes back to the Minkowski-Weyl theorem. Here you can find a paper about that algorithm, there is probably a lot more out there.

share|improve this answer

answered Oct 2 at 8:26

Philipp ChristophelPhilipp Christophel

83611 silver badge1111 bronze badges

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  as the points have integer (in particular rational) data, the functions will have rational (and thus via scaling) integer data.
  $endgroup$
  – Marco Lübbecke
  Oct 2 at 14:32
  

  
  
  
  


• 
  
  
  

  
  2
  

  
  
  
  
  
  

  
  $begingroup$
  Thanks so much for this answer, especially the PORTA software and the DD method. They look to be very close to what I need. Also I can "guarantee" these functions can be chosen to have integer coefficients, the data is random but the process generating it is quite complicated. I will leave this question open for a bit to see if anyone has any other ideas, but otherwise I will accept this answer.
  $endgroup$
  – user12005284
  Oct 2 at 15:00
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  My comment above reads "the data is random but..." but that's a typo and the opposite is true: The data is very much not random, but it is generated in a very complicated process.
  $endgroup$
  – user12005284
  Oct 3 at 4:39
  
  

  
  
  
  

add a comment
 | 

$begingroup$

You are looking for algorithms to find the integer convex hull of a polytope. Unfortunately, there is no easy way to do it efficiently and I am not sure the 2. point (the functions have integer coefficients) is even possible.

I used to do this for studying cutting planes (for small toy problems) using PORTA (http://porta.zib.de/), which is not under development anymore. But there are more modern software packages listed on the PORTA webpage that might be able to do this more efficiently and with more modern algorithms.

If I remember correctly, one algorithm to do this is the double description method, i.e. an algorithm that converts an extreme point and ray representation of a polyhedron into an matrix (inequalities) representation of a polyhedron. That this is possible goes back to the Minkowski-Weyl theorem. Here you can find a paper about that algorithm, there is probably a lot more out there.

share|improve this answer

answered Oct 2 at 8:26

Philipp ChristophelPhilipp Christophel

83611 silver badge1111 bronze badges

$endgroup$

share|improve this answer

answered Oct 2 at 8:26

Philipp ChristophelPhilipp Christophel

83611 silver badge1111 bronze badges

answered Oct 2 at 8:26

Philipp ChristophelPhilipp Christophel

83611 silver badge1111 bronze badges

answered Oct 2 at 8:26

Philipp ChristophelPhilipp Christophel

83611 silver badge1111 bronze badges