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

accept rate: 0%

edited 11 Oct '17, 15:37

Paul%20Rubin's gravatar image

Paul Rubin ♦♦


MathJax on this site is funky, to put it charitably. For future reference, you might find this question helpful:

(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).


answered 13 Oct '17, 08:55

AndyT's gravatar image

accept rate: 7%

edited 13 Oct '17, 11:51

Paul%20Rubin's gravatar image

Paul Rubin ♦♦

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.


answered 13 Oct '17, 13:42

Paul%20Rubin's gravatar image

Paul Rubin ♦♦
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



Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text]( "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



Asked: 10 Oct '17, 08:38

Seen: 521 times

Last updated: 13 Oct '17, 13:42

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