1
$\begingroup$

I want to learn a bit about Linear Programming.

After some research, I decided to solve the Cutting Stock problem as an example to learn. After doing some more research, I feel like I finally understand Linear Programming enough to use a 3rd party solver to solve the problem. Yet, I've only found a suitable solver for non-integer solutions. Using this type of solver is it possible to solve the tighter integer constraints problem?

If so, can someone please post some resources that I can use to read and perhaps implement an integer solver using an existing solver.

My understanding of this topic is EXTREMELY low, and I'm simply looking to learn more about it, so if the problem as I have stated it doesn't make sense, please let me know.

Thanks.

Improve this question
$\endgroup$

3 Answers 3

Reset to default
3
$\begingroup$

I'd recommend you start by consulting the Linear Programming FAQ.

As for a solver, I'd recommend GLPK, which is free and can handle integer linear programming.

Improve this answer
$\endgroup$
2
$\begingroup$

Its worth pointing out that if you add integer constraints to a linear program, the problem of solving it becomes NP-hard. There are software packages that will attempt to solve these for you (e.g. CPLEX), and often succeed on very large instances. Nevertheless, for this reason, if you want an exact solution to an integer linear program, you shouldn't expect there to be a generic reduction (using only a polynomial number of variables and constraints) to solve it using an LP solver.

In fact, (even though it is not known whether P = NP), it is known that linear programs are somewhat limited. For example, solving the travelling salesman problem using a (symmetric) linear program provably requires exponential size. This is a result of Yannakakis: http://portal.acm.org/citation.cfm?id=62232

Improve this answer
$\endgroup$
1
$\begingroup$

I don't know if you're more interested in using solvers or understanding the basics, but from the latter perspective, the problem of using LPs to get integer solutions comes under a very fascinating area termed 'rounding'. In brief, there are ways to take a solution to an LP and systematically transform the variables to integers while preserving closeness to the LP solution.

This then guarantees (since the LP is a lower/upper bound on the IP) that the resulting integer solution is close to the optimal solution. One simple example of a rounding strategy for [0,1] variables is for a variable $x$ to toss a coin with probability of heads being $x$, and then set x to 1 if the coin returns heads. There are many more involved strategies for other problems as well. Best to google 'rounding LPs' or 'randomized rounding'

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .