Consider the following optimization problem:

\[ \begin{align} \max ~~ & \sum_{i=1}^{n} f(x_i) \\ \text{subject to~~} & \sum_{i=1}^{n} x_{i} = a \\ & x_{i} \in \{0,\dots,c_i\} \forall i \in \{1,\dots,n\}. \end{align} \]

Here, \(f(x)\) is a non-linear function of \(x\) and is defined for each non-negative integer \(x\). I am interested to know where this class of optimization problems can arise in practice.

Sorry, but I tried my best to use MathJax. It seems that this tutorial does not work here.

asked 10 Oct '17, 08:38

Opt1989's gravatar image

Opt1989
1076
accept rate: 0%

edited 11 Oct '17, 15:37

Paul%20Rubin's gravatar image

Paul Rubin ♦♦
14.6k412

1

MathJax on this site is funky, to put it charitably. For future reference, you might find this question helpful: https://www.or-exchange.org/questions/9930/what-format-could-i-post-equations-in-or-exchange.

(11 Oct '17, 15:38) Paul Rubin ♦♦

The case of \( c_i=1 \forall i \in \{1, \ldots, n \} \) resembles the best subset selection problem in regression, for a suitable loss-measuring objective function (so your maximization would need to be converted to minimization).

link

answered 13 Oct '17, 08:55

AndyT's gravatar image

AndyT
6788
accept rate: 7%

edited 13 Oct '17, 11:51

Paul%20Rubin's gravatar image

Paul Rubin ♦♦
14.6k412

If we change the objective function to \(\min \, \sum_{i} f_i(x_i)\), there are several potential applications in supply chain management. One is splitting an order for \(a\) units of a part across multiple suppliers with different price schedules (which could include quantity discounts). Another is splitting a production lot of \(a\) identical items across multiple machines (minimizing the total cost, with possible economies or diseconomies of scale on each machine). A third is splitting a load of \(a\) items across multiple carriers (whose costs depend on load quantity). Some of those examples might make sense if all cost functions were identical (drop the subscript on \(f\)), some maybe not so much.

For maximizing, maybe something like allocating \(a\) sales people or repair people to different regions, where the objective maximizes sales made, downed power lines restored, or whatever.

link

answered 13 Oct '17, 13:42

Paul%20Rubin's gravatar image

Paul Rubin ♦♦
14.6k412
accept rate: 19%

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:

×79
×53
×29
×2

Asked: 10 Oct '17, 08:38

Seen: 275 times

Last updated: 13 Oct '17, 13:42

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