Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

An Intro to Integer Programming for Engineers: Simplified Bus Scheduling

blog.remix.com

Post reply on HN
Print view View original

11–20 of 26 posts

Re: An Intro to Integer Programming for Engineers: Simplified Bus Scheduling

#11

Post by wolfgke »

ant6n wrote: post #8
repsilat wrote: post #5

Earlier quoted context omitted.

Doubly magical now that computers (and solvers) are so fast. A few times I've thought, "Oh, I could reduce this to a max-flow problem, and write/dig up an algorithm to solve it" before realising it'd just be easier to write it as a linear program (or an integer program "just in case".) And then if weird constraints come along that broke the max-flow reduction, I could usually shoehorn that into the formulation. Can't…

I wrote a sudoku solver in my first year of college using some heuristsics and some sort of branch-and-cut algorithm, in java. It used bit masks to keep track of the state and possiblities, I was pretty proud, spent like weeks on that. Recently I re-implemented in Pulp in an afternoon using ILP. It's similarly fast, both can solve similar sets of problems. But the ILP solution was so much easier and shorter.

> I wrote a sudoku solver in my first year of college using some heuristsics and some sort of branch-and-cut algorithm, in java.

What class of cutting planes did you use in your B&C algorithm (full disclure: I do my PhD on cutting planes, thus I'm interested)?

Re: An Intro to Integer Programming for Engineers: Simplified Bus Scheduling

#12

Post by Alphasite_ »

glangdale wrote: post #2

Integer programming often seems magical. I remember early grad school and seeing "Optimal and Near-optimal Global Register Allocation Using 0–1 Integer Programming" by Goodwin et al, where the very crunchy problem of register allocation was solved largely by punting it to a ILP solver. Gotchas abounded but it was eye opening to see how many hard problems could be solved (or at least adequately approximated) in this f…

Whats the distinction between Integer Programming and Constraint Programming? From a cutlery glance they appear to be the same solution to the same problem...

Re: An Intro to Integer Programming for Engineers: Simplified Bus Scheduling

#13

Post by barrkel »

Alphasite_ wrote: post #12
glangdale wrote: post #2

Integer programming often seems magical. I remember early grad school and seeing "Optimal and Near-optimal Global Register Allocation Using 0–1 Integer Programming" by Goodwin et al, where the very crunchy problem of register allocation was solved largely by punting it to a ILP solver. Gotchas abounded but it was eye opening to see how many hard problems could be solved (or at least adequately approximated) in this f…

Whats the distinction between Integer Programming and Constraint Programming? From a cutlery glance they appear to be the same solution to the same problem...

Integer programming is effectively searching the edge of a convex polygon (polytope for higher dimensions) for an optimal value function, defined in terms of the coordinates of the points in space. The inequalities are planes that subdivide the solution space into permitted and non-permitted domains.

Constraint programming generates lots of potential solutions (combinatorially) and prunes the search tree to make the large numbers tractable.

The intuitions behind the two techniques are quite different.

Re: An Intro to Integer Programming for Engineers: Simplified Bus Scheduling

#14

Post by ant6n »

wolfgke wrote: post #11
ant6n wrote: post #8

Earlier quoted context omitted.

I wrote a sudoku solver in my first year of college using some heuristsics and some sort of branch-and-cut algorithm, in java. It used bit masks to keep track of the state and possiblities, I was pretty proud, spent like weeks on that. Recently I re-implemented in Pulp in an afternoon using ILP. It's similarly fast, both can solve similar sets of problems. But the ILP solution was so much easier and shorter.

> I wrote a sudoku solver in my first year of college using some heuristsics and some sort of branch-and-cut algorithm, in java. What class of cutting planes did you use in your B&C algorithm (full disclure: I do my PhD on cutting planes, thus I'm interested)?

I mean branch-and-bound - i.e. just reject when solution becomes infeasible and back-track. No cutting planes in first year college. ;)

I think the heuristics may have been based on selecting cells that had the least possible solutions, in order to quickly 'zoom in' on the areas where you can quickly prune infeasible solutions.

Re: An Intro to Integer Programming for Engineers: Simplified Bus Scheduling

#15

Post by techwizrd »

I took a number of Operations Research courses in undergrad, and one course was almost entirely on Linear Programming and Integer Programming. I strongly recommend engineers to get familiar with them because they are powerful tools for solving a whole class of really tricky problems.

Re: An Intro to Integer Programming for Engineers: Simplified Bus Scheduling

#16

Post by repsilat »

barrkel wrote: post #13
Alphasite_ wrote: post #12

Earlier quoted context omitted.

Whats the distinction between Integer Programming and Constraint Programming? From a cutlery glance they appear to be the same solution to the same problem...

Integer programming is effectively searching the edge of a convex polygon (polytope for higher dimensions) for an optimal value function, defined in terms of the coordinates of the points in space. The inequalities are planes that subdivide the solution space into permitted and non-permitted domains. Constraint programming generates lots of potential solutions (combinatorially) and prunes the search tree to make the…

> Integer programming is effectively searching the edge of a convex polygon...

Great definition of linear programming. In a sense the thing that makes integer programming hard is that the feasible region is not convex -- for two feasible solutions x and y, ax + (1-a)y for 0aI'd also say that integer programming is a kind of constraint-based programming extended with the addition of an objective function -- we're not just looking for any satisfactory answer, but an answer with a cost or value that cannot be improved upon. You're definitely right that "things called constraint-based programs" tend to be solved in different ways, though (and the languages they're expressed in tend to be nicer, too.)

Re: An Intro to Integer Programming for Engineers: Simplified Bus Scheduling

#17

Post by CGudapati »

barrkel wrote: post #13
Alphasite_ wrote: post #12

Earlier quoted context omitted.

Whats the distinction between Integer Programming and Constraint Programming? From a cutlery glance they appear to be the same solution to the same problem...

Integer programming is effectively searching the edge of a convex polygon (polytope for higher dimensions) for an optimal value function, defined in terms of the coordinates of the points in space. The inequalities are planes that subdivide the solution space into permitted and non-permitted domains. Constraint programming generates lots of potential solutions (combinatorially) and prunes the search tree to make the…

I think your definition of Integer programming is not correct. Integer programming or Mixed Integer Programming assumes that the solution has the all or some variables, integers. Most of the Integer programming models are usually using binary variable to indicate decisions.

Further, I think you tried to describe Linear programming in the beginning of your post. But Linear programming searches the vertices of the polytope and not the edges.

The biggest issue with Integer programming is the lack of convexity of the solution space when compared to Linear programming. So the approach for solving them is very different compared to Linear programming. If I made any mistakes in my post, I welcome to be corrected.

Re: An Intro to Integer Programming for Engineers: Simplified Bus Scheduling

#18

Post by CGudapati »

graycat wrote: post #10
petters wrote: post #3

Earlier quoted context omitted.

Agreed that it seems magical. This is one of the areas where the open-source tools are way behind commercial solvers. Cplex and Gurobi are really impressive pieces of software.

C-PLEX and Gurobi -- R. Bixby.

I had the opportunity of interacting with Gu and Bob Bixby of GuRoBi(& CPLEX). Some of the most talented OR scientists.

Re: An Intro to Integer Programming for Engineers: Simplified Bus Scheduling

#19

Post by graycat »

CGudapati wrote: post #18
graycat wrote: post #10

Earlier quoted context omitted.

C-PLEX and Gurobi -- R. Bixby.

I had the opportunity of interacting with Gu and Bob Bixby of GuRoBi(& CPLEX). Some of the most talented OR scientists.

Thanks. You are ahead of me. I'd heard of Bixby's role but not Gu's.
Post reply on HN