algorithms – Solving quadratic assignment problem with two metrics using MIP solver

The problem is the following following:

N = {1,...,m} - servers;
Q = {q{1},...,q{m}} - the required amount of resources for tasks, where qi is the required amount of resources for task i;
T = {1, ..., k} - tasks;
V = {v{1}, ..., v{k}} - the amount of resources on servers, where vi is the amount of resources on server i;
DA - the matrix with the amount of data transferred between tasks. DA{i,j} is the amount of data transferred between task i and task j;
NC - the matrix with the network speeds between servers. NC{i,j} is the network speed between server i and server j;
IC - the matrix with a penalty for assigning two tasks on the same server. IC{i,j} is the penalty for assigning task i and task j on the same server;
x{i,j} = 0 if task i is assigned on server j and x{i, j} = 1 if task i is not assigned on server j

I want to minimize the total communication time and minimize the total penalty in two steps. The first step is to minimize the total penalty and the second step is to minimize the total communication time with the penalty constraint.

Total communication time:
enter image description here

Total penalty:
enter image description here

Constraints:
each task is assigned to exactly on server:
enter image description here

the total required amount of resources for tasks on servers does not exceed the available amount of resources on the servers:
enter image description here

and:
enter image description here

Hence the optimization problem is:
enter image description here

To make the objective function linear, I add constraints z{t1,t2,n1,n2} >= x{t1,n1}+x{t2,n2}-1, z{t1,t2,n1,n2} <= x{t1,n1}, z{t1,t2,n1,n2} <= x{t2,n2}, 0 <= z{t1,t2,n1,n2} <= 1

First step:
enter image description here

Let min_penalty be the result of the first step, then the second step:
enter image description here

Is everything correct?

P.S. Sorry for the grammar mistakes and formatting.

Group of similarity classes of a quadratic form over a complete discretely valuated field

Let $F$ be a c.d.v. field with uniformizer $pi$ and let $q$ be a quadratic form over $F$, so $q=<u_1, …, u_m> + pi <v_1, … , v_m>$ where the $u_i$ and $v_i$ are units in the valuation ring. Are we able to describe the similarity factors of $q$ in terms of the $u_i, v_j$ and $pi$? The similarity factors of $q$ are defined to be the $ain F^times$ such that $aqcong q$.

gt.geometric topology – Quadratic cusp shape

Which hyperbolic $3$-manifolds are known to have quadratic cusp shape?

Explanations: Cusps of hyperbolic $3$-manifolds are products torus x interval. They lift to horoballs in hyperbolic $3$-space, where the boundaries (horospheres) inherit a euclidean metric. (Differently sized horoballs yield the same similarity class of Euclidean metric.) The horosphere can thus be identified with ${bf R}^2$ and projection from the horosphere to the boundary torus of a cusp corresponds to dividing out a lattice from ${bf R}^2$. The „cusp shape“ is meant to be the shape of this lattice. The question is, for which (say $1$-cusped) manifolds one obtains a square lattice.

ordinary differential equations – Nondimesionalization of the ODE for a falling object subject to Quadratic Drag Law.

Given the ODE describing an object falling through the air subject to the quadratic drag law:
$$dfrac{dv}{dt}=-g -dfrac{beta}{m}v|v|$$
where $beta$ is a dimensional drag coefficient, how would we go about nondimensionalizing it? I’m really stuck on finding $v_o$ and $t_o$ s.t. $v(t) = tilde{v}(t)v_o $ and $t = tilde{t}t_o $.

Thanks in advance!

pr.probability – Uniform convergence of random Fourier quadratic forms

Let $xi_k$, $k in mathbb {Z}$, be a sequence of independent Rademacher random variables. Is there
a characterization of those families $a_{k,ell}$, $k, ell in mathbb {Z}$, of complex numbers such that the quadratic form
$$
sum_{k, ell in mathbb {Z}} a_{k, ell} , xi_k xi_ell , e^{itk} e^{isell}, quad t,s in [0, 2pi],
$$

is almost surely uniformly convergent?

generate quadratic functions to evaluate membership of points

Here’s an answer; there could be some cleanup done, and I need to explain why some of the auxiliary functions work. But here you go—I tried to explain how it works in inline comments along the way, so that you can simply copy-paste the whole code block and run it.

(* Given a list of coefficents {a, b, c}, make a polynomial
 function—this can be done with FromDigits. *)

makePolynomial(coeffs_List) := Evaluate(FromDigits(coeffs, #)) &

(* Example: makePolynomial({1, 2, 3}) ==> 3 + 2 #1 + #1^2 & *)

(* Format polynomials as a function definition,
using fname and var for the lhs: *)

polynomialFormat(fname_, var_)(f_) := 
 With({poly = Reverse@Inactivate(f(var), Plus)}, 
  HoldForm(fname(var) = poly))

(* Example: polynomialFormat(f, x)(makePolynomial({1, 2, 3})) ==>
   f(x) = x^2 + 2 x + 3 *)
(* We expect to apply TraditionalForm to this to make it look nicer. *)

(* Format a 2D point as a tuple: *)

pointFormat({x_, y_}) := Row({"(", x, ", ", y, ")"})

(* Again, we expect to apply TraditionalForm. *)

(* If the first argument is True, get a point from the
graph of the function; if false, get one definitely not from the graph. *)

ifGetPoint(xrange_ : {-9, 9}, yrange_ : {-25, 25})(bool_, f_) :=
 With({x = RandomInteger(xrange)},
  If(bool,
   {x, f(x)},
   Block({y = RandomInteger(yrange)},
    While(y == f(x), y = RandomInteger(yrange)); {x, y})
   )
  )

(* Ok, main function. We allow parameters for the range of 
coefficients, the percentage of answers which should be 
true, and the range in which to select a "false" point. 
All but the number of rows requested can be omitted and
will take on default values.*)

ParabolaPointTableBasic(numrows_Integer?Positive, 
  coefficientrange : (_Integer?Positive) : 9, 
  truepercentage : (_?(0 <= # <= 1 &)) : 0.5,
  xrange : {_Integer, _Integer} : {-9, 9}, 
  yrange : {_Integer, _Integer} : {-25, 25}) :=
 (* First, make sure x is "fresh" for the duration of 
    this evaluation, and that any external definition of x 
    or f, e.g. x = 5, will not affect us. *)
 Block({f, x},
  (* "With" is a way of saying that symbols explicitly used 
     in the following expression should be repalced with 
     some value (whatever we set in the following list. *)
  With(
   (* First, let's get a list with about truepercentage*
   numrows values of True, and the rest False. 
   We'll do this by asking if each integer between 1 and numrows is 
below truepercentage*numrows, 
   then mixing that list up with RandomSample. *)
   {truelist = 
     RandomSample@Table(i <= truepercentage*numrows, {i, numrows}),
    (* Next, we'll get a list of polynomial functions. 
    We generate a random list of three coefficient ranges, 
    and if the leading coefficient is 0, we change it to 1,
    then apply makePolynomial. *)
    
    polys = 
     Table(
      makePolynomial@
       Replace({0, b_, c_} :> {1, b, c})@
        RandomInteger({-coefficientrange, coefficientrange}, 
         3), {numrows})},
   (* We need a new "With", since we're going to now
      use the variables defined in the previous one. *)
   With(
    (* Get a point in the parabola if the corresponding 
       element of truelist is True, and a point not in the 
       parabola if it's false. *)
    {points = 
      MapThread(ifGetPoint(xrange, yrange), {truelist, polys})},
    (* store the "answer key" in global variable answerKey *)
    answerKey = Transpose({polys, points, truelist});
    (* Put it all together. We have two lists of equal length; 
    that's three rows. We need a third list of just blank space. 
    We need to flip it to turn those rows into columns, 
    so we use Transpose. 
    We also need to format the polynomials and points, 
    and call them f, 
    so we map those formatting functions over the lists. 
    Also, prepend the headers. 
    Wrap the whole thing in Grid and give it appropriate options. *)
    TraditionalForm@Grid(
      Prepend(
        Text /@ {"Quadratic Function", "Point", 
          "Put T if the point belongs n to the graph of the n 
function and F if not."})@
       Transpose({polynomialFormat(f, x) /@ polys, 
         pointFormat /@ points, Table("   ", {numrows})}),
      Frame -> All,
      Alignment -> {{Left, Center, Center}, {Center, 
       {Automatic}}, {1, 1} -> {Center, Center}})
    )
   )
  )

(* Test/example call: *)

ParabolaPointTableBasic(9)

(* Out: *)

A table like the one in the original.

Validate the answers that have been stored in answerKey:

validAnswer({f_, {x_, y_}, answer : (True | False)}) :=
  (f(x) == y) == answer

AllTrue(answerKey, validAnswer)

(* Out (should be): True *)

Improvements we could make:

  • Give the optional arguments as Options instead of default arguments

  • Remove grid from around header elements

  • ✓ Align $f(x)=$ to the left of each cell (added Alignment -> {{Left, Center, Center}, {Center,{Automatic}}, {1, 1} -> {Center, Center}} to Grid)

  • Generate values that are in the function range (considered over the xrange) instead of a predetermined range, so that they seem more realistic

  • ✓ Store the “answer key” as well as the computational content in a global variable somewhere for the instructor (declared variable answerKey)

  • Make storing the answer key optional and controlled by an option

  • ✓ Include way of validating the answer key (via validAnswer for a single triple of {function, point, answer}, and then AllTrue(answerKey, validAnswer))

  • Make it interactive, so that someone could choose True or False in the actual mathematica notebook

  • Provide an “Export” button for exporting it as a given filetype

  • Provide manipulation options for individual elements/the ability to “refresh” individual rows

  • Include optional numbering of rows along the side


Hope this helps; it was fun! Let me know if there’s anything you’d like me to explain or change.

algebra precalculus – Making sense of William Jones’s solution of quadratic equations and notation

In his History of Mathematical notation, Cajori (1993) writes about Jones’s approach to the solution of a quadratic equation as follows:

excerpt

Extract from Cajori (1993)

Could you please help me make sense:

(a) What is meant with “the contrary” of “any sign”?

(b) Do I understand correctly that the “then” part supposed to be a solution to the preceding quadratic equation? If yes, how does this work exactly? How does it align with how we would symbolize the solution today?

differential equations – What is known about gradient descent on quadratic models (not loss functions!)

Let $mathcal X$ be any set, and $f:mathcal Xtimesmathbb R^ntomathbb R$ be a differentiable model, meaning that for any fixed first argument, $f$ is differentiable in its second argument. Then we can perform (continuous time) gradient descent with $f$ using a mean-squared-error loss function, on some fixed training set of elements of $mathcal Xtimesmathbb R$, by which I mean we can solve the initial value problem

$$w'(t)=-nabla_w frac1n sum_i (f(x_i, w(t)) – y_i)^2$$
$$w(0)=w_0$$

If $f$ is linear in its second argument, it is known that this is equivalent to kernel least-squares regression. For example, the training predictions $(f(x_i))_i$ follow a linear ODE with constant coefficients.

What if $f$ is quadratic? Is anything known about the dynamics?

reference request – Sum of binary quadratic forms over inputs of equal Hamming weight

$DeclareMathOperator{field}{mathbb{F}}$
Let $n$ be a positive integer, and let $q : field_2^{n} rightarrow field_2$ be a quadratic form, specified in coordinates as

$$q(x)=sum_{i =1}^n alpha_i x_i + sum_{substack{j,k=1\ j<k}}^n beta_{i,j} x_i x_j$$

for some $alpha_i, beta_{j,k} in field_2$. For each integer $ain {0,dots, n}$, I am interested in the quantity

$$ C_{q,a}=sum_{substack{x in field_2^{n}\ |x|=a}} (-1)^{q(x)} in mathbb{Z},$$

where $|x|$ denotes the Hamming weight of $x$.

Is there a simple formula for $C_{q,a}$? Have these quantities $C_{q,a}$ been studied before?