I am trying to solve a fairly common MIP. Here are the problem characteristics.

  1. Multi product , Multi site (sites simultaneously serve as production, demand & inventory storage locations). weekly time buckets
  2. products (unit: cases) can be made only in discrete batch sizes using limited number of shifts/batches at each site during each week.
  3. Transportation is allowed across sites to meet demand at any site
  4. Additionally minimum end of week inventory levels must be met at each location.

The current solution from a solver(gurobi) never reaches an MIP gap of better than 15 % from the best bound.

If this problem does not have fixed batch sizes( can produce any quantity during a shift), it is straightforward. But if not, can someone suggest simple heuristic techniques to solve this kind of MIP?

asked 05 Apr '15, 11:55

VM1's gravatar image

accept rate: 0%

It would be of advantage to state the MIP, or at least the objective function and the most important constraints.

(05 Apr '15, 16:56) JF Meier

Gurobi has already applied some not-so-simple heuristic techniques to your problem. The 15% gap might indicate that Gurobi's solution has an objective value 15% above optimum; but more often Gurobi's solution is optimal or quite close to optimal, and it's only the bound that is 15% off because (informally speaking) the constraints don't give a tight enough continuous relaxation. A heuristic tailored to your problem might or might not give you a better solution than Gurobi's heuristics, and might not give any bound at all.

(05 Apr '15, 19:01) 4er
Be the first one to answer this question!
toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here



Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "Title")
  • image?![alt text](/path/img.jpg "Title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported



Asked: 05 Apr '15, 11:55

Seen: 780 times

Last updated: 05 Apr '15, 19:01

OR-Exchange! Your site for questions, answers, and announcements about operations research.