1
$\begingroup$

The basic form of my problem is as follows. Let $S = \{ 1, 2, ..., 30 \}$. I have an integer-valued function $f$, whose argument is an integer-valued vector $\vec{x} \in S^{200}$. I also know that this function is non-decreasing in $x$. I also have access to a function $g$ which returns the derivative of the function $f$ at a given point $x \in S^{200}$.

My first question is: what is the right formulation of this problem, in particular, what are the trade-offs of the various ways to express the decision variables? e.g. integer valued variables $\vec{x} = \{ x_1, x_2, ..., x_{200} \}$ taking on values from $S$ versus binary variables $x_{i, j}$ for each $i = 1 \to 200$ and $j = 1 \to 30$, as well as a set of constraints enforcing that only one such variable can be set for each $i = 1 \to 200$.

Secondly, I then want to model more complex constraints in addition to the above, what possible approaches should I consider? For example, I would like to introduce an additional set of variables $\vec{y} = \{ y_1, y_2, ..., y_{1000} \}$ also taking on values from $S$, such that each variable $x_i \in \vec{x}$ is a linear function of the variables $\vec{y}$.

How does this change the classification of my problem and which approaches should I consider?

I have only a high-level understanding of operations research and numerical optimization (my background is in combinatorics, so please go easy on me). I am working in Python, and would also like to know which libraries and/or solvers would be suitable for solving my problem. As I understand, it could be possible to run gradient descent given access to the derivative of this function to obtain a solution. I am also considering exploring derivative-free approaches such as genetic algorithms and so on.

$\endgroup$
2
  • $\begingroup$ The unconstrained problem is trivial. If $f$ is nondecreasing and you are maximizing it, then $x=(30,\dots,30)$ is guaranteed to be an optimum (not necessarily unique). Two questions might help clarify the constrained problem. First, if $h$ is the function mapping $y$ to $x,$ is $h$ a surjection? Second, are you interested in heuristic methods (not guaranteed to produce an optimal solution) or just exact methods (guaranteed optimum assuming enough time and memory)? You mentioned GAs, so I'm guessing you would be interested in heuristics. $\endgroup$
    – prubin
    Feb 23 at 23:06
  • $\begingroup$ Pardon me... it was late when I posted that -- the constrained problem is really what I'm interested in. To answer your questions: yes, the function $h$ is indeed surjective (however I would be interested to understand what happens when it is not). I am very interested in heuristic methods as well, if computing an optimal one is not tractable as my problem scales. Thanks for your help! $\endgroup$
    – j x
    Feb 24 at 8:45

2 Answers 2

2
$\begingroup$

For the modelling question, I would say that if there is really more difference between $x_i = 1$ and $x_i = 20$ than between $x_i = 19$ and $x_i = 20$, then using integers might be more relevant.

On the other hand, solvers work better with binary variables. For example, a MINLP solver can deduce new bounds for variables but cannot remove a specific value from its domain. Therefore, with integer variables, if the solver deduces than $x_i$ cannot be equal to $19$, it won't take advantage of the information. While with binary variables, it can just set the upper bound of $x_{i,19}$ to $0$.

Using binary variables might also increase significantly the size of the model and slow down the resolution.

In the end, you should experiment with both.

Bonmin (free, open-source) and Knitro (commercial) are the best suited solvers to solve problems with black box functions with derivatives and integer (and possibly continuous) variables.

Another alternative could be to look at derivative-free optimization solvers such as Nomad

$\endgroup$
1
$\begingroup$

Let me start with a bit of terminology: we will say $x^{(1)}$ dominates $x^{(2)}$ if $x^{(1)}_i \ge x^{(2)}_i$ for all $i$ and $x^{(1)}_i \gt x^{(2)}_i$ for some value of $i.$ Since $f()$ is nondecreasing and you are maximizing, at least one optimal solution will occur at a point $x$ nondominated in $S^{200}.$ (There may also be one or more optimal solutions at dominated points.)

I can propose a heuristic, but I cannot predict how well it will work. Consider the integer linear program \begin{align*} \max w^{\prime}x\\ \textrm{s.t. }x & =h(y)\\ x & \in S^{200}\\ y & \in S^{1000} \end{align*} where $h()$ is your linear transform from $y$ to $x$ and $w>>0$ is a strictly positive randomly generated weight vector. The optimal solution to the problem is a nondominated point in $S^{200}.$ Evaluate $f()$ at that point and declare the point the initial incumbent. Now draw a new random $w$ and repeat the process. If the new solution $x$ produces a larger value of $f(),$ record it as the new incumbent and repeat ad nauseum. It might (or might not) be useful to hot-start each IP solution either from the previous solution $(x, y)$ or from the incumbent solution, both of which remain feasible since we never alter the constraints.

How well this might work would clearly depend in large part on how quickly the ILPs could be solved. On the bright side, it avoids having to deal directly with the nonlinearity of $f().$

$\endgroup$
2
  • $\begingroup$ Thanks for your suggestion. It seems like a sensible approach so I will give it a try. I am curious as to why it does not somehow make use of the derivative? Is there any other obvious approach that you'd try which does? Thanks! $\endgroup$
    – j x
    Feb 25 at 22:12
  • $\begingroup$ It's not clear how much information the gradient provides, given that (a) we already know $f$ is nondecreasing and (b) $x$ is integer-valued, and derivatives tell you "instantaneous" rates of change. Mainly, though, I wanted to keep the ILP objectives linear in the hopes that it would make solving them computationally tolerable. $\endgroup$
    – prubin
    Feb 26 at 3:47

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.