Questions tagged [optimization]

For questions involving mathematical problems that aim to minimize or maximize some objective function, possibly subject to one or more constraints.

Filter by
Sorted by
Tagged with
1
vote
0answers
33 views

0-1 knapsack with non-linear objective function

There's efficient algorithms for solving the 0-1 knapsack problems when the objective function is just a sum of profits. I am dealing with the following problem with non-linear objective function: $$\...
1
vote
1answer
30 views

Parallel scheduling with precedence constraints and variable job length

I have $N$ jobs and $M$ machines and want to minimize the makespan, i.e. the total time to finish all jobs. Some jobs have precedence constraints and can only be started once other jobs are finished. ...
1
vote
0answers
11 views

Question about theorems of the form “Any limit point of the sequence is a minimum of the problem”

In Optimization, we have problems of the form \begin{align*} &\min f(x)\\ &\text{s.t. }\hspace{0.2cm} x \in S \end{align*} and many theorems are of the form "If the problem satisfies ...
1
vote
3answers
296 views

Find the farthest point in hypercube to an exterior point

Let $\mathcal{U} = \{ [x_1, ..., x_n] \in \mathbb{R}^n : 0 \leq x_i \leq 1\}$ be the unit hypercube and $C \in \mathbb{R}^n\setminus\mathcal{U}$ fixed. Let us consider the following problem $$ \max_{X ...
0
votes
0answers
60 views

Linearization of constraints with square root

I am trying to solve an optimization programming model involving a non-linear constraint with a square root. It follows (in a simplified form): $X_i\ge\sqrt{A_i/B_i}$ where $X_i,A_i,B_i$ are positive ...
2
votes
1answer
93 views

How can I perform discrete optimisation of a variable over a data set

This question relates directly to a dataset I've generated for Fantasy Premier League, but I'm also curious how I can apply this to a more general case. Data I have a list of premier league players, ...
-3
votes
0answers
42 views

If-else statement in cvx

I have a problem with if-else statement in cvx which causes error. I raised this issue in cvx forum and was highly recommended to ask for assistance in this community. Could you please help to fix it ...
3
votes
1answer
75 views

Bioinformatics / Genomics Optimization Problems?

I am a third year bioinformatics student and would like to apply my knowledge from an introductory course in Optimization Methods to some problems in the field of genomics or bioinformatics. Do you ...
1
vote
1answer
69 views

How to prove this convex-optimization problem?

I am struggling with the following optimization problems. Problem 1 \begin{align}\max_{\alpha, s_1, s_2}&\quad s_1 + s_2 - \gamma (s_1 (K_1 +c_1 + s_1) + s_2 (K_2+ c_2 + s_2) + 2\alpha K) +C\\\...
1
vote
1answer
597 views

How to describe the traveling salesman problem with an integer programming model?

I'm trying to describe the travelling salesman problem as an integer programming model. I'm interested in the asymmetric version of the problem. The problem can be summarized as finding the optimal ...
6
votes
0answers
74 views

Is the solution of a convex combination of the objective in simple problems a convex combination of the solutions of the same problems?

Let $\mathbf{A}=\left(a_{ij}\right)$ be a $n\times J$ matrix with $a_{ij}\geq 0$, $n>J$ and such that no row has all its entries equal to zero, and each column has at most one zero. Let also $\...
3
votes
1answer
78 views

What are the flow based formulations?

What are the flow-based formulations? For what optimization problems are they applied, and in which form? Which are the specificities of such a formulation? Also, the same question for the time staged ...
6
votes
2answers
393 views

How to model bicycle sharing scheme?

One of the problems I have recently considered is the problem of rebalancing bicycle stations for bike-sharing schemes all over the world. It is not a secret that the demand for bikes across the city ...
3
votes
0answers
24 views

R ompr MILPModel array multiplication?

In R, I regularly ompr::MILPModel for optimization. I adapt the below snippet to enable multiplication of a decision variable with two dimensions (e.g., x[i,j] ) ...
3
votes
1answer
53 views

What is the difference between min- cut formulation and (bi) partitioning formulation?

I have a min-cut formulation and a bi-partitioning problem. The two problems focus on finding the minimal cut value separating the two partitions? So what are really the differences between the ...
1
vote
0answers
24 views

MILP formualtion for Two-level minimum dominating set (MDS) problem?

I'm working on an optimization problem which is kind of finding the minimum dominating set (MDS) or the minimum vertex set (MVS) in an undirected graph. given the MILP formulation for both problems, I ...
2
votes
0answers
51 views

Reading MPS file for linear programming and reconstructing the Optimization model

Are you aware of any tutorial that can help me learn on how to reconstruct the objective function and constraints from a MPS file once it's loaded in MATLAB. I can load the mps file given to me and ...
4
votes
1answer
70 views

Is the order of edges in graph is changing the optimization result?

I am solving an optimization problem using Pulp and NetworkX. The problem is similar to the Minimum Vertex Set (MVS) problem. I have noticed that the optimizer is Scanning the edges according to their ...
0
votes
2answers
170 views

How can I formulate this specific if-then constraint?

IF $\sum\limits_d X_{i,d}\ge6$ THEN $Y_i = 1$ (strictly) AND IF $\sum\limits_d X_{i,d}<6$ THEN $Y_i = 0$ (strictly) $X$ and $Y$ are binary variables. What I'm actually trying to do is to charge the ...
5
votes
2answers
85 views

how to determine differents gap rate?

I found in the literature different gaps: a gap between a random solution and an exact solution a gap between the exact solution and a lower bound a gap between the exact solution and a lower bound a ...
3
votes
1answer
66 views

Sum of links neighbors in a graph

I'm trying to model this constraint in an optimization problem using Pulp and NetworkX. Here is a piece of code I'm using. ...
3
votes
2answers
110 views

Summation of all links that contains nieghbors to certain node in Graph

I'm trying to model a constraint in Python using Pulp and networkX that is getting the sum of the edges that contain this node over all the nodes. The constraint can be like that: $$\sum_{m\in\cal N}...
-4
votes
0answers
46 views

How to treat with equality constraints in whale optimization algorithm? [duplicate]

Whale optimization is one of the metaheuristic algorithms which used to find the optimal solution to unconstrained optimization problems. I have an objective function : $x_1+2 x_2−6 x_3≥0$, subject to ...
4
votes
2answers
101 views

How to deal with an optimization problem that have a sum of nonlinear functions of Z as a constraint when Z is the quantity to be minimized?

I have to minimize a quantity $Z$ subject to the following constraints: $$ w_1 + w_2 + w_3 = 1 \tag{1}$$ $$ \frac{f_1(w_1 Z) + f_2(w_2 Z) + f_3(w_3 Z)}{Z} \ge k \tag{2}$$ where $k$ is a known ...
2
votes
0answers
25 views

MDP model for a unique system

Let's assume that we have a system where there are two exogenous factors, name $a$ and $b$, that can affect the system state. At each decision epoch either $a$ or $b$ occurs and it is not possible ...
3
votes
3answers
177 views

How to handle an equality constraint in metaheuristic algorithms (like GA, PSO)?

Metaheuristic algorithms are generally used to find the optimal solution to unconstrained optimization problems. I would like to maximize $x_1+3x_2-x_3\ge0$ while respecting the equality constraint $...
2
votes
1answer
47 views

How to build a GAMS model in python

I looked at the GAMS python API but the documentation only describing already predefined models (run .gms with some tweaking options). My question is now: Can I somehow build a gams model from scratch ...
1
vote
0answers
92 views

How to develop a vehicle routing optimization package? [closed]

I would like to know how vehicle routing software optimizes routes? In demos of this software, they provide the optimal (or a good) route in just a few seconds or minutes with several nodes (maybe 50 ...
3
votes
0answers
46 views

Flexible Job Shop with Preemption

I'm trying to solve a flexible job shop problem variant that has precedence constraints on jobs along with a few other issues. We have a MIP formulation and also a simulated annealing algorithm to ...
4
votes
1answer
67 views

the set of optimal solutions of a linear programming (LP) problem as a mapping of right-hand side

Consider a linear programming (LP) problem \begin{align} M(b) \in \arg\min_x \{ c^\top x : Ax=b, x \ge 0 \}. \end{align} Suppose the LP is feasible and bounded for all values of $b$. We know that $M(...
0
votes
1answer
73 views

How can I find the shortest path for all nodes in a graph from a source $s$?

This is the shortest path problem. I've used a model where we can find the shortest path between the source and a specified destination. The idea behind this model is that we assign a flow of 1 for ...
2
votes
3answers
252 views

Why can quadratic functions over polyhedrons be minimized exactly in finite time?

I have heard it said that QP problems $$\min f(x) = \frac 12 x^TAx + b^T x$$ $$x \in P$$ where $A$ is a symmetric matrix and $P$ is a polyhedron can all be solved exactly and in finite time (or it can ...
5
votes
3answers
574 views

How to determine if this problem is NP-HARD or NP-COMPLETE?

Suppose that I have a pool with N nodes and I have to move the nodes one by one to another pool. For each move, consider a value on the edge linking the two pools. The goal is to find a order of nodes ...
2
votes
3answers
161 views

Are there any standard “tests” that determine if a model will not optimize / no solution?

As the title says, what are the tests for optimality or non-optimality I can build into my procedure and code to alert me that the model is going to be infeasible so I need to revise my constraints? ...
2
votes
2answers
110 views

Pyomo + Ipopt. Speed Issue

I am using Pyomo + Ipopt as solver to solve a NLP problem. The problem is not extremely complex in terms of dimensionality and ...
4
votes
1answer
126 views

How/when can we use MINLP engines instead of linearizing MP models?

Nowadays, mathematical programming solvers have been frequently used to solve lots of practical/academic problems. Many of these might be interpreted as a MIP or MINLP to represent a specific problem (...
3
votes
1answer
109 views

How do I interpret the CPLEX Optimization Studio MIP gap output?

I'm having difficulties understanding my FlowControl output compared to what the Engine Log shows me. My output from the FlowControl into the Scripting Log (yellow marks) is ...
1
vote
1answer
71 views

What kind of job shop scheduling problem is this and how do I solve it?

I have a production planning / scheduling problem, which I believe is a kind of job shop scheduling problem. But I would like to get some input on what kind of job shop scheduling problem it is and ...
5
votes
0answers
216 views

Substituting inequality by equality constraints

Let $\mathbf{A}=\left(a_{ij}\right)$ be a $n\times J$ matrix with $a_{ij}\geq 0$, $n>J$ and such that no row or column has all its entries equal to zero. Let also $\mathbf{k}=\left(k_j\right)$ be a ...
3
votes
3answers
622 views

Does adding constraint to an optimization model make it solve faster?

Some say adding constraints cuts the feasible region smaller hence the same solver terminates faster due to the less search effort. Others say it adds more complexity to the problem and it may take ...
5
votes
2answers
200 views

Can I use 'SCIP' solver for PYOMO?

I have an MINLP problem to solve where I was initially using 'ipopt' solver but the solution was not sticking to 'binary/boolean/integer' domain type for a variable. I am not sure which free solver ...
4
votes
1answer
54 views

How do you turn an abstract set constraint into equality constraints?

I am reading from Nonlinear Programming by Bertsekas, and in the section on ADMM, he says: Consider the problem $$\text{min} \sum _{i=1} ^ m f_i(x)$$ $$\text{s.t. }x \in \cap _{i = 1}^m X_i,$$ where $...
2
votes
1answer
295 views

Divisibility constraint in Integer programming

I have a simple question regarding the divisibility in integer programming suppose the objective function is $\text{max}\quad x_1 + x_2$ where the constraint is that the sum of $x_1$ and $x_2$ are ...
2
votes
1answer
75 views

confusing results of two models with different complexity

i have two models that address the same problem. the first one is : the second one is: for different instances for the same size (n=30) i found the following results ( the first column on the left ...
2
votes
1answer
55 views

MIP for assigning tasks with prerequisite tasks

I have a modified assignment problem for which I'm having difficulty formulating the constraints mathematically. I have a set of workers and a set of tasks which should be completed in the minimum ...
5
votes
1answer
210 views

How to determine the size of a model?

I want to know about the number of variables and constraints of this formulation (exp: $o(n)$ variables and constraints or $o(n^2)$ ....). Is the number of variables $\mathcal O(n^3)$ because we have ...
1
vote
1answer
33 views

Handy way to index set of tuples in AMPL

I am dealing with a discrete math optimization problem on a complete graph. My variables are the arcs but I want to delete the arcs that "cost too much". I have $n$ nodes which means I have $...
3
votes
1answer
72 views

Which method to use to solve this multi-objective conflicting objectives

I have the following multiobjective problem. I need to minimize the user-perceived latency while doing so aggressively minimizing user-perceived latency generates large switching cost (Reconfiguration ...
2
votes
0answers
95 views

How develop a branch and bound algorithm for integer programming with black box objective function?

The problem here described was taken from a university exercitation session. A serial production line is made of $K$ workstations: one kind product is manufactured by this line and has to be processed ...
3
votes
1answer
145 views

Issue in solving a large scale MIQP problem

I am solving a large scale MIQP optimisation problem at each step of a model predictive control problem. The problem description is as below. \begin{align} \min_{u} \quad (x_{k}&-x_\text{ref})^{T}...

1
2 3 4 5
8