New answers tagged

3

[I'm leaving out constraint 0] I see two levels of decisions in your problem: Group servers into clusters Assign each user to one of these clusters (BTW, this way of seeing the problem is heavily inspired by Facility location problems). The second step is actually the easiest: once the clusters are known, you can just compute each user's gain w.r.t to each ...


2

Integrating a piecewise linear function means you end up with a piecewise quadratic function. Unless there is come convex structure in the resulting piecewise quadratic function (i.e. the PWL is non-decreasing) you will end up with a model involving nonconvexities. It was an interesting question so I had to play around a bit with it, and wrote a small post ...


2

I'm not familiar with what GUROBI does exactly, but continuous non-convex QCPs are solved using continuous branch-and-bound. This involves generating a linear relaxation of the problem which is solved at every node of the BnB tree, along with local optimisation of QCPs to get primal solutions (until we hit the global optimum). The linear relaxations would ...


3

First of all, you should determine the sign of the multipliers based on the objective function direction and how the complicating constraints are violated. Then you have to use a standard method like subgradient optimization to solve the lagrangian dualized problem to determine the optimal value of the multipliers. For more details: Marshall L. Fisher, An ...


3

With my best understanding (mostly from the practice of MISO), the goal of Day-ahead SCUC is to provide commitment decisions for the next day while the commitment decisions will also guarantee there are enough "average" power/energy with sufficient ramping for each of the considered discretized time-window. (See [1] for the manual reference) In ...


4

Rank-one constraints are unfortunately not mixed-integer convex representable, as shown in this paper: https://arxiv.org/abs/1706.05135, although they are quadratically-constrained quadratic representable. If the problem size is not too large, you can try solving it using Gurobi, either directly (for n<=10) or via branch-and-cut (for say n<=50; see ...


2

This is because SCUC provided on/off + dispatch Sometimes when you are at time t the demand is not the same as the predicted value and you need to adjust the P values (not on/off since they can't be changed) then you will run a SCED to make sure everything is fine


2

Maxcut with CPLEX CPOptimizer in https://github.com/AlexFleischerParis/howtowithopl/blob/master/maxcutcpo.mod using CP; execute { // time limit 10 s cp.param.timelimit=10; } int n=400; range r=1..n; // Random graph float edge_prob=0.5; int weight_range=10; int big=100000; tuple t { int i; int j; } {t} s={<i,j> | ordered i,j in r}; int ...


5

Shameless plug: I recently gave a webinar on diagnosing infeasibility. Here's what your example looks like in SAS: proc optmodel; var A >= 0; var B >= 0; max z = 20*A + 30*B; con c1: A <= 60; con c2: B <= 50; con c3: A+2*B >= 220; solve with lp / iis=true; expand / iis; quit; The resulting IIS contains all three ...


3

Have a look at MQLib, which contains efficient implementations of many published algorithms. Their paper is awesome too. You can find a lot of code for QUBO online, one of the most publicized being qbsolv from Dwave. It is meant as a demonstrator of how much better quantum algorithms are, and the method is very basic. In general, I would take any hype on ...


3

You are not going to be able to add these logs and quadratic terms to the model via simple double-sided big-M constraints, as they generate non-convex use of convex quadratics and logs, and CVX does not support that. The use of the squared log is not possible either. I don't think it supports automatic modelling of nonconvex use of abs operator either. Most ...


8

I think one of the reasons you have difficulties implementing the constraint is because it is not written correctly. You need to be more precise with your indexes. If $N:=\{1,...,n \}$, you can write the constraint as follows: $$ \sum_{i \in S}\sum_{j \in S, j\neq i} x_{ij} \le |S| -1 \quad \forall S \subset N, 2 \le |S| \le n-1 $$ This means that you have ...


1

Since you are open to a heuristic, I wonder if a restricted decision diagram (DD) might work for you. Decision diagrams are similar to dynamic programs in the sense that each node represents a state of the system and each arc represents a decision that results in a new state that is dependent only on the decision and the state at which it is made. The least ...


4

Although focused on implementing the model in YALMIP instead of CVX (converting the code should be trivial), precisely this case is described in the following tutorial https://yalmip.github.io/modellingif You basically introduce a binary variable $\delta_i$ for each region, and then add the implications that $\delta_i \rightarrow \{\text{cost} = f_i(x), x \...


2

If the constants are such that the cost function is convex (e.g., $b=0$, $c=-25$, $d=-1775$), you could minimize a variable $z$ subject to \begin{align} z &\ge 10p + b \\ z &\ge 15p+c \\ z &\ge 20p^2 -10p +d \\ z &\ge 0 \end{align} With the above values, the cost function is the maximum of the curves in the figure below: EDIT: With the ...


2

It sounds like you want to pack $N$ rectangles with given dimensions $w_i \times h_i$ in a $W \times H$ rectangle, as discussed here. To allow each rectangle to be rotated 90 degrees (with dimensions $h_i \times w_i$), you can introduce a binary variable $r_i$ to indicate whether to rotate rectangle $i$ or not. Then modify the constraints like this: \begin{...


1

since you deal with a scheduling problem I encourage you to have a look at CPOptimizer scheduling within CPLEX. See also https://stackoverflow.com/questions/49405659/mip-vs-cp-for-scheduling-problems


5

I actually have quite a few points. As usual, things are not as clear cut. I use advanced bases for LPs very often and they are surprisingly effective and tolerant of quite a few changes in the model. For large problems, often a good strategy is to use the barrier method for the first problem (solved from scratch) and the simplex for subsequent related ...


1

Warm starting is used predominantly when solving problems that are only slightly different, and typically when only some coefficients have changed. The idea is that many of the feasible polyhedrons' vertices are shared between the two problems, therefore starting at a vertex that was good at a previous problem will save us pivot operations. If the problems ...


5

Your constraint matrix is changing with each new problem, so it might not be easy to warm-start ... and it might not be worthwhile, even if you could. One nice thing (among several) about transportation problems is that the origin is feasible, meaning the simplex method has an obvious starting basis. Warm-starting would require you to massage the previous ...


1

I don't think weeding "outliers" will get you to a fair comparison, given that some stores have larger sales than others. A somewhat crude alternative is to compute two average sales per period figures for every store, one for a time period before the marketing campaign and the other for the time period containing the marketing campaign. Then ...


5

You want to enforce $$x_I=\max(x_P-C,0).$$ See https://math.stackexchange.com/a/4086955/683666, where the various big-M values are specified explicitly. More generally, see Linearizing a Max Function in the constraint - not working to linearize the max of $n$ linear functions.


6

You are maximizing a convex quadratic (the monotonic log is irrelevant) so the maximum is attained at the border, i.e. either $0$ or $\min(1,\sqrt{1-\text{constant}})$.


4

You can model it by adding a binary variable $b$ and the following four constraints. $$ \begin{align} x_I &\geq x_P - C & x_I &\geq 0\\ x_I &\leq x_P - C + Mb & x_I &\leq M(1-b) \end{align} $$ where $M$ is a big constant. Note that if $x_P > C$, $b$ can't be $1$ as otherwise $0\geq x_I > 0$, which would lead to infeasibility. ...


3

Assuming $x_p$ is a continuous variable, you could use the following big-M inequalities: \begin{align} C - M_2(1- y) &\le x_p \le C-1 + M_1 y \\ x_p - C - M_4(1-y) &\le x_I \le x_p - C + M_3(1-y) \\ 0 & \le x_I \le M_5y \\ y &\in \{0,1\} \end{align} So if $y=0$, $x_P \le C-1$, or by contrapositive, if $x_P \ge C$, $y=1$. And if $y=1$, then $...


1

For the problem you describe, since the function is strongly convex and $x,y \in \mathbb{R}$ (so you don't have bound constraints), your solution is obtained by solving the system $\nabla f = 0$. Now, if you only have approximations to the gradient, the resulting error largely depends on the algorithm you chose to use to solve this. For instance, since your ...


5

Yes, because $\log$ is monotonic, it preserves inequalities. The tightness depends on your other constraints.


Top 50 recent answers are included