Discrepancy in computing facets of a mixed integer program

Questions and problems about using polymake go here.

Moderator: Moderators

UserCplex
Posts: 22
Joined: 11 Jan 2018, 13:37

Re: Discrepancy in computing facets of a mixed integer program

Postby UserCplex » 27 Feb 2018, 02:48

Hi opfer,

Thank you very much for the inputs. They are very helpful.

opfer
Developer
Posts: 68
Joined: 04 Feb 2013, 11:12

Re: Discrepancy in computing facets of a mixed integer program

Postby opfer » 27 Feb 2018, 06:42

Hi,

if you don't find the solution, could you post your 3104 points and the code you use to find the facets?

By the way: you have 32 factes (not 31) as you for some reason start counting at 0.

Best regards,
Thomas

UserCplex
Posts: 22
Joined: 11 Jan 2018, 13:37

Re: Discrepancy in computing facets of a mixed integer program

Postby UserCplex » 27 Feb 2018, 06:51

Sure Thomas.

Here is the code to get the facets once I have the integer lattice points (3104 in number)

Code: Select all

use application "polytope"; use vars qw($s $M $l $L @lines @keys $novars); open($l, "<varname.txt") || die "Error : $!"; my @lines = <$l>; close($l); my @keys = split( /\s+/,$lines[0]); open($L, "<points.txt") || die "Error : $!"; my $M = new Matrix<Rational>(<$L>); close($L); reset_preference "*.convex_hull"; prefer_now "ppl"; $s = new Polytope<Rational>(POINTS=>$M, COORDINATE_LABELS=>[@keys]); print_constraints($s);
The files accessed in code above are output from cplex and they are provided as attachment. OOps...I am unable to attach the files, since they are too large for the system 1.3 MB in size.

Roughly "points.txt" has 3104 rows, one for each point, with coordinates space separated. The "varname.txt" file is the exact same file but one extra top row which includes the variable names space separated, both files are output from cplex.

Regards

opfer
Developer
Posts: 68
Joined: 04 Feb 2013, 11:12

Re: Discrepancy in computing facets of a mixed integer program

Postby opfer » 27 Feb 2018, 08:26

Hi!

Could you try to zip the file and attach it afterwards? If this still does not work, could you upload it somewhere?

Best regards,
Thomas

UserCplex
Posts: 22
Joined: 11 Jan 2018, 13:37

Re: Discrepancy in computing facets of a mixed integer program

Postby UserCplex » 27 Feb 2018, 08:59

Sure. Attaching the zipped file.
Attachments
points.zip
(75.53 KiB) Downloaded 33 times

opfer
Developer
Posts: 68
Joined: 04 Feb 2013, 11:12

Re: Discrepancy in computing facets of a mixed integer program

Postby opfer » 27 Feb 2018, 20:22

Hi,

if I add the output of "Affine hull:" (189 constraints) instead of "Facets:" (32 constraints) to the IP and make in an LP, then I obtain 178 as optimal value. (Adding the factes yields 163.429 .) I hope my colleagues can explain this. I am not an expert on how Polymake handles LPs/polyhedra.

Best regards,
Thomas

UserCplex
Posts: 22
Joined: 11 Jan 2018, 13:37

Re: Discrepancy in computing facets of a mixed integer program

Postby UserCplex » 28 Feb 2018, 02:30

Hmm...that does seem strange. The facets of the convex hull H of an IP's feasible region should suffice to solve the IP with linear objective function. The affine hull, A, is a superset of the feasible integer region. But I am guessing that while A contains H, A need not necessarily contain L, where L is the linear programming relaxed feasible region of the IP. (I could be wrong. My real analysis is a bit rusty by now.)

That may explain why when adding the constraints pertaining to A to L, we get A\intersect L to be tighter than L.

Unless I am missing something obvious, this seems like a bug in polymake.

User avatar
gawrilow
Main Author
Posts: 330
Joined: 25 Dec 2010, 17:40

Re: Discrepancy in computing facets of a mixed integer program

Postby gawrilow » 01 Mar 2018, 20:46

... Unless I am missing something obvious, this seems like a bug in polymake.
Sorry, I've kind of got lost in the lengthy discussion, it contains several possible solutions to the same problem achieved after different roundings and other modifications. Could you please reformulate this claim as a self-contained reproducible task, like this:

"Given a system of linear inequalities A*x <= B and objective function C, I expect the optimal solution V attained with x = X, with all A, B, C, V and X specified as rationals or integers."

Then we can debug it.

User avatar
gawrilow
Main Author
Posts: 330
Joined: 25 Dec 2010, 17:40

Re: Discrepancy in computing facets of a mixed integer program

Postby gawrilow » 01 Mar 2018, 22:09

I am not an expert on how Polymake handles LPs/polyhedra.
There is absolutely no magic. You create a Polytope object with INEQUALITIES and EQUATIONS, then add an LP subobject with LINEAR_OBJECTIVE vector and ask for LP.MINIMAL_VALUE or LP.MAXIMAL_VALUE or LP.MINIMAL_VERTEX or LP.MAXIMAL_VERTEX. Depending on your current preferences, either your implementation of the simplex algorithm (TOSimplex) or that from lrslib or cddlib is executed.

opfer
Developer
Posts: 68
Joined: 04 Feb 2013, 11:12

Re: Discrepancy in computing facets of a mixed integer program

Postby opfer » 01 Mar 2018, 23:14

There is absolutely no magic. You create a Polytope object with INEQUALITIES and EQUATIONS, then add an LP subobject with LINEAR_OBJECTIVE vector and ask for LP.MINIMAL_VALUE or LP.MAXIMAL_VALUE or LP.MINIMAL_VERTEX or LP.MAXIMAL_VERTEX. Depending on your current preferences, either your implementation of the simplex algorithm (TOSimplex) or that from lrslib or cddlib is executed.
This is not what I meant. I could reproduce the "problem". If I take an appropriate integer program, I get points as lattice points. If I create a new polytope out of these points and ask for the polytope's facets and add these facets to the IP and convert the IP to an LP, then the objective value is still better than the IP optimal value. I would have expected that they have the same optimal value as the "facets" should define the polytope. Maybe, polymake and I, we have a different understanding of the term "facets". If I take the affine hull constraints and add them instead, then the optimal values coincide.

Best regards,
Thomas


Return to “Helpdesk”

cron