Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [optimization]

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

1
vote
1answer
19 views

Reduce the total internal border of a set of touching rectangles (using graphs)

I have a set of touching rectangles (Initial problem), and an associated graph relating the rectangles through the edges. I want to reduce the rectangles through graph operations to the minimum ...
0
votes
1answer
14 views

Distribute repeated values into bins as evenly as possible

Preface I've asked a very similar question already on stack overflow in a different wording and gotten a working answer under the assumption that there is no way to go through all possibilities (np-...
0
votes
0answers
35 views

Fast Boolean minimization

Two level boolean logic minimization(AND, OR, NOT) for big number of variables,(say n) is time consuming. I want to minimize an n variable sum of Product form boolean expression efficiently where n ...
0
votes
0answers
17 views

Feasible algorithm to find interpolating complex polynomial based on absolute value

Consider a complex degree-$(n-1)$ polynomial $p(z) = \sum\limits_{i=0}^{n-1} a_i z^i$. Given a number $0 > m > 2n$ of positions in the complex plane with absolute value requirements, i.e. $|p(...
1
vote
0answers
23 views

Big M method for continuous variables

Is there any way to model the big M method for continuous variables? Something similar to this but $B, C \in \mathbb{R}_{\geq 0}$ and $A\in\{0,1\}$. Due to the precision problem, when the $B$ and $C$ ...
2
votes
2answers
52 views

Algorithm challenge: build a pile of 'n' cubes whose total volume adds up to 'm'

I'm working on solving an algorithm problem defined as follows (important parts in bold): Your task is to construct a building which will be a pile of n cubes. The cube at the bottom will have a ...
-1
votes
0answers
15 views

How to transfer the following model into MILP formulation?

if xmin<=x<=xmax then y=1; otherwise y=0; here, y is a binary variable,x is continuous variable,xmin and xmax are upper bound and lower bound of x respectively.
0
votes
1answer
27 views

Find the cheapest combination of raw foods that fulfill nutritional requirements

I am starting a raw food diet and would like to properly plan it, and thus, would like to create a program that takes a list of available raw food, and finds the best combination of foods (multiples ...
0
votes
0answers
15 views

If I have two variables, x and y, which are constrained to only be {0, 1}, is there any way to multiply/AND them using only addition/subtraction

Basically I want to add and subtract x and y using some linear operations to AND/multiply the values. The use case is a linear program, which is why I don't want to introduce new variables/can't ...
0
votes
1answer
45 views

Solving the Knapsack problem in $O(v^*n^2)$, where $v^*$ is the maximum value of all $n$ items

For my study I am supposed to develop an dynamic programming algorithm which solves the following simplification of the Knapsack problem in $O(v^*n^2)$ time ($v^*$ is the maximum value of all elements)...
0
votes
0answers
18 views

Method for optimizing many levels of iteration where some combinations can be discarded

I have the following problem which I wish to optimize: Find the value $n$ for which the function $f(n)$ is maximized, where $0 < n < 3^{36}$. An optimization is possible, given that when ...
0
votes
0answers
8 views

Best way to handle this optimizatio problem

I am having problems with an optimization problem. {a,b..e} are access nodes, and {1,2..} are hubs In the diagram, It can be seen, that we have some allocations based on the criteria of minimum ...
2
votes
1answer
107 views

What is the right term/theory for prediction of Binary Variables based upon their continuous value?

I am working with a linear programming problem in which we have around 3500 binary variables. Usually IBM's Cplex takes around 72 hours to get an objective with a gap of around 15-20% with best ...
0
votes
0answers
16 views

Maximization Modularity using SDP relaxtion

I am trying to clustering the graph by maximizing modularity where modularity is given by: $Q=\frac{1}{2m} \sum \limits_{i,j}\left(A_{ij} - \frac{d_i d_j}{2m}\right)\delta(c_i,c_j)$ or equalvance ...
0
votes
0answers
9 views

How to derive the optimal bayesian solution to a model of two normal distributed populations

In the "Introduction" section of the paper Support-Vector Networks, it mentioned Fisher's solution to a model of two normal distributed populations: My questions are: How to derive equation (1)? I ...
1
vote
0answers
20 views

Algorithm for first-price, sealed bid simultaneous auctions for distinct items and budget-constrained bidders

Context: I play in a simulated online basketball league (a la the NBA) where each human player controls one of the teams. When each simulated basketball player is a free agent (that is, their previous ...
0
votes
0answers
13 views

What are “self-adjusting computation” and “dynamic programming”, and how are they different?

According to this website: Self-adjusting computation refers to a model of computing where computations can automatically respond to changes in their data The papers linked on this page make ...
-1
votes
0answers
9 views

Booking problem

Have a list of busy intervals and resources (resource Ids), start, end, resourceId 1-1-2018, 1-2-2018, 32423 1-1-2018, 1-2-2018, 42352 Need to find out an ...
0
votes
0answers
5 views

How to understand the separation phrase for generalized subtour constraints?

Suppose the constraints of our integer programming model consist of two parts: the polynomial-size formulations, that have a size (number of variables and constraints) which is polynomial w.r.t. the ...
2
votes
0answers
27 views

Maximum-minimum-satisfiability

In MAX-SAT, we are given a formula and want to maximize the number of satisfied clauses. I.e., given a formula $\phi = c_1 \cap \cdots \cap c_n$, where each $c_i$ is a disjunction, we want to find the ...
0
votes
1answer
24 views

Determining cycle time and and hold time in logic circuits

First I have general question. In a circuit with both logic and D edge flip flop does hold time have to satisfy $t_{hold} < t_{setup}($D-FF$) + t_{pd-min}$(Logic), or is it enough that $t_{hold} \...
5
votes
1answer
108 views

Find a strategy to evade hungry lions on the real line for the longest time

This is an interview question I was asked, which I don't know how to approach. I would appreciate pointers to algorithms I should look up. You are placed on the real line, and there also are $K$ ...
1
vote
1answer
24 views

Minimizing the area of a simple polygon by modifying/adding to a subset of its vertices

I'm trying to minimize the area of a simple (non-intersecting, without holes) polygon by adding points to it, or modifying points of its subset. Let me describe this more formally: Let: $P$ be a ...
0
votes
0answers
20 views

Optimizing with diminishing marginal utility

Let $M$ be the integer number of dollars available, and let $P$ be a set of products to buy. Assuming that for each product its marginal utility decreases as you buy more of it. How to find the ...
2
votes
0answers
24 views

Given a set of point sets, find points from each set with maximum total distance between them while each distance is larger than a threshold

The title may be a bit confusing but the problem is this; Lets assume I have 5 points in 4 groups (in total 20 points). What I want to achieve is; -> Pick one point from each group (we will have 4 ...
0
votes
0answers
32 views

Maximizing score of partitioning of table

Consider a table where the cells are Boolean values and rows & columns are positive integers. \begin{array}{|c|c|c|c|c|c|c|} \hline & a_1 & a_2 & a_3 & a_4 & \dots & a_n \\...
1
vote
1answer
83 views

Help needed for understanding proof of No Regret Multi Armed Bandit Algorithm

I was reading Elad Hazan's book on Online Convex Optimization(http://ocobook.cs.princeton.edu/OCObook.pdf) and am facing difficulty understanding the proof given for the No regret algorithm for MAB (...
1
vote
0answers
16 views

Expected development of 'fitness histogram' for PSO over time

I'm plotting the fitness histogram of my particle swarm optimizer - i.e. the individual fitness scores for each particle and iteration - during a run. The problem tackled is basically curve fitting/...
0
votes
1answer
56 views

Finding minimum number of edges such that when adding into the graph, the graph is a 2-connected graph

Given is a undirected and 1-connected graph G=(V,E). Between every two node b=(u,v) in graph G there is a cost c_b to build another edge(Regardless of whether (u,v) ∈E or not). We use a C={c_b |c_b∈Z^+...
0
votes
1answer
74 views

What is the difference in SMO algorithm for SVM and SMO for one class?

Please let know if this is not the correct forum to ask this question. If not can anyone please tell where can I ask this question? I am trying to understand the difference between the paper : https:/...
0
votes
0answers
30 views

How to select the best genetic algorithm for optimization?

I am trying to optimize parameters for a trading strategy, with many local/global maxima. I need to run a backtest for each new parameter set, which takes minutes to hours. I am wondering, if my own ...
2
votes
1answer
30 views

Computational complexity of maximizing sum of rational functions

I have a optimization problem: $$\max_z\ \sum_{i=1}^n \frac{W_i}{D_i - z_i} \quad \text{s.t.}\ \sum_{i=1}^n z_i \leq k, z_i \in [0,k],$$ where each $W_i$, $D_i$ are constants and $z_i$ are integer ...
0
votes
1answer
29 views

Stable matching with asymmetric arrays (gale shapley)

I was reading this thread The stable marriage algorithm with asymmetric arrays and started to solve the problem asked in this thread about matching 5 students with 10 dorms. One of the answer ...
0
votes
1answer
26 views

If value of LP relaxation of s-t minimum cuts is P ,then wen can find a s-t cut at most P edges?

My problem is mainly from this lecture notes on convex optimization here page4 Consider a s-t Minimum problem, on unweighted undirected graph $G=(V,E)$,we can formalize in following linear integer ...
0
votes
1answer
24 views

Interpretation of Backtracking Algorithm Problem - weighted matching

I am attempting to resolve the following problem using Backtracking: Suppose that you have $n$ men and $n$ women and two matrices P y Q (n x n); such that $P_{ij}$ is the preference of the man $i$ ...
0
votes
0answers
4 views

Looking for a specific type of ADMM iterates

For a $k-$dimensional optimization variable $b \in \mathbb{R}^k$ say the objective is given as, $$f(b) = \langle b, v \rangle + \langle b , Ab \rangle + \lambda \Vert b \Vert_1$$ for some parameter ...
1
vote
2answers
99 views

Knapsack problem: equal profits

I am looking for references to efficient algorithms that solve knapsack problem where all profits are equal. More formal definition of the problem from a Wikipedia article on KPs: If all the ...
0
votes
0answers
39 views

A combinatorial optimization problem with restrictions

Assume $A$ is an $n \times m $ matrix. How can we select $n$ elements, one element from each row, such that their sum is minimized, subject to the following constraint: we can choose the elements from ...
0
votes
0answers
11 views

Two-dimensional equal frequency (/ equal height) binning

I have an optimization problem, which is comparable to finding equal height histograms. However, in my case the problem has two dimensions: Given a set of coordinates C and two bin counts n and m, ...
2
votes
1answer
19 views

Positioning items to maximize separation

Say we want to place n items on the real line. Let us denote the position of item i by $p_i$. We have interval constraints on the position $p_i$, i.e. we are given $l_i, r_i$ such that $l_i \le p_i \...
1
vote
1answer
41 views

Variant of interval scheduling with varying task durations

I am probably just missing the correct term for my problem to find the solution but here it goes: I have a set of tasks with a given duration and an interval for each task in which it has to be ...
0
votes
0answers
11 views

Algorithm to distribute text evenly across N columns

What is the algorithm that implements CSS's multi-column layout with balanced fill? Mathematical formulation: given a list of positive numbers (those would be the heights of the items to arrange), ...
4
votes
1answer
146 views

How to produce nonzero absolute differences between neighboring numbers on a circle as long as possible?

I apologize for the lack of an even better title. The main reason I couldn't find a better one is because I have a problem that I cannot find reference anywhere. I am pretty sure it has a name, but I'...
1
vote
0answers
36 views

NodeJS vs Golang Performance [closed]

I was testing performance of NodeJS vs GoLang with a very simple script. Situation one is three nested for loops to do a Sin calculation and Situation two is just one for loop. It turns out that for ...
1
vote
0answers
10 views

Sparse feasible solution $|x|_0\le k$ for system of linear inequalities $A x \le b$

Suppose the set of linear inequalities $Ax\le b$, in which $A\in\mathbb{R}^{m\times n},x,b\in\mathbb{R}^n$ is given. Is it possible to determine in polynomial time with regard to $m$ and $n$ if there ...
3
votes
1answer
46 views

Is there an algorithm that can find a solution that solves the most number of equations in a linear system of equations?

My apologies if this question makes no sense. I am trying to find an algorithm that can solve a linear system of equations. Unlike most problems like this, this algorithm does not need to find a ...
3
votes
1answer
106 views

Minimize sum of squares of rows in matrix when sum of columns have some constraint

I'm looking for an algorithm that can find any matrix $a_{j,i}$ such that $$ \sum_{i \in I} \left(\sum_{j\in J} a_{j,i}\right)^2 $$ is minimal, while also for each $j\in J$ satisfying the constraint ...
3
votes
2answers
48 views

Optimization Problem when calculating fitness is expensive

I need to solve an optimization problem, maximizing fitness in a set of around 1 million solutions. Calculating the fitness of any solution is very time consuming, taking around 5 minutes. Therefore, ...
0
votes
1answer
35 views

On the proof of NP-Hardness of the Cardinality Constrained Quadratic Knapsack Problem

in Polyhedral Study of the Cardinality Constrained Knapsack Problem the authors prove that the Cardinality Constrained Knapsack Problem is NP-Hard by reducing PARTITION to it. Besides, it's easy to ...
2
votes
0answers
18 views

How to minimize the number of gates of an arithmetic circuit?

A circuit is simply a DAG, with some input wires, some output wires, and some operations on the vertices. Consider an arithmetic circuit where the only operations are addition ($+$) and ...