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
2
votes
1answer
51 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
93 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
50 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 ...
2
votes
3answers
257 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 ...
2
votes
2answers
117 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
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
74 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
163 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? ...
7
votes
1answer
164 views

What are Operations Research applications for 'morally discussable causes'?

Out of curiosity, since I read this question What are Operations Research applications for 'good causes'? and thought it might be a good addition to it. What are Operations Research ...
4
votes
1answer
134 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
127 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 ...
3
votes
3answers
630 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 ...
1
vote
1answer
74 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 ...
18
votes
4answers
897 views

PhD-level textbooks on linear programming

My graduate Linear Programming class uses Bertsimas & Tsitsiklis's Introduction to Linear Optimization. Are there any alternative texts that I could use to supplement this textbook (mainly the ...
5
votes
2answers
273 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 ...
16
votes
3answers
675 views

What are some real-world applications of QUBO?

QUBO (Quadratic Unconstrained Binary Optimization) is the minimization of a quadratic function of binary variables. It has been used for computer vision, Ramsey numbers, factoring numbers, the ...
4
votes
1answer
60 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
298 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 ...
13
votes
3answers
206 views

Protein folding and protein design relation

I understand from this active COVID-19 question: Are there any COVID-19 (coronavirus) related optimization problems with input datasets that we can "crowd solve"? that the protein folding ...
15
votes
2answers
415 views

Are there any real-world problems where quadratization helps to solve something that couldn't have been solved without quadratization?

The closest thing I know is the computer vision problem, in which an image is de-blurred and/or de-noised by quadratizing a quartic problem into a quadratic optimization problem (QUBO) and then the ...
5
votes
1answer
211 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 ...
2
votes
1answer
58 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 ...
3
votes
1answer
77 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 ...
1
vote
1answer
36 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
148 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}...
2
votes
0answers
96 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 ...
4
votes
1answer
179 views

Trouble understanding a passage in Nonlinear Programming by Bertsekas

I am reading Nonlinear Programming by Bertsekas, and the chapter on duality starts like this: we define the primal problem as $$\begin{align*} &\min f(x)\\ &x \in X\\ &g(x) \le 0 \end{...
2
votes
0answers
35 views

How to set solver options in Pyomo with GAMS Python API?

Did anyone have experiences with Pyomo and GAMS as solver? I had looked into the pyomo documentation (GAMSShell Solver) and in the CPLEX Manuals, but doesnt find the correct syntax. My Code looks like:...
1
vote
0answers
33 views

Interger programming using gray encoding

Could anyone suggest me a tool or library which takes an integer programming problem written in DOCPLEX or CVXPY as input and outputs the equivalent problem using Gray binary encoding? I am happy to ...
2
votes
0answers
33 views

Optimization of strongly convex functions with approximate evaluations of gradient and Hessian

Suppose I want to find the minimum of a differentiable, strongly convex function $f:\mathbb{R}^n\to\mathbb{R}$ with constant $\mu>0$. That is, for all $x,y\in\mathbb{R}^n$, I have that: $$f(y) \geq ...
2
votes
1answer
80 views

Looking for a similar optimization problem

I want to know if there is any already defined problem that could give me a hint on how should I approach the following task. There are N tasks that should be accomplished, each task requires ...
0
votes
1answer
82 views

Does this objective function makes sense?

I am wondering if the objective function in the following problem makes sense. The question is posted in CrossValidated, stack exchange as well. I know there is a physical system having an underlying ...
12
votes
2answers
449 views

How to handle an IP sub-problem with an objective function in Benders Decomposition

I have a question on Benders Decomposition (BD). Suppose I have an MILP model which can be decomposed into a master problem (MP) including integer and continuous variables and a subproblem (SP) ...
2
votes
1answer
84 views

Specific usecase of two-phase simplex algorithm

The problem below aims to find to most optimal way to transport the fuel : A company Er must transport a type of fuel from its two refineries Ra and Rb to its two points of sale PV1 and PV2. The ...
2
votes
1answer
114 views

Is my formulation correct and how to formulate this IF-THEN constraint?

I have system with $N_U$ users and $N_T$ transmitters. Multiple transmitters can transmit to a single users and one transmitter can transmit to many users, i.e., two sets of transmitters serving two ...
4
votes
1answer
150 views

Combinatorial Optimisation, Allocation problem

I am trying to solve a problem (in pyspark/ python) where I need to find two distinct values to allocate, and how to allocate them in a network of stores. The two distinct values can only be integer ...
3
votes
2answers
184 views

Optimal way of connecting N sensor to M devices in polynomial time?

Let's say I have 3 type of sensors: A, B, C. These sensors can be connected to multiple devices at the same time: let's call them dA, dB and dC. Now, device dA can only accept connections of sensor of ...
4
votes
1answer
74 views

How would you linearize this scheduling problem? Or how would you solve this? It is variation of a set coverage problem for OpenSolver

So, it's been about 15 years since I took my OR class in college. I'm not versed in any programming language besides a little bit of VBA. A client of mine is looking to solve the following problem. I ...
2
votes
1answer
49 views

Reformulating to locate the second largest decision variable of a set of decision variables

Consider a set of $A_{vn}$ decision variables such that $A_{v1},A_{v2},\cdots,A_{vn}<A$. While this is the standard formulation finding the maximum value of $A_{vn}$, I would also like to find the ...
2
votes
1answer
54 views

Formulating indicator constraint set

I am having difficulty formulating the indicator constraints for the following: Consider a set of $A_{n}$ decision variables such that $A_{1},A_{2},⋯,A_{n}<A$. While all of them are integers that ...
4
votes
2answers
138 views

Is there efficient way to deal with division by zero?

I am trying to solve an optimization problem in which there is an objective function in the following form: \begin{equation}f(x, y)=x+\left(\frac{1}{y}\right)\end{equation} Where, $x,y$ are positive ...
4
votes
2answers
134 views

Constraint $x'Ax = 0$, where $x$ and $A$ are both optimization variables

I'm trying to solve the following optimization problem: $$ \min_{x, \phi} x \quad \text{s.t.} \quad \sum_{s,t = 1}^n \left(m_{s,t} x -v_{s,t} \right)\phi_s \phi_t = 0 , \quad \lVert \phi \rVert = 1$$ ...
1
vote
1answer
90 views

How can I have minimum amount of resources wasted in this resource allocation problem?

I have a demand, $d$ I also have supply from 1000 sources. The supplies from those $N$ (for example, $N=1000$) sources are given by $s_1,s_2,s_3,\cdots,s_N$. So,the total supply is : $s_1+s_2+\cdots+...
4
votes
0answers
74 views

Fast solvers for LASSO-type non-convex optimization problems

Given $y \in \mathbb{R}^{n \times 1}, X \in \mathbb{R}^{n \times p}$, $p > n$, assume a LASSO-type optimization problem in the form of $$ \hat\beta=\underset{\beta}{\operatorname{argmin}}\frac{1}{2}...
6
votes
2answers
71 views

Optimizing MIP Parameters For Various Data Sets

I have a MIP that runs for several different data sets. For each data set the MIP runs multiple times, once for each time period in the data set, and each time period is independent. I've experimented ...
24
votes
15answers
2k views

Recommended books/materials for practical applications of Operations Research in industry

I have a Masters' degree in Mathematics. I've very fair understanding of methods and techniques of Operations Research. I am looking for a good book/material where I can see a lot of examples on Math ...
4
votes
1answer
86 views

how to apply Big M to model the logic constraint (if-then-else)

I was hoping to get some help in modelling the following logic as an MIP Constraint c_{m,l}^{RC} is binary decision variable. Simplify it:
1
vote
0answers
44 views

$\nabla_y\nabla_vf(x^*)\geq0$ for any concave $f$ if and only if $y=-v$

$f:\mathbb R^3\to\mathbb R$ is an arbitrary concave function. $H$ is a plane. $v$ is a given vector on $H$. $x^*=\max_{x\in H} f(x)$ Prove that $\nabla_y\nabla_vf(x^*)\geq 0$ if and only if $y=-v$. I ...

1
2
3 4 5
8