2
$\begingroup$

I'm working on a MIP optimization problem where I'm trying to reorganize a list of purchases (negative integer numbers) and requests (positive integer number) to maximize the number of positive values in the cumulative_sum array, while minimizing the number of requests movements. Only the requests can "jump", the relative position of purchase should not change. For ex:

-1 cumsum: -1
-7 cumsum: -8
5  cumsum: -3

cumsum array = [-1,-8,-3], number of positive values in the cumsum array = 0. As I result I expect:

5  cumsum: 5
-1 cumsum: 4
-7 cumsum: -3

number of positive values in the cumsum array = 2 My issue is on the objective function. The first objective (number of positive values in the cumsum array) could be be even order of thousands, while the jump parts, provided a jump = 1, can be 10. How to tackle this problem? Or maybe I can move the cumsum part in a constraint?

$\endgroup$
4
  • $\begingroup$ What do you mean by "maximize the positive cumulative sum"? The overall cumulative sum is a constant (-3 in your example). Are you trying to maximize the number of list entries where the cumulative sum is positive? Also, do you consider a jump of one position equivalent (in objective terms) to a jump of, say, five positions, or does the objective contribution depend on the distance jumped? $\endgroup$
    – prubin
    Jan 4 at 16:25
  • $\begingroup$ thanks for replying. I ve edited my post, hoping now is more clear. In principle a jump is a jump, no matter the old-new positions. My issue is that I have two objective functions and I do not know what to look at to rescale them. What I would like to have is: the minimum jumps to have the all the cumsum values positive (or as much as it can). $\endgroup$ Jan 5 at 11:32
  • $\begingroup$ It sounds as if you might have a "preemptive priority" problem. Is it correct to say that you would not be willing to reduce the number of positive cumsum values by 1 even if it would eliminate a large number of jumps? $\endgroup$
    – prubin
    Jan 5 at 16:31
  • $\begingroup$ thanks again for replying. Yes, exactly, I would not. I want "at the same time" obj1:min number of jumps that can give the obj2: max number-of-positive-cumsum-values, where obj2 is "more important". I would like an advice on what to start looking at: multi objective with epsilon constraint? trying to guess a good weight? find a result and then use heuristics? is it a preemptive priority problem? I ve never implemented something like that so I m just looking for suggestions :) $\endgroup$ Jan 5 at 17:59

1 Answer 1

0
$\begingroup$

Based on comments, you might consider a "lexicographic" multiobjective model with two objectives: (1) maximize the number of cumulative sums that are positive; and (2) minimize the number of jumps. In the lexicographic approach, objective (1) has "preemptive" priority over objective (2), meaning no improvement in (2) justifies a sacrifice in (1).

Once upon a time, solving a lexicographic bicriterion model meant solving a MIP to maximize (1), then locking in the optimal value of (1) as a constraint and solving the modified MIP to minimize (2). That is still an option, but some solvers (definitely CPLEX, I'm pretty sure Gurobi, and I think Xpress) have built-in support for lexicographic multiobjective models. My impression is that they modify the branch-and-bound approach so that a node that equals (to within tolerance) the incumbent value of the first objective is not pruned unless its second objective is worse than the incumbent (with this logic generalized when there are three or more objectives). So, basically, they solve a single MIP model, taking all objectives into consideration.

$\endgroup$
1
  • 1
    $\begingroup$ I m using gurobi multi objectives and it works perfectly! model.setObjectiveN(cumsum_sum, index=0, priority=2, name="Obj1") model.setObjectiveN(movements, index=1, priority=1, name="Obj2") thanks! I ve been learning a lot of new stuff :) $\endgroup$ Jan 6 at 16:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.