Qurious Cube
  • Member for 7 months
  • Last seen more than a month ago
Numbering the vertices of an $n$-layer graph so that edges have similar numbered vertices on their ends
Accepted answer
3 votes

Maybe this can work? Numbering is same as sorting. Disregard the layers and treat the whole thing as a single graph. Use Cuthill-Mckee (if the bandwidth is low) or other heuristics for the graph ...

View answer
Why are the bounds 3 and 6 instead of 7, in this binary expansion of a slack variable in this QUBO problem?
Accepted answer
3 votes

According to the equality constraint (the equal to 4 one), at least two of the $x_{?}$ are 1. Therefore, the slack for the 1st constraint is at most 3. According to the equality constraint, the worst ...

View answer
Numbering the vertices of an $n$-layer graph so that edges have similar numbered vertices on their ends
2 votes

Treat nodes in 1st and 3nd layer as extra edges in the 2st layer to make a merged layer. Minimize bandwidth of 2nd layer. Repeat for the other layers. layer 2: o o o \ / \ / layer 1: @ ...

View answer
KKT conditions analysis for binary constraints
2 votes

Binary (Boolean) values are integer values. Therefore, optimization problems with boolean constraints are either integer programming or mixed integer programing (MIP). Generally, there is no easy ...

View answer
How to make the elements of the solution of gurobi belong to the elements of the specified list?
1 votes

Here is a small variation of RobPratt's answer. I will use two sets, as an example. Two sets of constants are given: $S_1 = \lbrace x_{1,1}, x_{1,2}, x_{1,3} \rbrace$ and $S_2 = \lbrace x_{2,1}, x_{2,...

View answer
Obtaining solver timings from Pyomo
1 votes

For timing within the gurobi solver, maybe you can call <optimizer>.solve() method with report_timing=True, as described in pyomo's documentation at https://pyomo.readthedocs.io/en/stable/...

View answer
Linear Relaxation of Boolean Constraint for Solving Integer Linear Program Using KKT
1 votes

Minimize $x^2$ where $1 \le x \le 2$. \begin{aligned} \min_{x} \quad & f(x)\\ \textrm{s.t.} \quad & h_{1}(x) \le 0\\ &h_{2}(x) \le 0 \\ \end{aligned} where \begin{align} f(x) &= x^...

View answer
How to make following constraint a convex one?
0 votes

Transform the optimizing variables $x$ and $y$ in everything (the whole model) to $u = \frac{ax}{\ln(b + cy)}$ and $v = x$ Transformed constraint $u + dv \le A$ is linear. Therefore, the transformed ...

View answer