Unanswered Questions
42 questions with no upvoted or accepted answers
9
votes
0
answers
230
views
Solving large-scale stochastic mixed integer program
What are some methods or algorithms for solving a large-scale stochastic mixed-integer optimization problem that runs on an hourly dataset for a year? Do we employ some kind of decomposition? (the ...
- 1,687
9
votes
0
answers
182
views
Modelling resource dependency in the assignment problem
The assignment problem is well-studied and has a nice polynomial time algorithm. I'm interested in an extension of this problem where all edges are in a certain group and taking multiple edges from ...
CommunityBot
- 1
6
votes
2
answers
171
views
Complexity of the ellipsoid method in general convex problems
The ellipsoid method is often mentioned in relation to the complexity of solving linear programs.
Is the method however polynomial in the general non-linear convex cases? Preferably I would like a ...
CommunityBot
- 1
6
votes
0
answers
226
views
Airline revenue management re-solving problem
I am considering a bid prices (shadow price of the capacity constraint) problem (from Chen, L. and Homem-de Mello, T. (2009)., page 14) where the acceptable classes for booking requests for ...
- 165
6
votes
0
answers
95
views
Sample Average Approximation vs. Numerical Integration
In the sense of the calculation of the expected value of objective functions, we have two choices to evaluate the value; 1. Sample Average Approximation (SAA):
$$
\frac{1}{N}\sum_{i=1}^N f(x,\xi^i).
$$...
- 155
5
votes
0
answers
124
views
Scale of largest CPLEX/Gurobi execution
I am trying to understand the CO2 emission of large scale optimization using CPLEX or Gurobi. Is there a published literature which addresses the compute usage of large scale executions?
- 1,895
5
votes
0
answers
113
views
How many clues make Sudoku polynomial
Consider a $n^2 \times n^2$ grid sudoku.
Define a clue to be composed of a coordinate $x$ and $y$ of the grid and a value $z$.
The goal is given $n$ and a set of clues, to find one solution to the ...
- 303
5
votes
0
answers
154
views
Chance constrained optimization - interpretation
Suppose that we have a stochastic vector $\psi$ and $S$ realisations of $\psi$ given by $\psi_1,\dots,\psi_S$ with equal probability of occurrence. In addition, we have constraints of the form
\begin{...
- 2,463
5
votes
0
answers
63
views
Complexity of solving a certain commodity flow problem
Does anyone know the complexity of obtaining the optimal solution to the integral multi-commodity network flow problem with unit demands, integral capacities, but the cost of using an arc varies ...
- 1,583
5
votes
0
answers
116
views
Complexity of determining whether a LP or MIP is infeasible
What is the best complexity for the worst case scenario and the algorithm associated with it to determine if a linear programming (LP) is infeasible ? Further, what if we consider a mixed integer ...
- 51
5
votes
0
answers
124
views
Maximum eigenvalue across subsamples
I have an $N$-dimensional vector of data, say $X_{t}$, with $1 \leq t \leq T$.
Of this vector $X_{t}$, I want to consider sub-vectors, say $X_{t}^{b}$, which are $m$-dimensional combinations of ...
- 1,895
4
votes
0
answers
164
views
Stochastic optimization for inventory management
The deterministic problem is to minimize operational cost subject to constraints in demand, supply and capacity. The ordering policy is periodic review, order-up-to.
The stochastic version of the ...
- 1,895
4
votes
0
answers
54
views
How to find range of values for the first-stage decisions resulting in the same cuts in two-stage stochastic programming?
Suppose we have a two-stage stochastic program as follows:
\begin{equation}
\begin{split}
\min \ & c^Tx + \mathbb{E}_\xi[Q(x,\xi)] \\
& \text{where}\\
&Q(x,\xi)=\min q(\xi)^Ty\\
&Tx+...
- 2,160
3
votes
0
answers
50
views
Control variables and cofounding effects in stochastic programming/,model predictive control/reinforcement learning
How can we be sure that confounding variables/control variables don’t pickup the effect our decisions w.r.t decision variables had on the actual control variable?
Since the term control variable ...
3
votes
0
answers
111
views
Polynomial Time Solution For a Mixed-Integer Linear Programming Specific Case
Consider the following mixed-integer linear programming (MILP):
\begin{equation*}
\begin{array}{ll@{}ll}
\text{maximize} & 1 & \\
\text{subject to}& x_{i} \geq 0, &i=1 ,\dots, m\\
...
- 1,015