Questions tagged [optimization]

Questions about problems that entail selecting the best element from some set of available alternatives, and methods to solve them.

Filter by
Sorted by
Tagged with
1
vote
1answer
13 views

update distance matrix between n points

I am looking for an efficient algorithm to update a $N*N$ matrix, in which the coefficients represents the distance between $N$ number of points, every time that the coordinates of a point change in a ...
1
vote
0answers
26 views

combination of traveling salesman with knapsack

I am trying to create an optimisation process for a variant of the travelling salesman problem which is combined with a knapsack problem in the following way: Let there be a set of points $P$ on a two-...
3
votes
0answers
28 views

Optimization on hypergraph "refinements"

Given a hypergraph $H = (V, E)$, call $H' = (V, E')$ a refinement of $H$ iff there exists a partition $p : E' \to I$ (where $I$ is an arbitrary index set) such that $E = \{\bigcup_{x \in p^{-1}(i)} x \...
0
votes
0answers
42 views

Finding a set of 9 integers that minimize an error function

I have an algorithm that takes a 3d triangle PMN(which is constructed from running a function that converts per-vertex UV coordinates to a PMN triangle) and P' which is a randomly chosen 3D point that ...
0
votes
1answer
41 views

How can i do this type of swap(4-opt) between 4 edges of a graph?

The double bridge move is a specific type of swap between 4 edges of a graph, also called 4-opt. It consists of removing 2 pairs of edges. Let`s call them (I, I+1), (J, J+1) and (P, P+1), (Q, Q+1). ...
0
votes
0answers
24 views

Complex profit optimisation problem (logistics and trading)

Problem statement There is a number of towns $\{T_1 \dots T_n\}$, a number of items $\{I_1 \dots I_n\}$ and a number of lorries $\{L_1 \dots L_n\}$. Each town $T_n$ has a market which offers a ...
4
votes
0answers
56 views

minimizing a pairwise sum with respect to a sequence of integers

Let $m$ and $n$ be two integers, where $m \leq n$. Suppose you are given $m^2$ matrices $W^{i,j} \in \mathbb{R}^{n \times n}$ for $i, j \in \{1, \dots, m\}$. The goal is to find a sequence $a$ of $m$ ...
0
votes
0answers
27 views

Solving Lasso via ADMM

I have a question regarding the theory behing solving Lasso's optimization problem via ADMM. Let's look at this pdf https://candes.su.domains/teaching/math301/Lectures/Consensus.pdf. First rewrite the ...
1
vote
1answer
31 views

Minimum steps needed to partially cover a sequence of points on a grid

Problem statement: You are in a 2D grid where you can move in any of the 4 directions, no obstacles. You start at position (0, 0). We say that you partially cover a point $(x,y)$ if your position has ...
5
votes
0answers
89 views

Optimization problem with discrete and continuous components

Suppose we have a sequence of $m$ tokens $(T_1, T_2, \ldots, T_m)$. We can split this sequence considering two parameters $w$ (which is the width of the window) and $x$ which is the overlap between ...
0
votes
0answers
32 views

ILP - Maximize the number of pairs of variables with the same value

I have a 0-1 integer linear program for a set of $2n$ variables $S = \{x_1, ..., x_n, y_1, ..., y_n\}$. My objective is to maximize the number of pairs $(x_i, y_i)$ such that $x_i = y_i$, $i = 1, ..., ...
0
votes
0answers
21 views

minimizing std. dev. in linear programming

I'm new to Linear Programming and trying to create an automated scheduling algorithm, and am having trouble defining the objective function and decision variables. Any help would be appreciated: Let ...
0
votes
0answers
34 views

What can I say about complexity of this optimisation problem?

I have a set of parameters $\{\alpha_s\}$, and I have $u$ functions of the form $w_i(\{\alpha_s\}) = \prod\alpha_s^{c^{i}_s} $ for some known values of $c^{i}_s$. Similarly, I have $b$ functions of ...
1
vote
0answers
50 views

Does the standard 4/3 integrality gap for TSP example work for Euclidean TSP?

The standard LP gap example for the held karp relaxation for TSP min $ c^tx $ $x(\delta(S)) \geq 2 $ $x(\delta(v))=2 $ $x \geq 0$ Is to have two triangles and three long paths connecting the ...
0
votes
0answers
27 views

traveling salesman problem with k-nearest-neighbor algorithm

I tried to solve a problem similar to the TSP problem using the Nearest Neighbor algorithm. The solution was not efficient enough. Then I tried sorting the items with nearest neighbor first and then ...
3
votes
1answer
140 views

A complexity class between P and FPTAS

The question is about approximation algorithms to NP-hard optimization problems. For concreteness, let $M$ be a minimization problem with $n$ inputs, where all inputs and outputs are integers in the ...
1
vote
0answers
9 views

How to optimize the locations and orientations of a collection of irregular 3D objects?

I'm working on a project where I need to optimize both the locations and orientations of a collection of irregular 3D objects in a given simulation box. To optimize the locations and orientations ...
0
votes
0answers
23 views

Optimization Problems which very deep local minima

I am looking for combinatorial optimization problems which have very deep local minima. So I am searching for the global optimum (which is not unique). Are there some games or problems you know which ...
2
votes
1answer
33 views

Optimal order to minimise time until first success

Say you are a salesperson and you want to make a sale; there are $N$ customers on your list; customer $i$ takes $t_i$ time to talk to and there is $p_i$ probability to make the sale to that customer - ...
0
votes
1answer
33 views

Independent set problem with given black box

I'm very new to P and NP complexity classes and reductions. I'm trying to solve this problem and I want to verify my solution and if it is wrong, understand why. Suppose that I'm given a polynomial ...
2
votes
0answers
23 views

How do video games like Age of Empires code how a soldier spots an enemy soldier and decides to attack?

I was just curious how do RTS games actually implement this. There are usually thousands of units on the whole map. They all have usually unique range of sight and then there's also settings for ...
3
votes
0answers
71 views

Deciding whether a given flow is unique in $O(\lvert V \rvert + \lvert E \rvert)$ time

I am stuck with the following exercise: Is it possible to decide whether a given flow $f$ is a unique mamimum flow in $O(\lvert V \rvert + \lvert E \rvert)$ time? I am not sure that this is possible....
0
votes
0answers
13 views

Arranging rectangular textures in square texture atlas and optimize sub texture proximity

I have a mesh consisting of about 100'000 - 200'000 quads. Each quad has a rectangular texture. I'm packing these rectangular textures into a power-of-two atlas. My packing algorithm currently works ...
5
votes
0answers
112 views

discrete optimization problem with a matrix inverse

I'm trying to solve this discrete optimization problem:$\newcommand{\I}{\mathcal{I}}\newcommand{\R}{\mathbb{R}}$ $$\max_{|\I| \le k} f(\I) \qquad\text{where}\; f(\I) :=x_{\I}^{\top} (\Sigma_{\I})^{-1} ...
2
votes
1answer
36 views

Efficient solution for a particular form of quadratic Diophantine equation

Preface: I know there are a lot of posts already here and elsewhere about algorithms for solving quadratic Diophantine equations in general. I am posting this in the hope that my very particular case ...
1
vote
0answers
46 views

Shortest path as a linear program

I just encountered this formulation of the shortest $s$-$t$ path problem as a linear program in a homework. I don't understand exactly the meaning of the variables and restrictions. Here, $G = (V, E)$ ...
2
votes
1answer
57 views

Why is this equality about the relative translation in the iterative closest point (ICP) algorithm obvious, and how can I derive it?

I'm a computer science bachelor student tasked with understanding On the ICP Algorithm by Esther Ezra, Micha Sharir, and Alon Efrat, and I'm having a lot of difficulty with even supposedly obvious ...
3
votes
0answers
58 views

Graph coloring problem with violations

I would like a name for the following problem. We consider a relaxed vertex coloring problem, where Let $k$ be the number of colors Let $B$ be the set of edges violating coloring, i.e., $$B := \{(u,...
1
vote
1answer
22 views

Efficient intersection detection between disks with identical radius

I have a set of $N$ points randomly positionned on a rectangular space (btw with either absorbing, reflecting or wrapping boundaries), and I need to obtain the distances between every 2 points whose ...
1
vote
0answers
28 views

Minimize waste for wood router machine

I am not sure if this is the right place to ask this question but of all StackExchange communities, this looks to be the closest one. We have to cut an equal number of circles of 5 different diameters ...
2
votes
1answer
56 views

Cover 2 by n binary matrix with submatrices of minimum total size

This is a homework problem. Let $A$ be an input binary matrix of size $2 \times n$, and $L$ an integer. The objective is to cover all 1s in $A$ with submatrices, such that we minimize the sum of the ...
1
vote
1answer
81 views

How to get the highest score in this game?

I would like some advice in this homework question. There is a three players game, in which each player ($A, B$, and $C$) is given a $n$-length array of integer values. There are $n$ rounds in this ...
0
votes
0answers
22 views

Fitness Functions, Landscapes and Basins of Attraction

In optimization, particularly evolutionary computation, we often try to optimize (through either minimization or maximization) non-smooth, non-differentiable, discrete functions that aren't readily ...
0
votes
0answers
35 views

Minimum General Routing Problem

I have been researching about general routing problems and came across a type TSP problem as: "Find a minimum cost cycle in a graph G = (V, E) which visits vertices in a required subset V′ ⊂V ...
0
votes
2answers
122 views

LQR optimal control of accumulator via dynamic programming

Let $$ x_{k+1} = x_k + u_k, \qquad x_0 = 5 $$ where $k \in \{ 0,1,2,3 \}$, define the return function $$ - \sum_{k=0}^3 \left( x_k^2 + u_k^2 \right) $$ with the following inequality constraints on the ...
0
votes
1answer
14 views

Same instances for different problems

According to the formal definition of an instance, it is a set of input data containing the values of the parameters of some problem (What is an instance of NP complete problem?). So, two problems may ...
1
vote
1answer
33 views

Determine the time complexity of this algoritm (pseudocode)

{ t <- n while t>1 do t <- log_2(t) } I tried to do it this way: $f^\text{(1)}(t)=\log_2(t) \\ f^\text{(2)}(t)=\log_2\log_2(t) = \log_2^{(2)}(t) \\f^\...
1
vote
1answer
34 views

Assigning balls to bins with constraints

Let $S= \{ b_{11}, b_{12}, b_{21}, b_{22}, b_{31}, b_{32},\dots, b_{n1}, b_{n2} \}$ be a set of $2n$ balls grouped in $n$ pairs, and $T = \{ B_1, B_2, \dots, B_m\}$ be a set of $m$ bins with ...
2
votes
0answers
46 views

How to impose distance constraint without quadratic constraints?

I have a set of variables $\{x_i\}$ that I want to optimize according to some objective function. However, I would like that $$(x_i-x_j)^2 \geq d^2\ \ \ \mathrm{for\ all}\ \ \ i,j$$ Which is a lower ...
1
vote
0answers
37 views

Set partitioning algorithm that aligns centroids

I have a collection of points $C := \{x_1, \ldots, x_{60 N}\}$ in 3D space. I am looking for a partition of $P$ of $C$ with the following properties: Each of $P$'s sets contains $60$ points, i.e., $P ...
0
votes
0answers
33 views

how do i formulate this assignment optimisation problem?

Individual i, associated with organization k, are to be deployed at facility j. Each individual has a cost cij of being deployed at j, and each facility has a minimum number of men required bj. In ...
2
votes
2answers
397 views

Minimize the expected value of money spent on boxes until the prize is found

There are $n$ closed boxes and one and only one box of them contains a prize. The $i$-th box has probability $p_i$ of containing a prize. A player must pay $c_i$ coins to open the $i$-th box. The ...
0
votes
0answers
16 views

How to write code for levy flight in cuckoo search

I want to write levy flight random number distribution code for cuckoo search optimization. So how to select randomly two instances from set of instances by levy flight.
0
votes
1answer
29 views

How can I develop an algorithm to schedule production?

Given an an table that contains products I am selling with the dates, and given a table that contains the possible work orders with each work order, arrange the work orders such that all items are ...
0
votes
0answers
19 views

the convergence of the iterative algorithm has a major problem

In order to solve an optimization problem, I divided the main problem into two sub-problems. The two sub-problems require to be solved iteratively until the algorithm converges. I use the bi-section ...
0
votes
0answers
50 views

Finding the Solution out of N possibilities

Suppose there are 10 (4x4) matrices, where the elements in each matrix are dependent on one variable ($\theta$) non-linearly. All the matrices are independent of each other, so there are 10 $\theta$s (...
1
vote
0answers
21 views

Software/library to generate Ising models for random $k$-sat problems

Could someone point me to a software/library which lets one to generate the Ising model/spin model for random $k$-sat problems or $k$-sat problem of a given structure? I understand that it will be ...
1
vote
0answers
36 views

How to choose the initial temperature in the Boltzmann selection method?

Using the Boltzmann selection in genetic algorithms, the probability of visiting a point in optimization space $X_j$ is $p(X_j)=\frac{\exp\frac{-f(X_j)}{T}}{\sum_i \exp \frac{-f(X_i)}{T}}$ my question ...
0
votes
1answer
25 views

Minimum spanning tree where weights of edges are intersecting sets

Given Graph $G=(V, E)$, where each edge in $E$ is assigned a "weight" as a set of elements. $w(e) = S_e \ \forall e \in E$. Find a subset $E' \subset E$ such that it spans $G$, i.e., $E'$ ...

1
2 3 4 5
32