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
5
votes
2answers
846 views

Integer programming problem

I have the following exercise: Stockco is considering four investments. Investment 1 will yield a net present value (NPV) of \$16,000; investment 2, an NPV of \$22,000; investment 3, an NPV of \$12,...
5
votes
3answers
973 views

Solving continuous Minimax Optimization problem

I want to solve a linear programming minimax problem here mathematically without using software: $$\begin{align*} \text{min}\ \text{max} \quad & \{x_1,x_2,x_3\} \\ \text{s.t.} \...
5
votes
2answers
102 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 ...
5
votes
1answer
147 views

ILP Constraint to ensure exactly one constraint from a set of constraints is satisfied

Consider several Integer (0/1) ILP variables, i.e., Boolean variables, $x_i$'s. Consider an ILP constraint $x_1 + x_2 + x_3 \geq 1$ and another constraint $x_4 + x_5 + x_6 \geq 1$. I would like to ...
5
votes
3answers
625 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 ...
5
votes
1answer
125 views

Dual variables associated with same equation for different time instants

I have three equations that are essentially the same equation defined for three time instants. The equations are basically calculating the state of energy of an energy storage facility. \begin{align} ...
5
votes
1answer
420 views

How to run MOSEK solver in CVXOPT

I have written a small code to do a simple min variance optimisation using CVXOPT, you can see the whole code below By using solvers.qp(P, q, G, h, A, b) in CVXOPT ...
5
votes
2answers
89 views

Solve nonlinear programming problems practically

In an exam, I studied Theoretical approaches to converting constrained minimum problems into unconstrained minimum problems. Specifically: KKT conditions Projection Gradient Descent Penalty and ...
5
votes
1answer
120 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: $$\...
5
votes
1answer
202 views

Column Generation algorithm for vehicle routing problem

I want to solve a VRP with a column generation algorithm. The objective of the problem is makespan minimization. In more detail, I want to minimize the arrival time of the last vehicle in the depot. I ...
5
votes
1answer
205 views

How to express this constraint?

I have the constraint \begin{align}\max&\quad\gamma\\\text{s.t.}&\quad a\ge\gamma b\\&\quad\gamma\le 1\end{align} where $\gamma$ is an optimization variable and $a$ is a function of some ...
5
votes
2answers
85 views

Is $\min \ x^3 \ \mathrm{s.t.}\ x \geq 0$ a convex problem?

The problem $$\min \ x^3 \ \mathrm{s.t.} \ x \geq 0$$ is sometimes said to be a convex optimization problem. $f(x) = x^3$ is not a convex function. However, in the domain of $x\geq 0$ it is convex. So ...
5
votes
1answer
90 views

Local minimization of a function over a line

Let $f:\mathbb{R}^n \mapsto \mathbb{R}$ be a differentiable function. Suppose $x^*$ is a local minimizer of $f$ along every line that passes through $x^*$. This means that the function $$g(\alpha) = f(...
5
votes
1answer
329 views

How is Big M calculated?

Because of excessive pollution on the Momiss River, the state of Momiss is going to build pollution control stations. Three sites (1, 2, and 3) are under consideration. Momiss is interested in ...
5
votes
1answer
117 views

Which solver solves PSD constrained convex non-linear problem

I have a problem with a vector variable $w \in \mathbb{R}^n$ and a symmetric matrix variable $V \in \mathbb{R^{n \times n}}$. I am solving a problem which is roughly like: \begin{align} \begin{array}{...
5
votes
1answer
308 views

Python PuLP - Unable to Model Non-Square Matrix

I am having issues with setting up constraints using both input arrays from excel and variable arrays within PuLP. It appears the model only works with square matrices and my final code has a matrix ...
5
votes
1answer
110 views

Maximize number of backups that fit on backup drive

This is an intrinsically "practical" question, but it leads to a well-defined mathematical problem. Let me start with the practical part: I regularly back up my data. My backup strategy are ...
5
votes
1answer
84 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 ...
5
votes
1answer
215 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 ...
5
votes
2answers
174 views

How to linearize a quadratic constraint to add it then via a callback function

Suppose we have a positive continuous variables $0 \le x \le UB$ where $UB$ is a known upper bound. How can we linearize the term $x^2$? Detailled problem: Suppose that via a callback we compute a ...
5
votes
1answer
58 views

Discontinued function optimization

I am struggling with transport optimization problem, that simplified might stated as: Minimize the number of bananas transports to the shop in the following 5 days (...
5
votes
1answer
82 views

Prove that $x^*$ is an optimal solution where $f_0$ is $C^1$ and convex and $f_i$ are $C^1$ and strictly convex functions

Let $x^*$ be a feasible solution of the following convex optimization problem \begin{align}\min&\quad f_0(x)\\\text{s.t.}&\quad f_i(x)\leq0,i=1,\ldots,m\end{align} where $f_0$ is $C^1$ and ...
5
votes
1answer
105 views

Minimize binary variable's distance with respect to the index values

For a given binary decision variable $x[i,j,k]$ my goal is to get as dense results in terms of k for successive values of j. Distance of k value to be kept as close as possible throughout j values: $d ...
5
votes
2answers
124 views

Minimizing $x_1/x_2$ over a simplex in the positive orthant

I need to solve the following problem \begin{align}\min&\quad x_1/x_2\\\text{s.t.}&\quad Ax \leq b\\&\quad x > 0\end{align} where $A$ is a positive matrix. The best thing I can think ...
5
votes
2answers
68 views

AMPL implement constraint

I'm trying to implement the following in AMPL: $$ i \in [N], j \in[N] \backslash \{i\}, t \in [T] $$ I have so far written the following: ...
5
votes
1answer
88 views

How to linearize difference of absolutes?

How to linearize difference of absolutes? $$|a|\ge k|b|$$ where $a,b$ are variables and $k$ is a constant.
5
votes
0answers
54 views

Reference request — fishery yield optimization

I'm looking for references to do a review of research on managing fisheries in industry. I've seen adaptions of population growth models which include some harvesting constant or function and was ...
5
votes
0answers
222 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 ...
5
votes
0answers
43 views

Mixing time exponent above threshold temperature for Glauber dynamics or annealing

It is well-known that the Glauber dynamics will converge in polynomial time to the Gibbs distribution for, say, the Ising model on a d-regular graph at high enough temperatures $T>T_c$. There are ...
5
votes
0answers
287 views

What is the difference between root relaxation and LP relaxation

(I apologize. I saw this question but, I do not know these may be the same or not.) I am trying to solve a MIP problem and have an issue about that. The problem's LP relaxation has the objective ...
5
votes
0answers
122 views

A good memoryless elevator strategy?

Could you OR whizkids please help me out with this one: https://stackoverflow.com/questions/61854621/a-good-memoryless-elevator-strategy Surely somebody has solved this before. How do you classify ...
5
votes
0answers
33 views

In a binary logistic regression context, how to introduce a constraint to model the dependency between consecutive samples

Imagine we are running a logistic regression to identify opportunities for car sale promotion, using previous promotion campaign's result. Each $y$ is the increase of car sale after the promotion. ...
4
votes
3answers
818 views

Branch and bound algorithm programming code

I want to solve an integer programming problem using the branch and bound method, but I'm having trouble finding the programming code. From what I saw, almost all algorithms use it for traveling ...
4
votes
3answers
793 views

Shortest path problem

At the beginning of year 1, a new machine must be purchased. The cost of maintaining a machine $i$ years old is given in Table 5. The cost of purchasing a machine at the beginning of each year is ...
4
votes
2answers
747 views

Shortest path problem with boxes

A company sells seven types of boxes, ranging in volume from 17 to 33 cubic feet. The demand and size of each box is given in the following table. The variable cost (in dollars) of producing each box ...
4
votes
2answers
207 views

Two-Objective Optimization in CPLEX

Until now, I used CPLEX to solve single-objective optimization problems only, but now I need to solve a two-objective mixed-integer linear optimization problem and I noticed that CPLEX 12.6.9 (unlike ...
4
votes
1answer
187 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{...
4
votes
2answers
139 views

Maximum Flow Problem : Can someone refer me to accessible valuable resources

Can anyone please refer/suggest me some accessible papers, works, books, websites, documentation related to The Maximum Flow Problem.
4
votes
2answers
289 views

What are the most useful evaluation metrics when comparing the performance of different model formulations

Suppose you are writing a paper about a certain new problem class. You have certain problem instances of different size (real-world as well as random) given. You developed different integer ...
4
votes
1answer
480 views

Having negative value for non basic variable gives a infeasible solution in simplex method?

I try to solve the following linear program with the simplex method: $$ \begin{alignedat}{4} \max & \quad & x_1 & {}-{} & 2x_2\\ \text{subject to} & & &...
4
votes
2answers
182 views

Mixed-integer optimization with bilinear constraint

So I have an optimization problem of the following form: \begin{aligned} \max_{x,y} \quad & \sum_i x_i \\ \text{s.t.} \quad & \sum_i x_iy_i \leq a \\ \quad & x_{\min} \leq x \leq x_{\max} ...
4
votes
1answer
111 views

One and two period policy for inventory situation

The following exercise is in the book Operational Research by Hillier, 7th edition, page 978. In this exercise $p$ and $p$ are the stockout and holding cost parameters, respectively. $𝑦^0_i$ is the ...
4
votes
1answer
146 views

how to implement an optimization function with polynomial in Gurobi (Java)

I have the following problem: I have an objective function with the optimization variable $x$, which looks simplified like this: $ZF = (a+b)*(x+1)$ Here $a$ is simply a constant value. However, behind ...
4
votes
2answers
156 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
1answer
91 views

Analytically finding the maximizer of a trace optimization problem

$A \in \mathbb{R}^{m \times n}$ is an arbitrary data matrix. Moreover, $w \in \mathbb{R}^m$ is a data vector which is a probability vector, i.e., $w\succeq 0, \sum_{i=1}^m w_i = 1$. I have a ...
4
votes
1answer
428 views

How to read a solution file (.sol) in cplex python API?

I've been to trying to read a .sol file in cplex python API before solving the problem but couldn't find any command to do so. There are analogous commands for this ...
4
votes
1answer
268 views

Scheduling Optimization Problem

I want to solve below optimization problem. This is scheduling problem where I seek to complete as many of the jobs $\xi_l$ (objective function and constraint 1), with $T_C$ being the last time until ...
4
votes
2answers
124 views

Continuous water-filling optimization problem

Disclaimer: this question has been previously posted on Math StackExchange. I reposted it here since I did not receive any satisfactory answer there and a user suggested to re-post it here. Let $x\in\...
4
votes
1answer
139 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 (...
4
votes
2answers
143 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
3 4
5
6 7
10