0

Suppose we have N (in this example N = 3) events that can happen depending on some variables. Each of them can generate certain profit or loses (event1 = 300, event2 = -100, event3 = 200), they are constrained by rules when they happen.

event 1 happens only when x > 5,

event 2 happens only when x = 2 and y = 3

event 3 happens only when x is odd.

The problem is to know the maximum profit.

Assume x, y are integer numbers >= 0

In the real problem there are many events and many dimensions. (the solution should not be specific)

My question is:

Is this linear programming problem? If yes please provide solution to the example problem using this approach. If no please suggest some algorithms to optimize such problem.

Eddie Jamsession
  • 1,006
  • 6
  • 24

2 Answers2

1

This can be formulated as a mixed integer linear program. This is a linear program where some of the variables are constrained to be integer. Contrary to linear programs, solving the general integer program is NP-hard. However, there are many commercial or open source solvers that can solve efficiently large-scale problems. For up to 300 variables and constraints, you can use excel's solver.

Here is a way to formulate the above constraints:

enter image description here

If you go down this route, you might find this document useful.

the last constraint in an interesting one. I am assuming that x has to be integer, but if x can be either integer or continuous I will edit the answer accordingly.

I hope this helps!

Edit: L and U above should be interpreted as L1 and U1.

Edit 2: z2 needs to changed to (1-z2) on the 3rd and 4th constraint.

Community
  • 1
  • 1
Ioannis
  • 5,238
  • 2
  • 19
  • 31
  • Seems like correct direction, but I need some time to soak it in :) – Eddie Jamsession Dec 20 '14 at 18:31
  • Cool :) If you would like me to elaborate on how the constraints model the events let me know. In a nutshell, starting from each event on the `x` or `y`, the constraints should lead to unique values of `zi`. Also, the "not occurrence" of events should lead to the `z`s being zero. – Ioannis Dec 20 '14 at 23:52
  • I don't understand the 3rd and 4th constraints, when z2 = 0, it should be 0 <= x - 2 <= 0, but there will be -e <= x - 2 <= e, and similar for second one, why do we need this number 'e' here? – Eddie Jamsession Dec 21 '14 at 10:29
  • I edited it (in `edit 2`) so that it works correctly: `z2 == 1 => x - 2 == 0`. The `epsilon` quantity is added for numerical accuracy: the solution of a linear program uses floating point arithmetic, which means that constraints are correct within a certain tolerance threshold. I would select `epsilon = 10e-8`. Removing the `epsilon` from the formulation [can lead to infeasibilities](http://stackoverflow.com/questions/16001462/solving-an-integer-linear-program-why-are-solvers-claiming-a-solvable-instance). So although conceptually is not needed, it helps in practice. – Ioannis Dec 21 '14 at 10:50
0

A specific answer:

seems more like a mathematical calculation than a programming problem, can't you just run a loop for x= 1->1000 to see what results occur?

for the example:

as x = 2 or 3 = -200 then x > 2 or 3, and if x < 5 doesn't get the 300, so all that is really happening is x > 5 and x = odd = maximum results.

x = 7 = 300 + 200 . = maximum profit for x

A general answer:

I don't see how to answer the question without seeing what the events are and how the events effect X ? Weather it's a linear or functional (mathematical) answer seems rather beside the point of finding the desired solution.

Martin
  • 22,212
  • 11
  • 70
  • 132
  • You don't need to know what the events are you just need to know when they occur (e.g. x > 5 and y <= 2) and how much profit or loss you get from it. Also the brute-force solution is not ok here (because of many dimensions in real problem and a lot of events) that's why I started to work towards linear-programming (or maybe non-linear) optimization. – Eddie Jamsession Dec 20 '14 at 11:52