New answers tagged

3

The transformation you want is called node splitting. Replace node $i$ with two nodes $i'$ and $i''$, where all incoming arcs to node $i$ instead arrive at node $i'$ and all outgoing arcs from node $i$ instead leave node $i''$. Also introduce a directed arc from $i'$ to $i''$ with capacity $1$.


5

Your intuition that you need to adjust $b_i$ is correct, but you also need to adjust $u_{i,j}$. To derive the desired MCF, perform a change of variables $y_{i,j}=x_{i,j}-\ell_{i,j}$ (so that the lower bound constraints become $y_{i,j} \ge 0$). That is, replace $x_{i,j}$ with $y_{i,j}+\ell_{i,j}$ throughout your constraints, and rewrite into the form of MCF....


1

for (int m = 0; m < 12; m++) { constra = new GRBLinExpr(); constra.addTerm(150, x_m[m]); constra.addTerm(0.000001, x_m[m]); constra.addConstant(-0.000001); constrb = new GRBLinExpr(); constrb.addTerm(100; x0_m[m]); constrb.addTerm(-100); }


4

Optimality implies that a proof was constructed that proves there does not exist a better solution than the best feasible solution found. A brute force search does indeed give you a (rather long) proof. However, in many settings you can find shorter proofs than enumerating all possible cases. For example, when finding a shortest-path in a fully connected ...


1

In addition to what @Richard mentioned: You can consider $a=0$ and $b=\epsilon$ in @Richard's answer. Here you can find how special functions in the constraint can be modeled using Gurobi. Yours is defining an indicator variable for $S_m$ to find out whether the value of your variable is positive or negative. Edit: you can model it as follow: $$S_m \leq ...


1

The easiest would probably be to model it as follows: $$ S_m \leq a + bx_m \\ S_m \geq ax_m $$ where $a$ is the switch and $a+b$ is the upper bound for variable $S_m$. In this case, if $S_m< a$, then $x_m$ has to be 0 (otherwise this is infeasible). Similarly, if $S_m > a$, then $x_m$ has to be 1. The key question here is what you want to happen if $...


2

This depends on your definition of "optimal". Generally speaking, a solution is optimal iff it satisfies the KKT conditions for optimality. In that sense, finding a KKT point is relatively simple, and proving that a given point satisfies (or not) KKT is as trivial as evaluating a system of equations. If the problem is mixed-integer, the concept of ...


9

I am having a hard time to believe that the solver actually tries all solutions Indeed, they typically do not explore the whole search space (though it's possible to build problematic instances where they would). MILP solvers will use a combination of tools to do so, under the umbrella of the branch-and-cut paradigm (B&C is basically branch-and-bound ...


1

Your problem description is quiet vague. So i picked the simplest solution to his problem i can think off in modeling language JuMP. If you are more detailed about the reality you are working with a better model can be chosen. clients = 24 servers = 3 using JuMP using GLPK class = Model(with_optimizer(GLPK.Optimizer)) cost = rand(clients, servers) # cost ...


3

Using Calculus of Variations as an inspiration we have the lagrangian $$ \mathcal{L}(f,\lambda) = \int_0^{x_{max}}\left(-\ln\left(\alpha(x)+f(x)\right)+\lambda\left(f(x)-\frac{1}{x_{max}}\right)\right)dx\ \ \ \text{s. t.}\ \ \ f(x)\ge 0 $$ The variation regarding $f$ gives $$ -\frac{1}{\alpha(x)+f(x)}+\lambda = 0\Rightarrow f(x) = \frac{1}{\lambda}-\alpha(x)...


2

I can't tell if your path is right (because it depends on that you want to do), but it is sensible. Your problem structure is quite similar to one occurring in the field of optimal control. I'm not aware of any closed form solution of your approach, so you will have to pick a numerical approach to get started. As you are probably aware, you can't express ...


5

According to the docs, IloNumArrays constructor signature is public IloNumArray(const IloEnv env, IloInt n, IloNum f0, IloNum f1, ...) which creates an array of n floating point objects for use in a model. Note that the constructor is a C-Style variadic function due to the ... parameter. Thus, you can assign your values while calling the constructor, i.e. ...


5

Introduce a supersource node $s$, a supersink node $t$, arcs from $s$ to each source, and arcs from each sink to $t$. Arc $(s,i)$ has zero cost and capacity equal to supply[i]. Arc $(i,t)$ has zero cost and capacity equal to -supply[i]. All original nodes have supply zero, $s$ has supply equal to the sum of positive supplies, and $t$ has supply equal to ...


1

To add to @prubin's answer (which is the correct answer) if you somehow need to choose between the two obtions, my advice would be to add the constraints (or better, change the bounds on the variables). Obviously, a good solver will immediately identify the variables with a negativ profit and set their value to zero, but a bad/homebrew solver might not. Thus,...


5

Neither. You should delete $d_{u,c}$ from the model whenever $\omega_{u,c} < t_\min$.


4

Both might provide useful approximations, but minimizing the underestimator $Y$ is a relaxation in the sense that an optimal solution yields a lower bound on the minimum $X$. Bill Cook and his team exploit this idea to solve large TSPs when the edge costs are road distances. The number of pairs is too large to query Google for all of them, so geodetic ...


3

Your problem has continuous variables (the number of bananas delivered each day) but a discrete objective function (the number of deliveries over the period). As you noticed, counting the number of deliveries by using the expression "sum(transported_bananas > 0)" makes the objective function discontinuous. SLSQP (Least Square Sequential ...


4

From the comments I found that your problem can be described by a setup time $s_j$ for process $j$ a travel time $c_{ij}$ for worker $i$ to process $j$ Then the waiting time that we get when assigning worker $i$ to process $j$ is given by $w_{ij}:=|s_j-c_{ij}|$. Using $w_{ij}$ as your new weights of the assignments you can use any classic assignement ...


1

Many people seem to think that, but we do nothing of the sort in OR - our process is much simpler than people think. We build and solve a model, and if the results make sense, we are pretty much done. If the results don't make sense we typically know why. Crucially, we can know whether the issue is in the data or not. The reason OR has a reputation for being ...


4

As Sune noted, the $\epsilon$-constraint method is not comparable to what CPLEX does, since it finds all Pareto efficient solutions. In case you were thinking of option 2 as finding a lexicographic optimum by optimizing the highest priority objective, constraining it to be optimal, optimizing the next highest priority objective etc. (similar to but not the ...


5

The augmented $\varepsilon$-constraint method is designed to generate all non-dominated outcome vectors to a bi-objective (or multi objective) optimization problem, whereas a lexicographic optimization approach is designed to generate one particular non-dominated outcome vector to bi-objective (or multiobjective) problem. So it all depends on what you want ...


9

You can add an extra binary that equals $1$ if and only if the first constraint is satisfied: \begin{align} x_1+x_2+x_3 &\ge \delta\\ x_1+x_2+x_3 &\le 3\delta\\ x_4+x_5+x_6 &\ge 1 - \delta\\ x_4+x_5+x_6 &\le 3(1 - \delta)\\ \delta &\in \{0,1\} \end{align} If $\delta=1$, the first two constraints become: $$ 1 \le x_1+x_2+x_3 \le 3 $$ And ...


Top 50 recent answers are included