Most Popular
1500 questions
5
votes
1 answer
How does OR-Tools improve on an initial solution to CVRP?
I have an initial solution to a CVRP instance which I am setting as input to the solver. The solver as expected returns an improved solution. I have a few questions regarding the solver.
How does the solver improve upon the solution when I am not…
Alphanerd
- 91
- 5
5
votes
2 answers
Lin-Kernighan TSP edge choice
Step 4a of the original paper describing the Lin-Kernighan TSP algorithm states that the choice of edge $x_i = (t_{2i}, t_{2i+1})$ to be deleted is uniquely determined by the choice of edge $y_{i-1} = (t_{2i-1}, t_{2i})$ previously added.
Helsgaun…
llilibbou
- 61
- 4
5
votes
2 answers
The variable splitting scheme in the context of Lagrangian relaxation
I am interested to know solving the generalized assignment problem (GAP) using the variable splitting scheme, specifically, in the context of Lagrangian relaxation. The problem is stated as follows: (named GAP2)
\begin{align}
\text { Minimize Z = }…
A.Omidi
- 8,832
- 2
- 13
- 49
5
votes
3 answers
how to "calm down" optimizer
I want to optimize a charging schedule for Battery Electric Vehicles (BEV) along a grid line, taking into account customer wishes (when to be done with charging with what State of Charge (SOC)) and other loads like households. So the goal is to load…
Andre
- 303
- 1
- 5
5
votes
0 answers
What kind of packing problem is this?
I have the following problem which seems related to the packing problem. I have a grid of same size rectangles and a polygon on which this grid of rectangles needs to be placed such that the number of rectangles completely withing the polygon…
Av0
- 51
- 2
5
votes
1 answer
Linearizing this absolute difference objective function $\min\sum_{i=1}^{I}\sum_{j=1}^{i}|x_i-x_j|$
For $x_i>0, i=1,\ldots,I$, I tried to linearize this objective function
$$\min\sum_{i=1}^{I}\sum_{j=1}^{i}|x_i-x_j|$$
as
$$\min\sum_{i=1}^{I}\sum_{j=1}^{i}y_{ij}$$
subject to
\begin{align}
& y_{ij} \le x_i-x_j \quad i=1,\ldots,I, j =1,\ldots,i\\
&…
user9659
5
votes
2 answers
Knapsack - How to optimize bonuses for each pair of items
I am trying to solve a variation of the knapsack problem where every pair of items in my knapsack has a bonus or penalty associated with it.
My knapsack can hold a dozen items
There are thousands of items to choose from
Every pair of items has a…
Eddie
- 197
- 4
5
votes
1 answer
Tightening constraints for better formulation
Lately, I have been reading a lot of papers where the constraints have been tightened to include better formulations leading to decrease in optimiality gaps and also the time for solving the optimisation problem. I was wondering if there is a book…
Ishaan
- 139
- 6
5
votes
1 answer
Dynamic program for knapsack in $O(W)$ space?
A familiar dynamic programming algorithm for the binary knapsack problem
$$
\begin{align}
\text{maximize}\quad & v \cdot x \\
\text{subject to} \quad & w \cdot x \leq W \\
\quad&x_i \text{ binary}
\end{align}
$$
is as follows: Let $m[i, w]$ denote…
Max
- 544
- 2
- 8
5
votes
1 answer
How to model a max-min-max problem?
Everyone knows how to model max-min or min-max problems. I have a problem with objective to maximize min-max. So it can be called as a max-min-max problem. Any ideas how to model it efficiently?
The objective function looks like:…
Joseph
- 61
- 3
5
votes
0 answers
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 sudoku problem.
Let $R$ be the number of clues of…
Samuel Bismuth
- 173
- 7
5
votes
1 answer
Binary variable to indicate zero probabilities
I have a finite probability distribution $p_1, p_2, \ldots, p_n$ (but these are variables of an optimization problem). Moreover, we have monotonicity, $p_1 \geq p_2 \geq \cdots \geq p_n$.
Assume we already constrained that at least one of the $p_i$…
independentvariable
- 3,980
- 10
- 36
5
votes
1 answer
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 reference to a work stating the complexity of the…
gmn
- 666
- 4
- 10
5
votes
1 answer
Writing a specific MILP problem
I would like to choose a set of $\beta_j$s that maximizes a simple linear objective function of the type
$$
\underset{\beta_j}{\operatorname{max}}\sum_{j=1}^{J}X_j\beta_j \\
$$
subject to the following…
FightMilk
- 215
- 1
- 5
5
votes
1 answer
Constraints like "max(column a + column b) == 2" are not DCP
I am struggling with the following constraint on a minimization problem
cvx.max(z[:, i] + z[:, j]) == 2
where z is a Boolean matrix decision variable. I need to ensure that at least one row in z has a $1$ in two given columns (i and j). CVXPY…
Brannon
- 900
- 2
- 12