Hey All,

I need to solve a problem of this form: Find (n) and (X_1,...,X_n) such that the constraint (C(X_1,...,X_n)) is satisfied and (G(X_1,...,X_n)) is minimized. In other words, the number of variables itself is unknown and need to be found by the solver. The naive approach is to repeatedly invoke the solver for (n=1,2,3,...) and stop after a number of iterations. However, this is a very expensive process and is not guaranteed to find the global optimum. Is there a systematic way of handing this type of optimization setting, i.e. by somehow reducing it into an equivalent problem but with a fixed number of variables? Is there a solver that can handle this type of optimization? Does matlab have any features to solve this type of problem? What if we're also looking for a robust solution (i.e., the actual problem is a robust optimization problem)?

asked 06 Feb '12, 19:07

sina's gravatar image

sina
10126
accept rate: 0%

edited 20 Feb '12, 11:44

fbahr's gravatar image

fbahr ♦
4.6k716

@sina: Two quick questions:

1) Are the variables continuous or discrete?

2) Is there any upper bound on the maximum number of variables based on the problem infromation?

(06 Feb '12, 22:35) Ehsan ♦

3) Are C and G arbitrarily chosen?

(07 Feb '12, 05:55) Thiago Serra

1) variables are continuous.

2) there are no trivial bounds

3) Yes in general C and G are arbitrary, although in the problem setting that I am dealing with (C=sum_{i=1}^n c_i/X_i) where (c_i)'s are constants.

(07 Feb '12, 05:58) sina
1

I know you want to know in general, but it might be better to tackle your specific case first and see what insights you get. Even if your method for solving your case doesn't generalize at all, at least you solve your case.

Can you exploit some information about the constants (c_i)? Where do they come from? Can you tell us what G is?

(07 Feb '12, 11:45) Luis de la T...

Is (c_i) an infinite dimensional vector? If not, you have a bound on the number of variables.

(07 Feb '12, 16:58) Paul Rubin ♦♦

In this generality, we probably cannot help. I am sure that -- even when C and G are generic, they are not arbitrary, they have a meaning! -- your variables are not entirely arbitrary either but taken from some (possibly infinite, but well-described) set. What do we know about this set? [yes, I think about column generation]

(07 Feb '12, 17:28) Marco Luebbecke ♦
2

All the comments so far are very good for more precise problem definition. However, I've another concern. As far as I know, unknown number of decision variables (not unknown number of things to select, e.g. which facilities to open, which vehicles to use, or which products to produce) is a sign of incorrect modeling or lack of enough information about the system structure. If @sina could give us examples for applications of such problem definition, maybe it would help with solving the problem modeling as well.

(08 Feb '12, 00:48) Ehsan ♦
showing 5 of 7 show 2 more comments
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

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:

×79
×4
×2

Asked: 06 Feb '12, 19:07

Seen: 1,892 times

Last updated: 20 Feb '12, 11:44

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