Most Popular
1500 questions
6
votes
1 answer
Interpretation of Reduced Costs
I am looking for an answer to a question I can't quite get behind. (continuation of Linear Programming: Integer and non-integer decision variables)
I am given the following mathematical optimization problem:
\begin{align}\min&\quad\sum_{t\in…
coar
- 133
- 1
- 6
6
votes
1 answer
Linear Programming: Integer and non-integer decision variables
I am looking for an answer to a question I can't quite get behind.
I am given the following mathematical optimization problem: \begin{align}\min&\quad\sum_{t\in T}s_t\cdot z_t+h_t\cdot i_t+p_t\cdot q_t\tag1\\\text{s.t.}&\quad i_0=0\tag2\\&\quad…
coar
- 133
- 1
- 6
6
votes
3 answers
Budgeted max cut heuristic
I am looking for a heuristic that solves a budgeted variant of the max cut problem.
Given a graph $G = (V, E)$, if the original problem is to find a partition of $V$ into two subsets $A$ and $B$ where $A \cap B = \emptyset$ such that the size of the…
David
- 333
- 1
- 7
6
votes
1 answer
Minimizing a project costs through nonlinear optimization
I have a project and I want to minimize the costs. I am are responsible for the inspection of 1000 miles of sewer grid in Canada. My goal is to provide time high quality inspection reports. I tried to define the problem using optimization but I…
Revolucion for Monica
- 161
- 3
6
votes
2 answers
Does a modeling language that generates SAT instances exist?
Nowadays, we enjoy the expressivity of modern modeling languages. However, does it exists a modeling language that takes in input a declarative problem definition (like AMPL or MiniZinc, or similar), and produces as output a SAT instance, for…
Stefano Gualandi
- 1,750
- 1
- 13
- 26
6
votes
1 answer
Naturally branch-and-cuttable problems with high didactic value
I am willing to bet that the problem most often used to teach students about branch-and-cut is the Travelling Salesman Problem (TSP).
It has a number of nice characteristics which make it appropriate for this task:
The problem itself is easy to…
Alberto Santini
- 2,113
- 9
- 23
6
votes
1 answer
How can I solve a linear optimization problem with bounds that are a function of the decision
I am using the rDEA package's linear optimization function multi_glpk_solve_LP(which is built on top of the Rglpk package's linear optimization function Rglpk_solve_LP) to optimise the following problem:
## minimize: 20 x_1 + 34 x_2 + 22 x_3 + 27…
user9396820
- 63
- 4
6
votes
3 answers
Traveling Salesman Problem: How to avoid symmetry?
I solved a Traveling Salesman Problem (TSP) by the cutting plane method, i.e. adding violated sub-tour constraints until the LP relaxation is a tour. Now, I am realizing that, in this symmetric TSP, driving route $1 \to 2 \to 3 \to 4$ is identical…
LamBadaMan
- 63
- 5
6
votes
1 answer
Gurobi searches all nodes despite variable initialization
We are trying to solve a large-scale MIQCQP (18K decision variables) problem via Gurobipy (v9.0.3).
Gurobi is able to solve this problem in ~13 mins despite whether or not we initialize the decision variables. Ideally, we are expecting drastic…
pqrz
- 470
- 2
- 7
6
votes
1 answer
How to cope with the rigidity of solutions?
Consider the following problem of Technician Routing and Scheduling Problem.
We have:
A set of customers where each customer needs the intervention of a technician to do some job. Each customer has a time-window of presence and a geographical…
BloodyOrange
- 309
- 1
- 4
6
votes
1 answer
Dual of a model to obtain reduced costs
I have the following model which I am going to solve with column generation.
\begin{align}
\max & \sum_{b \in B} \sum_{s \in S} \sum_{r \in \Omega_s}\beta_{bs}p_r y_{br}\label{objective-set1}\\
\text{s.t.}
& \sum_{b \in B} \sum_{s \in S}…
pozyavas
- 61
- 4
6
votes
1 answer
In which time complexity operates the Savings algorithm for the TSP?
In which time complexity operates the Savings algorithm from Clarke and Wright for the TSP? I mean the parallel version of Savings. I think it is in $\mathcal O(|V|\log|V|)$ with V as vertex/node because the most complex operation is sorting the…
maxmitz
- 659
- 3
- 11
6
votes
2 answers
How to model this expression?
Suppose $0\le x \le 1$ is a decision variable and $\gamma(x)$ is defined as follows:
$$
\gamma(x)= \begin{cases}
\theta & x>0\\
0 & x=0
\end{cases}
$$
where $0\le \theta\le 1$.
In my model, I have both $\gamma(x)$ and $x \gamma(x)$ and I want to…
Amin
- 2,150
- 7
- 20
6
votes
0 answers
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).
$$
2. Numerical Integration (e.g., Monte Carlo…
Keith
- 155
- 4
6
votes
1 answer
Do you know of any formula to calculate the difficulty score of Sudoku?
I am looking for a formula to measure the difficulty level of a Sudoku solution.
Optimization team
- 1,326
- 1
- 6
- 20