Most Popular
1500 questions
11
votes
2 answers
Where can I find test instances for convex quadratic programming?
I am looking for (sources of) convex quadratic programming instances with linear constraints. I am open for both continuous and mixed integer problems, but do not want randomly generated instances.
I am aware of QPLIB, a collection of various…
Michael Feldmeier
- 2,856
- 14
- 40
11
votes
3 answers
Are Neural Networks Technically "Non-Linear Programs"?
If you look at the Loss Function for a Neural Network:
Can we consider the above problem as a "Non-Linear Optimization Problem"?
The way I see it, the Loss Function of real world Neural Networks usually contains higher order terms that likely…
stats_noob
- 1,831
- 7
- 30
11
votes
9 answers
Why is Discrete Optimization "Difficult'?
I have the following question about why Combinatorial and Discrete Optimization Problems are Considered to be "Difficult":
For continuous optimization problems (e.g. Loss Functions in Machine Learning Models) - we are often told that these…
stats_noob
- 1,831
- 7
- 30
11
votes
2 answers
Is deciding the presence of mixed-integer points in the relative interior of a polyhedron in NP?
Given $P = \{x\in\mathbb R^n: Ax \leq b\}$, I want to decide if $(\mathbb Z^\ell \times \mathbb R^{n-\ell}) \cap \operatorname{relint}(P)$ is non-empty.
Is this problem in NP?
One idea is to check if $P_\varepsilon \cap (\mathbb Z^\ell \times…
Sriram Sankaranarayanan
- 753
- 4
- 18
11
votes
2 answers
Can SOCPs approximate better than LPs?
Are there any classes of NP-hard combinatorial optimization problems where Second order cone programs (SOCP) gives a better approximation than linear programs (LP)?
I am looking for results in the flavor of Goemans and Williamson's celebrated…
Sriram Sankaranarayanan
- 753
- 4
- 18
11
votes
5 answers
A Stack Overflow user's curious problem of maximising unsortedness
User ddofborg posted on Stack Overflow a programming question which hides a combinatorial optimisation problem.
The idea is the following: given a list of URLs with their respective domain names, he wants to find the permutation which makes the…
Alberto Santini
- 2,113
- 9
- 23
11
votes
3 answers
Is my approach to my internship project good? Optimal allocation of product across stores, constrained optimization
Context: I am a CS student currently in a non-CS internship (logistics, supply chain).
My manager wants to leverage my knowledge of programming to build a program to solve the following problem:
As a company, we have different units of product that…
Marco
- 211
- 1
- 4
11
votes
1 answer
Heuristics for mixed integer linear and nonlinear programs
What are some primal heuristics that mixed-integer linear and nonlinear program solvers use to quickly obtain a reasonably good feasible solution?
Sriram Sankaranarayanan
- 753
- 4
- 18
11
votes
3 answers
From a performance/speed perspective, does the programming language matter if the solver used is the same?
Perhaps a silly question, I know... But just wondering if the programming language has an impact here if the solver used is the same? For instance, the same model formulation being solved using Gurobi in Python vs C++... Is the solver all that…
epilefst
- 159
- 5
11
votes
4 answers
What is the best open source solver for large scale LP optimization in pyomo?
I have used Gurobi and cplex for solving large scale LP problems with Pyomo. However, I do need to use open source solver. Any advise?
glpk and cbc seems to be very slow in solving the problem (with 2e6 variables)
Optimization team
- 1,326
- 1
- 6
- 20
11
votes
2 answers
partitioning hub assignment models
When solving large-scale hub assignment models (1000+ candidate hubs and 1000+ demand nodes), it is possible that parts of a cost matrix are not connected to one another.
A typical workflow would be:
Read in data
Create a graph (can be based on…
fhk
- 1,069
- 6
- 14
11
votes
1 answer
Efficient way to solve "easy" quadratic optimization problem
The linear program
\begin{align}
\min &\sum_{i=1}^nc_{i}x_{i}\\\
\mbox{s.t.:}&\sum_{i=1}^nx_{i}=1,\\\
&x_{i}\geq 0,&&\forall i=1,\dots,n
\end{align}
has a trivial optimal solution which is to simply: find an $i^*\in\arg\min_{i=1,...,n}\{c_{i}\}$…
Sune
- 6,457
- 2
- 17
- 31
11
votes
1 answer
Interplay of OR and Statistics Research
I saw some posts like this so I figured I would start my own.
What are some interesting papers in OR that are related to, or even develop, the theory of statistical inference? What are some of the applications that motivate these innovations? How…
Ariel
- 280
- 1
- 10
11
votes
2 answers
Linear Optimization Library for C++ with GPU Support
Does anyone know any linear optimization libraries for C++ supporting GPUs for parallelization? If multiple, which do you recommend?
The GPU support is important to me since I am dealing with large matrices in my problem constraints where the…
Daneshvar Amrollahi
- 113
- 7
11
votes
3 answers
Applicability of Lagrange Multipliers in the analysis of large-scale MILPs?
Qualitatively, in my experience in the solving of large scale MILPs, it is common that binary variables corresponding to "edge possibility" components are frequently chosen. Intuitively, these seem associated with various "critical values" within…
Mark H
- 550
- 3
- 11