Hello!

I am sorry if the question has already been posted or it has an obvious answer. I have the following problem: we have an array \(X = \{x_1,x_2,...,x_n\}\) of real numbers and the objective is to minimize the following function:

$$f(x_1,x_2,...,x_n) = \sum_{i=2}^{n} (y_i-y_{i-1})^2$$,

where \(Y = \{y_1,y_2,...,y_n\}\) is a sorted array X.

I am using CPLEX (for Java). Is my solution shown below correct or there is a better way to model it?

$$\sum_{i=1}^{n} x_i \equiv y_i \geq 1, \forall j \in [1,n]$$

$$y_j\leq y_{j+1}, \forall y \in [1,n-1]$$ $$f(x_1,x_2,...,x_n) = \sum_{i=2}^{n} (y_i-y_{i-1})^2$$

asked 29 Jun '12, 09:10

Vera's gravatar image

Vera
113
accept rate: 0%

edited 02 Jul '12, 04:55

fbahr's gravatar image

fbahr ♦
4.6k716

1

Forgive me if I'm misunderstanding, but it's not clear to me what you're trying to do (there are some errors in your notation). It seems that X is a set of numbers that is given to you, and Y is a ordered sorted list of X. But if X is fixed, and Y is a ordered list of X, your objective doesn't seem to serve any purpose.

(29 Jun '12, 11:28) Gilead ♦

A naive but straightforward way to sort a set \(X\) using an MIP is as follows:

$$ y_i = \sum_{j=1}^{n} x_j \delta_{i,j}, \quad i=1,\ldots,n $$ $$ \sum_{j=1}^{n} \delta_{i,j} = 1, \quad i=1,\ldots,n $$ $$ \sum_{i=1}^{n} \delta_{i,j} = 1, \quad j=1,\ldots,n $$ $$ y_i \leq y_{i-1}, \quad i=2,\ldots,n $$

where \(\delta\) is a set of binary variables.

If set \(X\) is an external input to your optimization problem, you should definitely sort it using a more efficient programmatic sorting algorithm.

However, if \(X\) arises from constraints in your optimization problem, then you have no choice but to sort it inside the mathematical program using some formulation like the one above.

EDIT: I neglected to mention that if the elements of \(X\) were decision variables, the first constraint becomes nonlinear and has to be decomposed using yet another MIP formulation (section 2.8, page 7).

link

answered 29 Jun '12, 11:34

Gilead's gravatar image

Gilead ♦
2.3k513
accept rate: 15%

edited 30 Jun '12, 10:03

You are completely right, the information about the function was redundant. I am sorry for this mistake. Thank you very much for the answer on how to sort an array!

(29 Jun '12, 11:38) Vera

I'm not aware of any mathematical formulation of sorting problem but since you're already in a programming environment, why don't you use a sorting algorithm such as merge sort which has a very good complexity, O(n.logn). Even if you succeed in modeling the sorting problem as a mathematical model, even the best algorithm will probably have worse complexity than O(n.logn).

By the way, your first constraint seems not correct. You've a summation over some real numbers which is equal to a variable that it self is greater/equal to 1. Even if this makes sense, it would make all \(y_i\) greater than sum of all \(x_i\).

link

answered 29 Jun '12, 11:46

Ehsan's gravatar image

Ehsan ♦
4.8k31122
accept rate: 16%

You are right, the Merge sort or the Quick sort will do the same job much faster. However, I also need to apply sorting to an array of decision variables. Thank you for your answer!

(29 Jun '12, 11:54) Vera

Unless that sorting is part of the problem formulation, this method of sorting seems not necessary. If this is the case, I would really appreciate if you could share your problem description briefly as I've not seen such formulation before (of course, if this is not against your other obligations).

(29 Jun '12, 12:00) Ehsan ♦

Are you acquainted with Brockett's work on dynamical systems that sort lists?

link

answered 01 Jul '12, 17:18

Rod%20Carvalho's gravatar image

Rod Carvalho
1
accept rate: 0%

Your answer
toggle preview

Follow this question

By Email:

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

By RSS:

Answers

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

Tags:

×191
×127

Asked: 29 Jun '12, 09:10

Seen: 2,092 times

Last updated: 02 Jul '12, 04:55

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