All Questions
Tagged with nonlinear-optimization integer-programming
16 questions
0
votes
1
answer
60
views
Optimizing sum of discrete minimum
Please consider the following optimization problem: Given a fixed positive natural $n < N$, and a set of functions $f_i$ over a finite domain of nonnegative outputs, s.t. $1 \le i \le N$, then we ...
- 103
0
votes
1
answer
169
views
How to integrate an indicator function/constraint into the cost function of a linear program?
I have a mathematical model $P$ for which I optimize two cost functions say $F_1$ and $F_2$ subject to a set of constraints $C1$–$C10$.
In $F_2$, I want it to be included only when its expression ...
- 3
2
votes
1
answer
274
views
Can we say this nonlinear integer programming problem is NP-hard?
I was wondering if the following nonlinear integer programming problem is NP-hard or not.
$$\max_{x_i \in \{0,1\}} \frac{\sum_{i=1}^{n}a_i x_i}{\sqrt{\sum_{i=1}^{n}b_i x_i}}$$
such that $\sum_{i=1}^{n}...
- 21
0
votes
1
answer
93
views
How quickly can this IQP or its MILP relaxation be solved
Let $A\in\{0,1\}^{(n,n)}$ be a $n$ by $n$ boolean matrix (in particular think of an adjacency matrix of a graph), and consider the following optimization problem:
$$\begin{align*}&&\max_{P\in\{...
- 71
0
votes
1
answer
100
views
Formulating a problem as a mixed-integer conic program
I have the following integer optimisation problem, and I wonder whether it can be reformulated as a conic program that can be solved with, e.g., Mosek. Suppose the $n$-dimensional vectors $a, b$ and $...
- 13
0
votes
1
answer
128
views
What is the computational complexity of the calculation of $ \Psi(x) $?
What is the computational complexity of the calculation of $ \Psi(x) $ described below:
Let $\left\{ f_i : \{0,1,\dots,m\} \to \mathbb{R} \right\}_{i=1}^n$. For each $x \in \{0,1,\dots,m\}$ we ...
2
votes
0
answers
406
views
Pros and cons of using integer programming alone or combined integer and global optimization?
First, I am not sure if this is the right question to ask in this forum. But I have been looking for answers for a long time and I have been also asking my university's "engineering" professors but I ...
1
vote
0
answers
101
views
How to solve such integer program problem?
Consider a $3$-tuple $(a,b,s)$ with $a,b\in\mathbb{Z}_+,s\in\mathbb{Q}_+$. Denote $ab-s$ by $\Delta$. Let $A$ be a positive number. What are the values of $A$ such that for any $(a,b,s)$ with $\Delta\...
- 1,982
2
votes
1
answer
69
views
Clarification on FPTAS optimization in a paper
In the abstract of this paper by Hildebrand, Weismantel & Zemmer it is stated that they provide an FPTAS for $$\min x'Qx$$ over a fixed dimension polyhedron when $Q$ has at most one negative or ...
- 13.9k
2
votes
1
answer
202
views
Feasibility of constrained multivariable diophantine equations
Let $d$ be day, $m$ be month and $y$ be year fields of a date. I want to find few dates of format
$$(d^2\, mod\,\, 2 + (my + d^3) \,mod \,4) = 2$$
Is there a method to solve this type of equation or ...
- 131
2
votes
1
answer
107
views
Does this simple non-convex problem involving discrete phase shifts have an exact solution?
Let the optimization problem be
\begin{equation}
\max_{\phi_n} \left|\sum_{n=1}^N e^{i\phi_n} a_n \right|,
\end{equation}
where $a_n\in\mathbb{C}$ and the optimization variables have discrete phase ...
- 345
3
votes
0
answers
148
views
The complexity of an optimization problem involving sum of binomial coefficients
I'm just new to this community. So please forgive me if the question is not properly asked.
I would like to get the natural number e such that the following function can be minimized:
$f(e)=\frac{b}{...
- 31
0
votes
0
answers
181
views
Mixed-Integer Bilinear Program (MIBLP)
Consider the problem of
\begin{align}
\min_{x,y} \quad &a^Tx + b^Ty + x^TQy \\
&Ax \leq d \\
&Cy \leq e \\
&x_i \in \mathbb{R} \quad i \in \{1,2,\ldots,N\} \\
&y_i \in {\{0,1\}} \...
- 113
3
votes
2
answers
1k
views
SDP relaxation vs LP relaxation
I have a question I hope you might be able to answer.
Let's say we have an integer program for the stable set problem (or clique, not principal).
\begin{equation}
\begin{aligned}
& \text{...
- 342
0
votes
2
answers
708
views
Approximate solution to large mixed integer programming problem
What are the available approaches to find an approximate solution to a large mixed integer programming problem?
I ran my problem in the Gurobi MIP solver.
It can find a feasible solution in ...
user24451
1
vote
0
answers
1k
views
Subtour Elimination in Travelling Salesman Problem using MTZ
I am trying to formulation a problem similar to a Traveling Salesman with Time Window constraints.
To eliminate subtours, I need to use some constraint similar to a generalization of MTZ constraints ...
- 11